Refs #17198 -- Detected existing total ordering in admin changelist.

Appending pk is not necessary when a subset of the ordering expressions is
contained in a non-nullable unique contraint.

Related field ordering through lookups and related ordering introspection is
omitted for simplicitly purpose.

2 files changed, 134 insertions, 12 deletions

diff --git a/django/contrib/admin/views/main.py b/django/contrib/admin/views/main.py
index 2f5616f4bd..298e18c57e 100644
--- a/django/contrib/admin/views/main.py
+++ b/django/contrib/admin/views/main.py
@@ -273,8 +273,8 @@ class ChangeList:
         First check the get_ordering() method in model admin, then check
         the object's default ordering. Then, any manually-specified ordering
         from the query string overrides anything. Finally, a deterministic
-        order is guaranteed by ensuring the primary key is used as the last
-        ordering field.
+        order is guaranteed by calling _get_deterministic_ordering() with the
+        constructed ordering.
         """
         params = self.params
         ordering = list(self.model_admin.get_ordering(request) or self._get_default_ordering())
@@ -303,15 +303,60 @@ class ChangeList:
         # Add the given query's ordering fields, if any.
         ordering.extend(queryset.query.order_by)
 
-        # Ensure that the primary key is systematically present in the list of
-        # ordering fields so we can guarantee a deterministic order across all
-        # database backends.
-        pk_name = self.lookup_opts.pk.name
-        if {'pk', '-pk', pk_name, '-' + pk_name}.isdisjoint(ordering):
-            # The two sets do not intersect, meaning the pk isn't present. So
-            # we add it.
-            ordering.append('-pk')
+        return self._get_deterministic_ordering(ordering)
 
+    def _get_deterministic_ordering(self, ordering):
+        """
+        Ensure a deterministic order across all database backends. Search for a
+        single field or unique together set of fields providing a total
+        ordering. If these are missing, augment the ordering with a descendant
+        primary key.
+        """
+        ordering = list(ordering)
+        ordering_fields = set()
+        total_ordering_fields = {'pk'} | {
+            field.attname for field in self.lookup_opts.fields
+            if field.unique and not field.null
+        }
+        for part in ordering:
+            # Search for single field providing a total ordering.
+            field_name = None
+            if isinstance(part, str):
+                field_name = part.lstrip('-')
+            elif isinstance(part, F):
+                field_name = part.name
+            elif isinstance(part, OrderBy) and isinstance(part.expression, F):
+                field_name = part.expression.name
+            if field_name:
+                # Normalize attname references by using get_field().
+                try:
+                    field = self.lookup_opts.get_field(field_name)
+                except FieldDoesNotExist:
+                    # Could be "?" for random ordering or a related field
+                    # lookup. Skip this part of introspection for now.
+                    continue
+                # Ordering by a related field name orders by the referenced
+                # model's ordering. Skip this part of introspection for now.
+                if field.remote_field and field_name == field.name:
+                    continue
+                if field.attname in total_ordering_fields:
+                    break
+                ordering_fields.add(field.attname)
+        else:
+            # No single total ordering field, try unique_together.
+            for field_names in self.lookup_opts.unique_together:
+                # Normalize attname references by using get_field().
+                fields = [self.lookup_opts.get_field(field_name) for field_name in field_names]
+                # Composite unique constraints containing a nullable column
+                # cannot ensure total ordering.
+                if any(field.null for field in fields):
+                    continue
+                if ordering_fields.issuperset(field.attname for field in fields):
+                    break
+            else:
+                # If no set of unique fields is present in the ordering, rely
+                # on the primary key to provide total ordering.
+                ordering.append('-pk')
         return ordering
 
     def get_ordering_field_columns(self):
diff --git a/tests/admin_changelist/tests.py b/tests/admin_changelist/tests.py
index df2c1b09f7..dfd8e91451 100644
--- a/tests/admin_changelist/tests.py
+++ b/tests/admin_changelist/tests.py
@@ -8,7 +8,7 @@ from django.contrib.admin.tests import AdminSeleniumTestCase
 from django.contrib.admin.views.main import ALL_VAR, SEARCH_VAR
 from django.contrib.auth.models import User
 from django.contrib.contenttypes.models import ContentType
-from django.db import connection
+from django.db import connection, models
 from django.db.models import F
 from django.db.models.fields import Field, IntegerField
 from django.db.models.functions import Upper
@@ -16,7 +16,9 @@ from django.db.models.lookups import Contains, Exact
 from django.template import Context, Template, TemplateSyntaxError
 from django.test import TestCase, override_settings
 from django.test.client import RequestFactory
-from django.test.utils import CaptureQueriesContext, register_lookup
+from django.test.utils import (
+    CaptureQueriesContext, isolate_apps, register_lookup,
+)
 from django.urls import reverse
 from django.utils import formats
 
@@ -937,6 +939,81 @@ class ChangeListTests(TestCase):
         OrderedObjectAdmin.ordering = ['id', 'bool']
         check_results_order(ascending=True)
 
+    @isolate_apps('admin_changelist')
+    def test_total_ordering_optimization(self):
+        class Related(models.Model):
+            unique_field = models.BooleanField(unique=True)
+
+            class Meta:
+                ordering = ('unique_field',)
+
+        class Model(models.Model):
+            unique_field = models.BooleanField(unique=True)
+            unique_nullable_field = models.BooleanField(unique=True, null=True)
+            related = models.ForeignKey(Related, models.CASCADE)
+            other_related = models.ForeignKey(Related, models.CASCADE)
+            related_unique = models.OneToOneField(Related, models.CASCADE)
+            field = models.BooleanField()
+            other_field = models.BooleanField()
+            null_field = models.BooleanField(null=True)
+
+            class Meta:
+                unique_together = {
+                    ('field', 'other_field'),
+                    ('field', 'null_field'),
+                    ('related', 'other_related_id'),
+                }
+
+        class ModelAdmin(admin.ModelAdmin):
+            def get_queryset(self, request):
+                return Model.objects.none()
+
+        request = self._mocked_authenticated_request('/', self.superuser)
+        site = admin.AdminSite(name='admin')
+        model_admin = ModelAdmin(Model, site)
+        change_list = model_admin.get_changelist_instance(request)
+        tests = (
+            ([], ['-pk']),
+            # Unique non-nullable field.
+            (['unique_field'], ['unique_field']),
+            (['-unique_field'], ['-unique_field']),
+            # Unique nullable field.
+            (['unique_nullable_field'], ['unique_nullable_field', '-pk']),
+            # Field.
+            (['field'], ['field', '-pk']),
+            # Related field introspection is not implemented.
+            (['related__unique_field'], ['related__unique_field', '-pk']),
+            # Related attname unique.
+            (['related_unique_id'], ['related_unique_id']),
+            # Related ordering introspection is not implemented.
+            (['related_unique'], ['related_unique', '-pk']),
+            # Composite unique.
+            (['field', '-other_field'], ['field', '-other_field']),
+            # Composite unique nullable.
+            (['-field', 'null_field'], ['-field', 'null_field', '-pk']),
+            # Composite unique nullable.
+            (['-field', 'null_field'], ['-field', 'null_field', '-pk']),
+            # Composite unique nullable.
+            (['-field', 'null_field'], ['-field', 'null_field', '-pk']),
+            # Composite unique and nullable.
+            (['-field', 'null_field', 'other_field'], ['-field', 'null_field', 'other_field']),
+            # Composite unique attnames.
+            (['related_id', '-other_related_id'], ['related_id', '-other_related_id']),
+            # Composite unique names.
+            (['related', '-other_related_id'], ['related', '-other_related_id', '-pk']),
+        )
+        # F() objects composite unique.
+        total_ordering = [F('field'), F('other_field').desc(nulls_last=True)]
+        # F() objects composite unique nullable.
+        non_total_ordering = [F('field'), F('null_field').desc(nulls_last=True)]
+        tests += (
+            (total_ordering, total_ordering),
+            (non_total_ordering, non_total_ordering + ['-pk']),
+        )
+        for ordering, expected in tests:
+            with self.subTest(ordering=ordering):
+                self.assertEqual(change_list._get_deterministic_ordering(ordering), expected)
+
     def test_dynamic_list_filter(self):
         """
         Regression tests for ticket #17646: dynamic list_filter support.