Remove ORDER BY pk from subqueryload, selectinload

Modified the queries used by subqueryload and selectinload to no longer
ORDER BY the primary key of the parent entity;  this ordering was there to
allow the rows as they come in to be copied into lists directly with a
minimal level of Python-side collation.   However, these ORDER BY clauses
can negatively impact the performance of the query as in many scenarios
these columns are derived from a subquery or are otherwise not actual
primary key columns such that SQL planners cannot make use of indexes. The
Python-side collation uses the native itertools.group_by() to collate the
incoming rows, and has been modified to allow multiple
row-groups-per-parent to be assembled together using list.extend(), which
should still allow for relatively fast Python-side performance.  There will
still be an ORDER BY present for a relationship that includes an explicit
order_by parameter, however this is the only ORDER BY that will be added to
the query for both kinds of loading.

Fixes: #5162
Change-Id: I8befd1303c1af7cc24cbf005f39bc01c8b2745f3

9 files changed, 36 insertions, 46 deletions

diff --git a/test/orm/inheritance/test_poly_loading.py b/test/orm/inheritance/test_poly_loading.py
index d1d57c744..c40794ef4 100644
--- a/test/orm/inheritance/test_poly_loading.py
+++ b/test/orm/inheritance/test_poly_loading.py
@@ -121,14 +121,13 @@ class BaseAndSubFixture(object):
                         "SELECT c.a_sub_id AS c_a_sub_id, "
                         "c.id AS c_id "
                         "FROM c WHERE c.a_sub_id "
-                        "IN ([POSTCOMPILE_primary_keys]) ORDER BY c.a_sub_id",
+                        "IN ([POSTCOMPILE_primary_keys])",
                         {"primary_keys": [2]},
                     ),
                 ),
                 CompiledSQL(
                     "SELECT b.a_id AS b_a_id, b.id AS b_id FROM b "
-                    "WHERE b.a_id IN ([POSTCOMPILE_primary_keys]) "
-                    "ORDER BY b.a_id",
+                    "WHERE b.a_id IN ([POSTCOMPILE_primary_keys])",
                     {"primary_keys": [1, 2]},
                 ),
             ),
@@ -255,7 +254,7 @@ class FixtureLoadTest(_Polymorphic, testing.AssertsExecutionResults):
                 "people.name AS people_name, people.type AS people_type "
                 "FROM people WHERE people.company_id "
                 "IN ([POSTCOMPILE_primary_keys]) "
-                "ORDER BY people.company_id, people.person_id",
+                "ORDER BY people.person_id",
                 {"primary_keys": [1, 2]},
             ),
             AllOf(
diff --git a/test/orm/inheritance/test_polymorphic_rel.py b/test/orm/inheritance/test_polymorphic_rel.py
index b376be12a..830d60b95 100644
--- a/test/orm/inheritance/test_polymorphic_rel.py
+++ b/test/orm/inheritance/test_polymorphic_rel.py
@@ -1955,7 +1955,7 @@ class PolymorphicUnionsTest(_PolymorphicTestBase, _PolymorphicUnions):
                 "JOIN managers ON people.person_id = managers.person_id) "
                 "AS pjoin WHERE pjoin.name = :name_1) AS anon_1 JOIN "
                 "machines ON anon_1.pjoin_person_id = machines.engineer_id "
-                "ORDER BY anon_1.pjoin_person_id, machines.machine_id",
+                "ORDER BY machines.machine_id",
                 params=[{"name_1": "dilbert"}],
             ),
         )
diff --git a/test/orm/inheritance/test_single.py b/test/orm/inheritance/test_single.py
index 3f3718190..553380ac7 100644
--- a/test/orm/inheritance/test_single.py
+++ b/test/orm/inheritance/test_single.py
@@ -640,8 +640,7 @@ class RelationshipFromSingleTest(
             "employee.id AS employee_id FROM employee "
             "WHERE employee.type IN ([POSTCOMPILE_type_1])) AS anon_1 "
             "JOIN employee_stuff ON anon_1.employee_id "
-            "= employee_stuff.employee_id ORDER BY "
-            "anon_1.employee_id",
+            "= employee_stuff.employee_id",
             use_default_dialect=True,
         )
 
