Repository: openfga/openfga

Issue:
Collation issue in OrderedCombinedIterator
### Description

[Initially reported by @danloiterton in this [discussion](https://github.com/orgs/openfga/discussions/491)]

When using PostgresDB as the datastore for OpenFGA, certain checks return an Internal Server Error "iterator 0 is not in ascending order".

`POST .../stores/{{fga-store-id}}/check` with:

```
{
  "tuple_key": {
    "user": "user:ABC123",
    "relation": "member",
    "object": "project:MYPROJECT"
  }
}
```

```
ERROR   rpc error: code = Code(4000) desc = Internal Server Error       {"grpc_service": "openfga.v1.OpenFGAService", "grpc_method": "Check", "grpc_type": "unary", "user_agent": "PostmanRuntime/7.45.0", "raw_request": {"store_id":"01JB24DR66DCNK7YCHR70V59QQ","tuple_key":{"user":"user:___","relation":"member","object":"project:___"},"contextual_tuples":null,"authorization_model_id":"","trace":false,"context":null,"consistency":"UNSPECIFIED"}, "raw_response": {"code":"internal_error","message":"Internal Server Error"}, "query_duration_ms": "181", "request_id": "df21a2d6-41dd-44a6-bdc2-6f82b03b5c6a", "store_id": "01JB24DR66DCNK7YCHR70V59QQ", "authorization_model_id": "01K2YCX3YYHTJ37NEVJNGYFGDZ", "dispatch_count": 0, "datastore_query_count": 5, "request.throttled": false, "peer.address": "127.0.0.1:33980", "grpc_code": 4000, "internal_error": "iterator 0 is not in ascending order"}
```



### OpenFGA version

1.9.3

### How are you running OpenFGA?

As a binary

### What datastore are you using?

Postgres

### OpenFGA Flags

-

### Logs

_No response_

Discussion:
@tylernix: https://github.com/orgs/openfga/discussions/491#discussioncomment-14630947

Solution patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 0cb18e93..e08fe486 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -30,6 +30,9 @@ Try to keep listed changes to a concise bulleted list of simple explanations of
 - Fixed bug in how experimental ReverseExpand support for ttus with multiple parents in the intersection and exclusion for list objects. [#2691](https://github.com/openfga/openfga/pull/2691)
 - Improve performance by allowing weight 2 optimization if the directly assignable userset types are of different types. [#2645](https://github.com/openfga/openfga/pull/2645)
 - Update ListObjects' check resolver to use correct environment variable. [#2653](https://github.com/openfga/openfga/pull/2653)
+- !!REQUIRES MIGRATION!! Collation specification for queries dependent on sort order. [#2661](https://github.com/openfga/openfga/pull/2661)
+    - PostgreSQL is non-disruptive.
+    - MySQL requires a shared lock on the tuple table during the transaction.
 
 ## [1.9.5] - 2025-08-15
 ### Fixed
diff --git a/assets/migrations/mysql/007_collate_object_id.sql b/assets/migrations/mysql/007_collate_object_id.sql
new file mode 100644
index 00000000..851f6626
--- /dev/null
+++ b/assets/migrations/mysql/007_collate_object_id.sql
@@ -0,0 +1,15 @@
+-- +goose Up
+ALTER TABLE tuple MODIFY COLUMN object_id VARCHAR(255) COLLATE utf8mb4_bin,
+LOCK = SHARED;
+
+CREATE INDEX idx_user_lookup ON tuple (store, _user, relation, object_type, object_id) LOCK = NONE;
+
+DROP INDEX idx_reverse_lookup_user ON tuple LOCK = NONE;
+
+-- +goose Down
+DROP INDEX idx_user_lookup on tuple LOCK = NONE;
+
+ALTER TABLE tuple MODIFY COLUMN object_id VARCHAR(255),
+LOCK = SHARED;
+
+CREATE INDEX idx_reverse_lookup_user ON tuple (store, object_type, relation, _user) LOCK = NONE;
diff --git a/assets/migrations/postgres/006_add_collate_index.sql b/assets/migrations/postgres/006_add_collate_index.sql
new file mode 100644
index 00000000..5de4bc66
--- /dev/null
+++ b/assets/migrations/postgres/006_add_collate_index.sql
@@ -0,0 +1,16 @@
+-- +goose NO TRANSACTION
+-- +goose Up
+CREATE INDEX CONCURRENTLY IF NOT EXISTS idx_user_lookup on tuple (
+    store,
+    _user,
+    relation,
+    object_type,
+    object_id collate "C"
+);
+
+DROP INDEX CONCURRENTLY IF EXISTS idx_reverse_lookup_user;
+
+-- +goose Down
+DROP INDEX CONCURRENTLY IF EXISTS idx_user_lookup;
+
+CREATE INDEX CONCURRENTLY IF NOT EXISTS idx_reverse_lookup_user on tuple (store, object_type, relation, _user);
diff --git a/pkg/storage/postgres/postgres.go b/pkg/storage/postgres/postgres.go
index 7a016239..26f454d0 100644
--- a/pkg/storage/postgres/postgres.go
+++ b/pkg/storage/postgres/postgres.go
@@ -446,7 +446,7 @@ func (s *Datastore) ReadStartingWithUser(
 			"object_type": filter.ObjectType,
 			"relation":    filter.Relation,
 			"_user":       targetUsersArg,
-		}).OrderBy("object_id")
+		}).OrderBy("object_id collate \"C\"")
 
 	if filter.ObjectIDs != nil && filter.ObjectIDs.Size() > 0 {
 		builder = builder.Where(sq.Eq{"object_id": filter.ObjectIDs.Values()})



Test patch:
diff --git a/pkg/storage/test/tuples.go b/pkg/storage/test/tuples.go
index 365679e8..91788e3f 100644
--- a/pkg/storage/test/tuples.go
+++ b/pkg/storage/test/tuples.go
@@ -4,6 +4,7 @@ import (
 	"context"
 	"errors"
 	"fmt"
+	"sort"
 	"sync"
 	"testing"
 	"time"
@@ -2002,6 +2003,51 @@ func ReadStartingWithUserTest(t *testing.T, datastore storage.OpenFGADatastore)
 		_, objectID := tuple.SplitObject(tuples[0].GetObject())
 		require.Equal(t, "doc1", objectID)
 	})
+	t.Run("assert_bytewise_ordering_of_tuples", func(t *testing.T) {
+		storeID := ulid.Make().String()
+
+		var tupleInReverseOrder = []*openfgav1.TupleKey{
+			tuple.NewTupleKey("document:doc7", "viewer", "user:bob"),
+			tuple.NewTupleKey("document:doc6", "viewer", "user:bob"),
+			tuple.NewTupleKey("document:doc_3", "viewer", "user:bob"),
+			tuple.NewTupleKey("document:Apt", "viewer", "user:bob"),
+			tuple.NewTupleKey("document:doc-3", "viewer", "user:bob"),
+			tuple.NewTupleKey("document:alt", "viewer", "user:bob"),
+		}
+
+		err := datastore.Write(ctx, storeID, nil, tupleInReverseOrder)
+		require.NoError(t, err)
+
+		tupleIterator, err := datastore.ReadStartingWithUser(
+			ctx,
+			storeID,
+			storage.ReadStartingWithUserFilter{
+				ObjectType: "document",
+				Relation:   "viewer",
+				UserFilter: []*openfgav1.ObjectRelation{
+					{
+						Object: "user:bob",
+					},
+				},
+			},
+			storage.ReadStartingWithUserOptions{
+				WithResultsSortedAscending: true,
+			},
+		)
+		require.NoError(t, err)
+
+		tuples := iterateThroughAllTuples(t, tupleIterator)
+		var actualObjectIDs []string
+		for _, item := range tuples {
+			_, objectID := tuple.SplitObject(item.GetObject())
+			actualObjectIDs = append(actualObjectIDs, objectID)
+		}
+
+		result := []string{"Apt", "alt", "doc-3", "doc_3", "doc6", "doc7"}
+		sort.Strings(result)
+
+		require.Equal(t, result, actualObjectIDs)
+	})
 	t.Run("enforce_order_of_tuples", func(t *testing.T) {
 		storeID := ulid.Make().String()