Repository: getmoto/moto
Pull request #7555 (2024-04-02 16:43:21)

DynamoDB: query/scan secondary index fixes
Recent logic added in 194088 to accommodate a missing start key brain-damaged pagination because determination of previously-encountered items was not implemented correctly for all use cases.

* Make sure comparisons are performed in the sense of `ScanIndexForward` (previously, this was assumed to be `True` -- the default -- and returned incorrect results when reverse sorting was requested)
* When querying/scanning a secondary index, make comparisons using the index attribute(s) instead of the primary table attribute(s)

This commit now passes my project's internal test suite, and also passes all existing moto DynamoDB unit tests. I expect to add a commit with a unit test that exercises a query with reverse sorting on a GSI with different key attributes, which describes my application's unit test that failed prior to this fix.

rbailey-godaddy: Fixes: #7554 
codecov[bot]: ## [Codecov](https://app.codecov.io/gh/getmoto/moto/pull/7555?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getmoto) Report
Attention: Patch coverage is `94.28571%` with `2 lines` in your changes are missing coverage. Please review.
> Project coverage is 94.07%. Comparing base [(`9aef694`)](https://app.codecov.io/gh/getmoto/moto/commit/9aef6944da6a6f1b84be99cefb34f1724e6ca58f?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getmoto) to head [(`b8dc4ce`)](https://app.codecov.io/gh/getmoto/moto/pull/7555?dropdown=coverage&src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getmoto).
> Report is 156 commits behind head on master.

| [Files](https://app.codecov.io/gh/getmoto/moto/pull/7555?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getmoto) | Patch % | Lines |
|---|---|---|
| [moto/dynamodb/models/table.py](https://app.codecov.io/gh/getmoto/moto/pull/7555?src=pr&el=tree&filepath=moto%2Fdynamodb%2Fmodels%2Ftable.py&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getmoto#diff-bW90by9keW5hbW9kYi9tb2RlbHMvdGFibGUucHk=) | 94.11% | [2 Missing :warning: ](https://app.codecov.io/gh/getmoto/moto/pull/7555?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getmoto) |

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##           master    #7555      +/-   ##
==========================================
- Coverage   95.88%   94.07%   -1.82%     
==========================================
  Files         843     1070     +227     
  Lines       82578    91882    +9304     
==========================================
+ Hits        79178    86434    +7256     
- Misses       3400     5448    +2048     
```

| [Flag](https://app.codecov.io/gh/getmoto/moto/pull/7555/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getmoto) | Coverage Δ | |
|---|---|---|
| [servertests](https://app.codecov.io/gh/getmoto/moto/pull/7555/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getmoto) | `29.55% <2.85%> (-2.97%)` | :arrow_down: |
| [unittests](https://app.codecov.io/gh/getmoto/moto/pull/7555/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getmoto) | `94.04% <94.28%> (-1.81%)` | :arrow_down: |

Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getmoto#carryforward-flags-in-the-pull-request-comment) to find out more.


</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/getmoto/moto/pull/7555?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getmoto).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getmoto).


Patch:
diff --git a/moto/dynamodb/models/table.py b/moto/dynamodb/models/table.py
index 8e24760bb..6f9c4f933 100644
--- a/moto/dynamodb/models/table.py
+++ b/moto/dynamodb/models/table.py
@@ -698,19 +698,27 @@ class Table(CloudFormationModel):
                         f"Range Key comparison but no range key found for index: {index_name}"
                     )
 
+            actual_hash_attr = index_hash_key["AttributeName"]
+            actual_range_attr = (
+                index_range_key["AttributeName"] if index_range_key else None
+            )
+
             possible_results = []
             for item in self.all_items():
                 if not isinstance(item, Item):
                     continue
-                item_hash_key = item.attrs.get(index_hash_key["AttributeName"])
-                if index_range_key is None:
+                item_hash_key = item.attrs.get(actual_hash_attr)
+                if actual_range_attr is None:
                     if item_hash_key and item_hash_key == hash_key:
                         possible_results.append(item)
                 else:
-                    item_range_key = item.attrs.get(index_range_key["AttributeName"])
+                    item_range_key = item.attrs.get(actual_range_attr)
                     if item_hash_key and item_hash_key == hash_key and item_range_key:
                         possible_results.append(item)
         else:
+            actual_hash_attr = self.hash_key_attr
+            actual_range_attr = self.range_key_attr
+
             possible_results = [
                 item
                 for item in self.all_items()
@@ -719,15 +727,15 @@ class Table(CloudFormationModel):
 
         # SORT
         if index_name:
-            if index_range_key:
+            if actual_range_attr is not None:
                 # Convert to float if necessary to ensure proper ordering
                 def conv(x: DynamoType) -> Any:
                     return float(x.value) if x.type == "N" else x.value
 
                 possible_results.sort(
                     key=lambda item: (  # type: ignore
-                        conv(item.attrs[index_range_key["AttributeName"]])  # type: ignore
-                        if item.attrs.get(index_range_key["AttributeName"])
+                        conv(item.attrs[actual_range_attr])  # type: ignore
+                        if item.attrs.get(actual_range_attr)
                         else None
                     )
                 )
@@ -747,7 +755,13 @@ class Table(CloudFormationModel):
             # Cycle through the previous page of results
             # When we encounter our start key, we know we've reached the end of the previous page
             if processing_previous_page:
-                if self._item_comes_before_dct(result, exclusive_start_key):
+                if self._item_comes_before_dct(
+                    result,
+                    exclusive_start_key,
+                    actual_hash_attr,
+                    actual_range_attr,
+                    scan_index_forward,
+                ):
                     continue
                 else:
                     processing_previous_page = False
@@ -873,8 +887,32 @@ class Table(CloudFormationModel):
                     "Consistent reads are not supported on global secondary indexes"
                 )
 
+            try:
+                index_hash_key = [
+                    key for key in index.schema if key["KeyType"] == "HASH"
+                ][0]
+            except IndexError:
+                raise MockValidationException(
+                    f"Missing Hash Key. KeySchema: {index.name}"
+                )
+
+            try:
+                index_range_key = [
+                    key for key in index.schema if key["KeyType"] == "RANGE"
+                ][0]
+            except IndexError:
+                index_range_key = None
+
+            actual_hash_attr = index_hash_key["AttributeName"]
+            actual_range_attr = (
+                index_range_key["AttributeName"] if index_range_key else None
+            )
+
             items = self.has_idx_items(index_name)
         else:
+            actual_hash_attr = self.hash_key_attr
+            actual_range_attr = self.range_key_attr
+
             items = self.all_items()
 
         last_evaluated_key = None
@@ -883,7 +921,13 @@ class Table(CloudFormationModel):
             # Cycle through the previous page of results
             # When we encounter our start key, we know we've reached the end of the previous page
             if processing_previous_page:
-                if self._item_comes_before_dct(item, exclusive_start_key):
+                if self._item_comes_before_dct(
+                    item,
+                    exclusive_start_key,
+                    actual_hash_attr,
+                    actual_range_attr,
+                    True,
+                ):
                     continue
                 else:
                     processing_previous_page = False
@@ -937,16 +981,31 @@ class Table(CloudFormationModel):
 
         return results, scanned_count, last_evaluated_key
 
-    def _item_comes_before_dct(self, item: Item, dct: Dict[str, Any]) -> bool:
-        hash_key = DynamoType(dct.get(self.hash_key_attr))  # type: ignore[arg-type]
-        range_key = dct.get(self.range_key_attr) if self.range_key_attr else None
-        if range_key is not None:
-            range_key = DynamoType(range_key)
-            if item.hash_key < hash_key:
-                return True
-            else:
-                return item.hash_key <= hash_key and item.range_key <= range_key
-        return item.hash_key <= hash_key
+    def _item_comes_before_dct(
+        self,
+        item: Item,
+        dct: Dict[str, Any],
+        hash_key_attr: str,
+        range_key_attr: Optional[str],
+        scan_index_forward: bool,
+    ) -> bool:
+        """Does item appear before or at dct relative to sort options?"""
+        dict_hash_val = DynamoType(dct.get(hash_key_attr))  # type: ignore[arg-type]
+        item_hash_val = item.attrs[hash_key_attr]
+        if item_hash_val != dict_hash_val:
+            # If hash keys are different, order immediately
+            return bool(item_hash_val < dict_hash_val) == scan_index_forward
+        if range_key_attr is None:
+            # If hash keys match and no range key, items are identical
+            return True
+        # We know hash keys are equal, use range key as tiebreaker
+        dict_range_val = DynamoType(dct.get(range_key_attr))  # type: ignore[arg-type]
+        item_range_val = item.attrs[range_key_attr]
+        if item_range_val == dict_range_val:
+            # If range keys (also) match, items are identical
+            return True
+        # Range keys are different, order accordingly
+        return bool(item_range_val < dict_range_val) == scan_index_forward  # type: ignore[arg-type]
 
     def _get_last_evaluated_key(
         self, last_result: Item, index_name: Optional[str]
diff --git a/moto/dynamodb/responses.py b/moto/dynamodb/responses.py
index 3b50dfc7a..20dd2d314 100644
--- a/moto/dynamodb/responses.py
+++ b/moto/dynamodb/responses.py
@@ -730,7 +730,7 @@ class DynamoHandler(BaseResponse):
         index_name = self.body.get("IndexName")
         exclusive_start_key = self.body.get("ExclusiveStartKey")
         limit = self.body.get("Limit")
-        scan_index_forward = self.body.get("ScanIndexForward")
+        scan_index_forward = self.body.get("ScanIndexForward", True)
         consistent_read = self.body.get("ConsistentRead", False)
 
         items, scanned_count, last_evaluated_key = self.dynamodb_backend.query(


Test patch:
diff --git a/tests/test_dynamodb/test_dynamodb.py b/tests/test_dynamodb/test_dynamodb.py
index 592aa8407..d798b9236 100644
--- a/tests/test_dynamodb/test_dynamodb.py
+++ b/tests/test_dynamodb/test_dynamodb.py
@@ -5497,3 +5497,81 @@ def test_query_with_unknown_last_evaluated_key(table_name=None):
         ExclusiveStartKey=different_key,
     )
     assert p4["Items"] == [{"pk": {"S": "hash_value"}, "sk": {"S": "range_value6"}}]
+
+
+@mock_aws
+def test_query_with_gsi_reverse_paginated():
+    client = boto3.client("dynamodb", region_name="us-west-2")
+    table_name = "unit-test-table"
+    index_name = "alternate"
+
+    # Create table - GSI has dissimilar attributes from the main table
+    client.create_table(
+        AttributeDefinitions=[
+            {"AttributeName": "pri", "AttributeType": "S"},
+            {"AttributeName": "alt", "AttributeType": "S"},
+        ],
+        TableName=table_name,
+        KeySchema=[
+            {"AttributeName": "pri", "KeyType": "HASH"},
+        ],
+        GlobalSecondaryIndexes=[
+            {
+                "IndexName": index_name,
+                "KeySchema": [
+                    {"AttributeName": "alt", "KeyType": "HASH"},
+                    {"AttributeName": "pri", "KeyType": "RANGE"},
+                ],
+                "Projection": {"ProjectionType": "KEYS_ONLY"},
+            },
+        ],
+        BillingMode="PAY_PER_REQUEST",
+    )
+
+    # Add some items. These are chosen so that the order of addition is not
+    # lexical order for the chosen values, i.e.
+    # pri: pri_5, pri_6, pri_7, pri_8, pri_9, pri_10, pri_11, pri_12, pri_13, pri_14
+    # alt: alt_1, alt_1, alt_1, alt_2, alt_2,  alt_2,  alt_2,  alt_3,  alt_3,  alt_3
+    for i in range(5, 15):
+        client.put_item(
+            TableName=table_name,
+            Item={
+                "pri": {"S": f"pri_{i}"},
+                "alt": {"S": f"alt_{i//4}"},
+            },
+        )
+
+    # Let's reverse-sort a query on the alternate index. These items match "alt_2":
+    # in insertion order: pri_8, pri_9, pri_10, pri_11
+    # in lexical order: pri_10, pri_11, pri_8, pri_9
+    # in reverse order: pri_9, pri_8, pri_11, pri_10
+    p1 = client.query(
+        TableName=table_name,
+        IndexName=index_name,
+        KeyConditionExpression="#h = :h",
+        ExpressionAttributeNames={"#h": "alt"},
+        ExpressionAttributeValues={":h": {"S": "alt_2"}},
+        ScanIndexForward=False,
+        Limit=2,
+    )
+    assert p1["Items"] == [
+        {"pri": {"S": "pri_9"}, "alt": {"S": "alt_2"}},
+        {"pri": {"S": "pri_8"}, "alt": {"S": "alt_2"}},
+    ]
+
+    # Fetch the second page of results
+    p2 = client.query(
+        TableName=table_name,
+        IndexName=index_name,
+        KeyConditionExpression="#h = :h",
+        ExpressionAttributeNames={"#h": "alt"},
+        ExpressionAttributeValues={":h": {"S": "alt_2"}},
+        ScanIndexForward=False,
+        Limit=2,
+        ExclusiveStartKey=p1["LastEvaluatedKey"],
+    )
+    assert p2["Items"] == [
+        {"pri": {"S": "pri_11"}, "alt": {"S": "alt_2"}},
+        {"pri": {"S": "pri_10"}, "alt": {"S": "alt_2"}},
+    ]
+    assert "LastEvaluatedKey" not in p2