diff --git a/test/orm/test_ac_relationships.py b/test/orm/test_ac_relationships.py
index 3d19e5a2f..bb99636d4 100644
--- a/test/orm/test_ac_relationships.py
+++ b/test/orm/test_ac_relationships.py
@@ -274,7 +274,7 @@ class AltSelectableTest(
                 "SELECT a_1.id AS a_1_id, b.id AS b_id FROM a AS a_1 "
                 "JOIN (b JOIN d ON d.b_id = b.id JOIN c ON c.id = d.c_id) "
                 "ON a_1.b_id = b.id WHERE a_1.id "
-                "IN ([POSTCOMPILE_primary_keys]) ORDER BY a_1.id",
+                "IN ([POSTCOMPILE_primary_keys])",
                 [{"primary_keys": [1]}],
             ),
         )
diff --git a/test/orm/test_deferred.py b/test/orm/test_deferred.py
index 9226580ea..a7957ec28 100644
--- a/test/orm/test_deferred.py
+++ b/test/orm/test_deferred.py
@@ -661,7 +661,7 @@ class DeferredOptionsTest(AssertsCompiledSQL, _fixtures.FixtureTest):
                     "FROM (SELECT users.id AS "
                     "users_id FROM users WHERE users.id = :id_1) AS anon_1 "
                     "JOIN orders ON anon_1.users_id = orders.user_id ORDER BY "
-                    "anon_1.users_id, orders.id",
+                    "orders.id",
                     [{"id_1": 7}],
                 ),
             ],
diff --git a/test/orm/test_of_type.py b/test/orm/test_of_type.py
index d6cbcf120..9e9387db9 100644
--- a/test/orm/test_of_type.py
+++ b/test/orm/test_of_type.py
@@ -1063,8 +1063,7 @@ class SubclassRelationshipTest2(
                 "anon_1.t_a_id AS anon_1_t_a_id FROM "
                 "(SELECT t_a.id AS t_a_id FROM t_a) AS anon_1 "
                 "JOIN (t_b AS t_b_1 LEFT OUTER JOIN t_b2 AS t_b2_1 "
-                "ON t_b_1.id = t_b2_1.id) ON anon_1.t_a_id = t_b_1.a_id "
-                "ORDER BY anon_1.t_a_id",
+                "ON t_b_1.id = t_b2_1.id) ON anon_1.t_a_id = t_b_1.a_id",
                 {},
             ),
             CompiledSQL(
@@ -1074,8 +1073,7 @@ class SubclassRelationshipTest2(
                 "AS anon_1 JOIN (t_b AS t_b_1 LEFT OUTER JOIN t_b2 AS t_b2_1 "
                 "ON t_b_1.id = t_b2_1.id) ON anon_1.t_a_id = t_b_1.a_id "
                 "JOIN (t_c AS t_c_1 LEFT OUTER JOIN t_c2 AS t_c2_1 ON "
-                "t_c_1.id = t_c2_1.id) ON t_b_1.id = t_c_1.b_id "
-                "ORDER BY t_b_1.id",
+                "t_c_1.id = t_c2_1.id) ON t_b_1.id = t_c_1.b_id",
                 {},
             ),
             CompiledSQL(
@@ -1088,7 +1086,7 @@ class SubclassRelationshipTest2(
                 "JOIN (t_c AS t_c_1 LEFT OUTER JOIN t_c2 AS t_c2_1 "
                 "ON t_c_1.id = t_c2_1.id) "
                 "ON t_b_1.id = t_c_1.b_id "
-                "JOIN t_d ON t_c_1.id = t_d.c_id ORDER BY t_c_1.id",
+                "JOIN t_d ON t_c_1.id = t_d.c_id",
                 {},
             ),
         )
diff --git a/test/orm/test_relationships.py b/test/orm/test_relationships.py
index 591ef4128..c9a314212 100644
--- a/test/orm/test_relationships.py
+++ b/test/orm/test_relationships.py
@@ -5749,7 +5749,7 @@ class SecondaryIncludesLocalColsTest(fixtures.MappedTest):
                 "(SELECT a.id AS aid, b.id AS id FROM a JOIN b ON a.b_ids "
                 "LIKE :id_1 || b.id || :param_1) AS anon_1 "
                 "ON a_1.id = anon_1.aid JOIN b ON b.id = anon_1.id "
-                "WHERE a_1.id IN ([POSTCOMPILE_primary_keys]) ORDER BY a_1.id",
+                "WHERE a_1.id IN ([POSTCOMPILE_primary_keys])",
                 params=[{"id_1": "%", "param_1": "%", "primary_keys": [2]}],
             ),
         )
