diff --git a/swh/storage/backfill.py b/swh/storage/backfill.py
--- a/swh/storage/backfill.py
+++ b/swh/storage/backfill.py
@@ -579,7 +579,7 @@
             raise ValueError(
                 "Object type %s is not supported. "
                 "The only possible values are %s"
-                % (object_type, ", ".join(COLUMNS.keys()))
+                % (object_type, ", ".join(sorted(COLUMNS.keys())))
             )
 
         if object_type in ["origin", "origin_visit", "origin_visit_status"]:
diff --git a/swh/storage/tests/test_backfill.py b/swh/storage/tests/test_backfill.py
--- a/swh/storage/tests/test_backfill.py
+++ b/swh/storage/tests/test_backfill.py
@@ -59,7 +59,7 @@
 
     error = (
         "Object type unknown-object-type is not supported. "
-        "The only possible values are %s" % (", ".join(PARTITION_KEY))
+        "The only possible values are %s" % (", ".join(sorted(PARTITION_KEY)))
     )
     assert e.value.args[0] == error