The provided starting key does not match the range key predicate

I have a DynamoDB table where:

PK: String

and a GSI on this table where PK and SK are attributes of the original table:

PK: String

SK: String 

(actually the SK it's the String representation of a Java Instant)

For a test, I'm trying to crawl over the pages returned by the queryPage method.
I've created 4 items and set the page size to 2.

When retrieving the first page (2 items) I'm doing:

DynamoDbAddress key = new DynamoDbAddress();
key.setProvider(DATA_PROVIDER);

return dbMapper.queryPage(DynamoDbAddress.class, new DynamoDBQueryExpression<DynamoDbAddress>()
                .withLimit(pageSize)
                .withIndexName(TABLE_GSI)
                .withHashKeyValues(key)
                .withRangeKeyCondition("Time", new Condition().withComparisonOperator(ComparisonOperator.LE)
                        .withAttributeValueList(new AttributeValue(Instant.now().minus(26, ChronoUnit.DAYS).toString())))
                )
        .getResults();

This snippet is working fine and retrieves 2 elements as expected.
When retrieving the second page (the final 2 items), I'm doing:

    DynamoDbAddress key = new DynamoDbAddress();
    key.setProvider(DATA_PROVIDER);

    return dbMapper.queryPage(DynamoDbAddress.class, new DynamoDBQueryExpression<DynamoDbAddress>()
            .withLimit(pageSize)
            .withIndexName(TABLE_GSI)
            .withHashKeyValues(key)
            .withRangeKeyCondition("Time", new Condition().withComparisonOperator(ComparisonOperator.LE)
                    .withAttributeValueList(new AttributeValue(Instant.now().minus(26, ChronoUnit.DAYS).toString())))
            .withExclusiveStartKey(Map.of(
                            "Provider", new AttributeValue().withS(lastProcessed.getProvider().toString()),
                            "Time", new AttributeValue().withS(lastProcessed.getTime().toString()),
                            "PK", new AttributeValue().withS(lastProcessed.getPartitionKey()))))
.getResults();

However, I'm getting the following error:

The provided starting key does not match the range key predicate

My interpretation of the error is that "the lastProcessed element does not match the condition expressed in the range key". However, this looks a little absurd to me, as it was retrieved by the very same query in the snippet executed a second before.

I've also verified the test data match the key condition

Why are you trying to manually reconstruct the ExclusiveStartKey? To avoid issues, like the one you are seeing, you should call getLastEvaluatedKey()

    DynamoDbAddress key = new DynamoDbAddress();
    key.setProvider(DATA_PROVIDER);

    return dbMapper.queryPage(DynamoDbAddress.class, new DynamoDBQueryExpression<DynamoDbAddress>()
            .withLimit(pageSize)
            .withIndexName(TABLE_GSI)
            .withHashKeyValues(key)
            .withRangeKeyCondition("Time", new Condition().withComparisonOperator(ComparisonOperator.LE)
                    .withAttributeValueList(new AttributeValue(Instant.now().minus(26, ChronoUnit.DAYS).toString())))
            .withExclusiveStartKey(lastResult.getEvaluatedKey())
.getResults();