diff --git a/test/orm/test_selectin_relations.py b/test/orm/test_selectin_relations.py
index 8453a2606..c7bac95c9 100644
--- a/test/orm/test_selectin_relations.py
+++ b/test/orm/test_selectin_relations.py
@@ -1734,7 +1734,7 @@ class BaseRelationFromJoinedSubclassTest(_Polymorphic):
                 "paperwork.description AS paperwork_description "
                 "FROM paperwork WHERE paperwork.person_id "
                 "IN ([POSTCOMPILE_primary_keys]) "
-                "ORDER BY paperwork.person_id, paperwork.paperwork_id",
+                "ORDER BY paperwork.paperwork_id",
                 [{"primary_keys": [1]}],
             ),
         )
@@ -1784,7 +1784,7 @@ class BaseRelationFromJoinedSubclassTest(_Polymorphic):
                 "paperwork.description AS paperwork_description "
                 "FROM paperwork WHERE paperwork.person_id "
                 "IN ([POSTCOMPILE_primary_keys]) "
-                "ORDER BY paperwork.person_id, paperwork.paperwork_id",
+                "ORDER BY paperwork.paperwork_id",
                 [{"primary_keys": [1]}],
             ),
         )
@@ -1830,7 +1830,7 @@ class BaseRelationFromJoinedSubclassTest(_Polymorphic):
                 "paperwork.description AS paperwork_description "
                 "FROM paperwork WHERE paperwork.person_id "
                 "IN ([POSTCOMPILE_primary_keys]) "
-                "ORDER BY paperwork.person_id, paperwork.paperwork_id",
+                "ORDER BY paperwork.paperwork_id",
                 [{"primary_keys": [1]}],
             ),
         )
@@ -1884,7 +1884,7 @@ class BaseRelationFromJoinedSubclassTest(_Polymorphic):
                 "paperwork.description AS paperwork_description "
                 "FROM paperwork WHERE paperwork.person_id "
                 "IN ([POSTCOMPILE_primary_keys]) "
-                "ORDER BY paperwork.person_id, paperwork.paperwork_id",
+                "ORDER BY paperwork.paperwork_id",
                 [{"primary_keys": [1]}],
             ),
         )
@@ -1932,7 +1932,7 @@ class BaseRelationFromJoinedSubclassTest(_Polymorphic):
                 "paperwork.description AS paperwork_description "
                 "FROM paperwork WHERE paperwork.person_id "
                 "IN ([POSTCOMPILE_primary_keys]) "
-                "ORDER BY paperwork.person_id, paperwork.paperwork_id",
+                "ORDER BY paperwork.paperwork_id",
                 [{"primary_keys": [1]}],
             ),
         )
@@ -2152,7 +2152,7 @@ class TupleTest(fixtures.DeclarativeMappedTest):
             CompiledSQL(
                 "SELECT b.a_id1 AS b_a_id1, b.a_id2 AS b_a_id2, b.id AS b_id "
                 "FROM b WHERE (b.a_id1, b.a_id2) IN "
-                "([POSTCOMPILE_primary_keys]) ORDER BY b.a_id1, b.a_id2, b.id",
+                "([POSTCOMPILE_primary_keys]) ORDER BY b.id",
                 [{"primary_keys": [(i, i + 2) for i in range(1, 20)]}],
             ),
         )
@@ -2257,19 +2257,19 @@ class ChunkingTest(fixtures.DeclarativeMappedTest):
             CompiledSQL(
                 "SELECT b.a_id AS b_a_id, b.id AS b_id "
                 "FROM b WHERE b.a_id IN "
-                "([POSTCOMPILE_primary_keys]) ORDER BY b.a_id, b.id",
+                "([POSTCOMPILE_primary_keys]) ORDER BY b.id",
                 {"primary_keys": list(range(1, 48))},
             ),
             CompiledSQL(
                 "SELECT b.a_id AS b_a_id, b.id AS b_id "
                 "FROM b WHERE b.a_id IN "
-                "([POSTCOMPILE_primary_keys]) ORDER BY b.a_id, b.id",
+                "([POSTCOMPILE_primary_keys]) ORDER BY b.id",
                 {"primary_keys": list(range(48, 95))},
             ),
             CompiledSQL(
                 "SELECT b.a_id AS b_a_id, b.id AS b_id "
                 "FROM b WHERE b.a_id IN "
-                "([POSTCOMPILE_primary_keys]) ORDER BY b.a_id, b.id",
+                "([POSTCOMPILE_primary_keys]) ORDER BY b.id",
                 {"primary_keys": list(range(95, 101))},
             ),
         )
