Correctly detect incomplete sort_keys passed to paginate_query4.13.1

Currently, the function expects that sort_keys will contain 'id',
otherwise a warning is triggered. This assumption is wrong in multiple
ways. First, models may not have an 'id' attribute. Second, even if the
attribute is present, it may be non-unique irrespective of the name
chosen for it.

The right way of determining sorting keys that would not guarantee
stable sorting order for paginated results is to extract sets of unique
keys from the model itself, and compare sorting keys to those extracted
sets. If at least one of those unique key sets is a subset of passed
sorting keys, then no warning should be issued.

The patch also add _get_unique_keys function but, in contrast to its
Ocata version, does *not* expose it as part of library public API, and
makes it explicit it's not part of it, by using the leading underscore
in its name. The rationale behind that is that we don't want to expose
new features in Newton if possible. The function is a modified version
of a function with a similar name (get_unique_keys) currently maintained
in Neutron tree for similar needs.

To avoid calculating the same result over and over on each call to the
new function, we cache it in info dict of the relevant Table.

Change-Id: I46d9d53ee5f6fa2863b31027fa81997571d6568a
Closes-Bug: #1617996
(cherry picked from commit dea700d13e4c152bf1a484b62cc2bce329ef6fa9)

2 files changed, 135 insertions, 5 deletions

diff --git a/oslo_db/sqlalchemy/utils.py b/oslo_db/sqlalchemy/utils.py
index 594a7f2..136e05a 100644
--- a/oslo_db/sqlalchemy/utils.py
+++ b/oslo_db/sqlalchemy/utils.py
@@ -66,6 +66,48 @@ def sanitize_db_url(url):
     return url
 
 
+def _get_unique_keys(model):
+    """Get a list of sets of unique model keys.
+
+    :param model: the ORM model class
+    :rtype: list of sets of strings
+    :return: unique model keys
+    """
+    # extract result from cache if present
+    info = model.__table__.info
+    if 'oslodb_unique_keys' in info:
+        return info['oslodb_unique_keys']
+
+    res = []
+    try:
+        constraints = model.__table__.constraints
+    except AttributeError:
+        constraints = []
+    for constraint in constraints:
+        # filter out any CheckConstraints
+        if isinstance(constraint, (sqlalchemy.UniqueConstraint,
+                                   sqlalchemy.PrimaryKeyConstraint)):
+            res.append({c.name for c in constraint.columns})
+    try:
+        indexes = model.__table__.indexes
+    except AttributeError:
+        indexes = []
+    for index in indexes:
+        if index.unique:
+            res.append({c.name for c in index.columns})
+    # cache result for next calls with the same model
+    info['oslodb_unique_keys'] = res
+    return res
+
+
+def _stable_sorting_order(model, sort_keys):
+    sort_keys_set = set(sort_keys)
+    for unique_keys in _get_unique_keys(model):
+        if unique_keys.issubset(sort_keys_set):
+            return True
+    return False
+
+
 # copy from glance/db/sqlalchemy/api.py
 def paginate_query(query, model, limit, sort_keys, marker=None,
                    sort_dir=None, sort_dirs=None):
@@ -100,11 +142,9 @@ def paginate_query(query, model, limit, sort_keys, marker=None,
     :rtype: sqlalchemy.orm.query.Query
     :return: The query with sorting/pagination added.
     """
-
-    if 'id' not in sort_keys:
-        # TODO(justinsb): If this ever gives a false-positive, check
-        # the actual primary key, rather than assuming its id
-        LOG.warning(_LW('Id not in sort_keys; is sort_keys unique?'))
+    if not _stable_sorting_order(model, sort_keys):
+        LOG.warning(_LW('Unique keys not in sort_keys. '
+                        'The sorting order may be unstable.'))
 
     assert(not (sort_dir and sort_dirs))
 
diff --git a/oslo_db/tests/sqlalchemy/test_utils.py b/oslo_db/tests/sqlalchemy/test_utils.py
index 19f78ce..6ab2c70 100644
--- a/oslo_db/tests/sqlalchemy/test_utils.py
+++ b/oslo_db/tests/sqlalchemy/test_utils.py
@@ -93,6 +93,28 @@ class FakeTable(Base):
         pass
 
 
+class FakeTableWithMultipleKeys(Base):
+    __tablename__ = 'fake_table_multiple_keys'
+
+    key1 = Column(String(50), primary_key=True)
+    key2 = Column(String(50), primary_key=True)
+    key3 = Column(String(50))
+
+
+class FakeTableWithIndexes(Base):
+    __tablename__ = 'fake_table_unique_index'
+
+    id = Column(String(50), primary_key=True)
+    key1 = Column(String(50))
+    key2 = Column(String(50))
+    key3 = Column(String(50))
+
+    __table_args__ = (
+        Index('idx_unique', 'key1', 'key2', unique=True),
+        Index('idx_unique', 'key1', 'key3', unique=False),
+    )
+
+
 class FakeModel(object):
     def __init__(self, values):
         self.values = values
@@ -276,6 +298,74 @@ class TestPaginateQuery(test_base.BaseTestCase):
                              sort_dirs=['asc', 'desc'])
 
 
+class Test_UnstableSortingOrder(test_base.BaseTestCase):
+    def test_multiple_primary_keys_stable(self):
+        self.assertTrue(
+            utils._stable_sorting_order(
+                FakeTableWithMultipleKeys, ['key1', 'key2']))
+
+    def test_multiple_primary_keys_unstable(self):
+        self.assertFalse(
+            utils._stable_sorting_order(
+                FakeTableWithMultipleKeys, ['key1', 'key3']))
+
+    def test_unique_index_stable(self):
+        self.assertTrue(
+            utils._stable_sorting_order(
+                FakeTableWithIndexes, ['key1', 'key2']))
+
+    def test_unique_index_unstable(self):
+        self.assertFalse(
+            utils._stable_sorting_order(
+                FakeTableWithIndexes, ['key1', 'key3']))
+
+
+class TestGetUniqueKeys(test_base.BaseTestCase):
+    def test_multiple_primary_keys(self):
+        self.assertEqual(
+            [{'key1', 'key2'}],
+            utils._get_unique_keys(FakeTableWithMultipleKeys))
+
+    def test_unique_index(self):
+        self.assertEqual(
+            [{'id'}, {'key1', 'key2'}],
+            utils._get_unique_keys(FakeTableWithIndexes))
+
+    def test_cache(self):
+
+        class CacheTable(object):
+            info = {}
+            constraints_called = 0
+            indexes_called = 0
+
+            @property
+            def constraints(self):
+                self.constraints_called += 1
+                return []
+
+            @property
+            def indexes(self):
+                self.indexes_called += 1
+                return []
+
+        class CacheModel(object):
+            __table__ = CacheTable()
+
+        model = CacheModel()
+        self.assertNotIn('oslodb_unique_keys', CacheTable.info)
+        utils._get_unique_keys(model)
+
+        self.assertIn('oslodb_unique_keys', CacheTable.info)
+        self.assertEqual(1, model.__table__.constraints_called)
+        self.assertEqual(1, model.__table__.indexes_called)
+
+        for i in range(10):
+            utils._get_unique_keys(model)
+
+        self.assertEqual(1, model.__table__.constraints_called)
+        self.assertEqual(1, model.__table__.indexes_called)
+
+
 class TestPaginateQueryActualSQL(test_base.BaseTestCase):
 
     def test_paginate_on_hybrid_assert_stmt(self):