diff --git a/swh/provenance/archive.py b/swh/provenance/archive.py
--- a/swh/provenance/archive.py
+++ b/swh/provenance/archive.py
@@ -47,8 +47,7 @@
             id: sha1 id of the snapshot.
 
         Yields:
-            sha1 ids of revisions that are a target of such snapshot. Revisions are
-            guaranteed to be retrieved in chronological order
+            sha1 ids of revisions that are a target of such snapshot.
 
         """
         ...
diff --git a/swh/provenance/postgresql/archive.py b/swh/provenance/postgresql/archive.py
--- a/swh/provenance/postgresql/archive.py
+++ b/swh/provenance/postgresql/archive.py
@@ -135,7 +135,7 @@
                               ON (RL.target=RV.id)
                             WHERE B.target_type='release'::snapshot_target
                               AND RL.target_type='revision'::object_type)
-                          ORDER BY date, id)
+                         )
                 SELECT id FROM heads
                 """,
                 (id,),
diff --git a/swh/provenance/storage/archive.py b/swh/provenance/storage/archive.py
--- a/swh/provenance/storage/archive.py
+++ b/swh/provenance/storage/archive.py
@@ -70,4 +70,4 @@
                 if revision is not None and revision.date is not None
             )
 
-        yield from (head for _, head in sorted(revisions))
+        yield from (head for _, head in revisions)