@@ -3047,7 +3047,7 @@ class SingleInhSubclassTest(
             CompiledSQL(
                 "SELECT role.user_id AS role_user_id, role.id AS role_id "
                 "FROM role WHERE role.user_id "
-                "IN ([POSTCOMPILE_primary_keys]) ORDER BY role.user_id",
+                "IN ([POSTCOMPILE_primary_keys])",
                 {"primary_keys": [1]},
             ),
         )
@@ -3205,7 +3205,7 @@ class M2OWDegradeTest(
                 "SELECT a_1.id AS a_1_id, b.id AS b_id, b.x AS b_x, "
                 "b.y AS b_y "
                 "FROM a AS a_1 JOIN b ON b.id = a_1.b_id "
-                "WHERE a_1.id IN ([POSTCOMPILE_primary_keys]) ORDER BY a_1.id",
+                "WHERE a_1.id IN ([POSTCOMPILE_primary_keys])",
                 [{"primary_keys": [1, 3]}],
             ),
         )
@@ -3261,7 +3261,7 @@ class M2OWDegradeTest(
             CompiledSQL(
                 "SELECT a_1.id AS a_1_id, b.id AS b_id, b.x AS b_x, "
                 "b.y AS b_y FROM a AS a_1 JOIN b ON b.id = a_1.b_id "
-                "WHERE a_1.id IN ([POSTCOMPILE_primary_keys]) ORDER BY a_1.id",
+                "WHERE a_1.id IN ([POSTCOMPILE_primary_keys])",
                 [{"primary_keys": [1, 2, 3, 4, 5]}],
             ),
         )
@@ -3296,7 +3296,7 @@ class M2OWDegradeTest(
                 "SELECT a_1.id AS a_1_id, b.id AS b_id, b.x AS b_x, "
                 "b.y AS b_y "
                 "FROM a AS a_1 JOIN b ON b.id = a_1.b_id "
-                "WHERE a_1.id IN ([POSTCOMPILE_primary_keys]) ORDER BY a_1.id",
+                "WHERE a_1.id IN ([POSTCOMPILE_primary_keys])",
                 [{"primary_keys": [1, 2, 3, 4, 5]}],
             ),
         )
diff --git a/test/orm/test_subquery_relations.py b/test/orm/test_subquery_relations.py
index 8bc146f18..f3fdfd3dc 100644
--- a/test/orm/test_subquery_relations.py
+++ b/test/orm/test_subquery_relations.py
@@ -1710,7 +1710,7 @@ class BaseRelationFromJoinedSubclassTest(_Polymorphic):
                 ":primary_language_1) AS anon_1 "
                 "JOIN paperwork "
                 "ON anon_1.people_person_id = paperwork.person_id "
-                "ORDER BY anon_1.people_person_id, paperwork.paperwork_id",
+                "ORDER BY paperwork.paperwork_id",
                 {"primary_language_1": "java"},
             ),
         )
@@ -1767,7 +1767,7 @@ class BaseRelationFromJoinedSubclassTest(_Polymorphic):
                 "paperwork.description = :description_1) AS anon_1 "
                 "JOIN paperwork ON anon_1.people_person_id = "
                 "paperwork.person_id "
-                "ORDER BY anon_1.people_person_id, paperwork.paperwork_id",
+                "ORDER BY paperwork.paperwork_id",
                 {
                     "primary_language_1": "java",
                     "description_1": "tps report #2",
@@ -1832,7 +1832,7 @@ class BaseRelationFromJoinedSubclassTest(_Polymorphic):
                 "WHERE engineers.primary_language = :primary_language_1) "
                 "AS anon_1 JOIN paperwork "
                 "ON anon_1.people_person_id = paperwork.person_id "
-                "ORDER BY anon_1.people_person_id, paperwork.paperwork_id",
+                "ORDER BY paperwork.paperwork_id",
                 {"primary_language_1": "java"},
             ),
             CompiledSQL(
@@ -1847,7 +1847,7 @@ class BaseRelationFromJoinedSubclassTest(_Polymorphic):
                 "AS anon_1 JOIN paperwork AS paperwork_1 "
                 "ON anon_1.people_person_id = paperwork_1.person_id "
                 "JOIN pages ON paperwork_1.paperwork_id = pages.paperwork_id "
-                "ORDER BY paperwork_1.paperwork_id, pages.page_id",
+                "ORDER BY pages.page_id",
                 {"primary_language_1": "java"},
             ),
         )
