diff --git a/swh/storage/algos/origin.py b/swh/storage/algos/origin.py
--- a/swh/storage/algos/origin.py
+++ b/swh/storage/algos/origin.py
@@ -69,25 +69,29 @@
         status exist (and match the search criteria), None otherwise.
 
     """
-    # visits order are from older visit to most recent.
-    visits = list(storage.origin_visit_get(origin_url))
-    visits.reverse()
-    if not visits:
-        return None
-    visit_status: Optional[OriginVisitStatus] = None
-    visit: Dict[str, Any]
-    # Iterate over the visits in reverse order, so the most recent match is found first
-    for visit in visits:
-        if type is not None and visit["type"] != type:
-            continue
-        visit_status = storage.origin_visit_status_get_latest(
-            origin_url,
-            visit["visit"],
-            allowed_statuses=allowed_statuses,
-            require_snapshot=require_snapshot,
+    last_visit = None
+    while True:
+        visits = list(
+            storage.origin_visit_get(
+                origin_url, last_visit=last_visit, order="desc", limit=10,
+            )
         )
-        if visit_status is not None:
-            break
-    if visit_status is None:
-        return None
-    return (OriginVisit.from_dict(visit), visit_status)
+        if not visits:
+            return None
+        last_visit = visits[-1]["visit"]
+
+        visit_status: Optional[OriginVisitStatus] = None
+        visit: Dict[str, Any]
+        for visit in visits:
+            if type is not None and visit["type"] != type:
+                continue
+            visit_status = storage.origin_visit_status_get_latest(
+                origin_url,
+                visit["visit"],
+                allowed_statuses=allowed_statuses,
+                require_snapshot=require_snapshot,
+            )
+            if visit_status is not None:
+                return (OriginVisit.from_dict(visit), visit_status)
+        if last_visit is None:
+            return None
diff --git a/swh/storage/algos/snapshot.py b/swh/storage/algos/snapshot.py
--- a/swh/storage/algos/snapshot.py
+++ b/swh/storage/algos/snapshot.py
@@ -67,7 +67,7 @@
 
     """
     visit_and_status = origin_get_latest_visit_status(
-        storage, origin, allowed_statuses=allowed_statuses, require_snapshot=True
+        storage, origin, allowed_statuses=allowed_statuses, require_snapshot=True,
     )
 
     if not visit_and_status:
diff --git a/swh/storage/tests/algos/test_snapshot.py b/swh/storage/tests/algos/test_snapshot.py
--- a/swh/storage/tests/algos/test_snapshot.py
+++ b/swh/storage/tests/algos/test_snapshot.py
@@ -135,20 +135,8 @@
         ]
     )
 
-    actual_snapshot = snapshot_get_latest(swh_storage, origin.url)
-    assert actual_snapshot is not None
-    assert actual_snapshot == complete_snapshot
-
-    swh_storage.origin_visit_status_add(
-        [
-            OriginVisitStatus(
-                origin=origin.url,
-                visit=visit_id,
-                date=date_now,
-                status="full",
-                snapshot=complete_snapshot.id,
-            )
-        ]
+    swh_storage.origin_visit_add(
+        [OriginVisit(origin=origin.url, date=now(), type=data.type_visit1,)]
     )
 
     actual_snapshot = snapshot_get_latest(swh_storage, origin.url)