@@ -1897,7 +1897,7 @@ class BaseRelationFromJoinedSubclassTest(_Polymorphic):
                 "engineers.engineer_id ORDER BY engineers.primary_language "
                 "DESC LIMIT :param_1) AS anon_1 JOIN paperwork "
                 "ON anon_1.people_person_id = paperwork.person_id "
-                "ORDER BY anon_1.people_person_id, paperwork.paperwork_id"
+                "ORDER BY paperwork.paperwork_id"
             ),
         )
 
@@ -1964,8 +1964,7 @@ class BaseRelationFromJoinedSubclassTest(_Polymorphic):
                 "DESC LIMIT :param_1) AS anon_1 "
                 "JOIN paperwork "
                 "ON anon_1.anon_2_people_person_id = paperwork.person_id "
-                "ORDER BY anon_1.anon_2_people_person_id, "
-                "paperwork.paperwork_id"
+                "ORDER BY paperwork.paperwork_id"
             ),
         )
 
@@ -2017,8 +2016,7 @@ class BaseRelationFromJoinedSubclassTest(_Polymorphic):
                 "ON people_1.person_id = engineers_1.engineer_id "
                 "ORDER BY engineers_1.primary_language DESC LIMIT :param_1) "
                 "AS anon_1 JOIN paperwork ON anon_1.people_1_person_id = "
-                "paperwork.person_id ORDER BY anon_1.people_1_person_id, "
-                "paperwork.paperwork_id"
+                "paperwork.person_id ORDER BY paperwork.paperwork_id"
             ),
         )
 
@@ -2716,8 +2714,7 @@ class CyclicalInheritingEagerTestTwo(
             "ON persistent.id = director.id) AS anon_1 "
             "JOIN (persistent JOIN movie "
             "ON persistent.id = movie.id) "
-            "ON anon_1.director_id = movie.director_id "
-            "ORDER BY anon_1.director_id",
+            "ON anon_1.director_id = movie.director_id",
             dialect="default",
         )
 
@@ -2842,8 +2839,7 @@ class SubqueryloadDistinctTest(
             "anon_1.movie_director_id AS anon_1_movie_director_id "
             "FROM (SELECT%s movie.director_id AS movie_director_id "
             "FROM movie) AS anon_1 "
-            "JOIN director ON director.id = anon_1.movie_director_id "
-            "ORDER BY anon_1.movie_director_id"
+            "JOIN director ON director.id = anon_1.movie_director_id"
             % (" DISTINCT" if expect_distinct else ""),
         )
 
@@ -2871,8 +2867,7 @@ class SubqueryloadDistinctTest(
             "JOIN director AS director_1 "
             "ON director_1.id = anon_1.movie_director_id "
             "JOIN director_photo "
-            "ON director_1.id = director_photo.director_id "
-            "ORDER BY director_1.id"
+            "ON director_1.id = director_photo.director_id"
             % (" DISTINCT" if expect_distinct else ""),
         )
         result = s.execute(q3)
@@ -3050,8 +3045,7 @@ class SelfRefInheritanceAliasedTest(
                 "anon_1.foo_foo_id AS anon_1_foo_foo_id "
                 "FROM (SELECT DISTINCT foo.foo_id AS foo_foo_id "
                 "FROM foo WHERE foo.id = :id_1) AS anon_1 "
-                "JOIN foo AS foo_1 ON foo_1.id = anon_1.foo_foo_id "
-                "ORDER BY anon_1.foo_foo_id",
+                "JOIN foo AS foo_1 ON foo_1.id = anon_1.foo_foo_id",
                 {"id_1": 2},
             ),
             CompiledSQL(
@@ -3060,7 +3054,7 @@ class SelfRefInheritanceAliasedTest(
                 "FROM (SELECT DISTINCT foo.foo_id AS foo_foo_id FROM foo "
                 "WHERE foo.id = :id_1) AS anon_1 "
                 "JOIN foo AS foo_1 ON foo_1.id = anon_1.foo_foo_id "
-                "JOIN foo ON foo.id = foo_1.foo_id ORDER BY foo_1.foo_id",
+                "JOIN foo ON foo.id = foo_1.foo_id",
                 {"id_1": 2},
             ),
         )