Keyset paging drops rows when sorting by a nullable column #766

Context

Paging a list ordered by a nullable column silently loses every row whose sort
value is NULL. It affects Postgres, SQLite and Spanner.

Two independent defects combine.

The cursor never carries a NULL. Schema bindings for nullable columns flatten
nil to a zero value, so session.user_id reaches the cursor as "" in all
three dialects. The null-aware compare helper only triggers on a Go nil, ""
fails that test, and the keyset predicate is compiled as an ordinary comparison.
A comparison against NULL is NULL, never true, so NULL rows are never returned.
This holds for the single-column form and for the row-value form used when a
tiebreaker column is present.

ORDER BY never states where NULLs sit. The null-aware compare helper documents
an assumption of ASC NULLS FIRST / DESC NULLS LAST and encodes it in the
predicates it emits. No dialect's ORDER BY compiler emits a NULLS clause, so
SQLite and Spanner satisfy the assumption by accident and Postgres contradicts
it. Fixing only the bindings would leave Postgres wrong in the other direction:
it would re-serve rows instead of dropping them.

Dialect NULL ordering decides how soon the row loss shows up, not whether it
happens. Postgres orders NULLs last on ASC and loses them as soon as one exists.
SQLite and Spanner order them first and lose them once the NULL block is wider
than one page.

Nullable bindings fall into three groups today.

• Flattened to a zero value, so rows are silently lost: session.user_id,
  user.lifecycle_owner_team_id, userpassword.verification_id and
  last_successful_check, usertotp, userrecoverycodes, userpasskey.
• Returning nil but coerced as a string, so the cursor fails to decode:
  json_schema.object_type. The string coercion has no nil branch and errors.
• Returning nil and coerced as a timestamp, which is correct:
  token.expires_at. The time coercion maps nil to nil deliberately. Note it
  returns a typed nil pointer, which only reads as a Go nil after the token
  round-trip through JSON. A string binding copying that shape without a
  matching nil branch in its coercion would still be broken.

Sessions are the first resource to want a nullable sort field, user_id, which
is nil until the session is associated with a user.

Where the bug is

Line links are pinned to b5b9b6e.

The cursor never carries a NULL. The session binding flattens a nil UserID
to "", so the null-aware compare helper never sees a Go nil
(postgres,
sqlite,
spanner).

domain.SessionFieldUserID: {SQLName: "s.user_id", Accessor: func(s *domain.Session) any {
	if s.UserID == nil {
		return ""
	}
	return *s.UserID
}, Coerce: database.CoerceString},

The user, userpassword, usertotp, userrecoverycodes and userpasskey
bindings listed above flatten the same way, to "" or time.Time{}.

A nil does not survive the coercion.
CoerceString
has no nil branch and errors, which is what breaks the bindings that already
return nil.
CoerceTime
has the shape to copy.

ORDER BY never states where NULLs sit. No dialect emits a NULLS clause:
postgres,
sqlite,
spanner.
The assumption they have to satisfy is stated in
null_aware.go.

A non-NULL cursor drops NULL rows too, when ordering descending. The
null-aware path is entered only when a cursor value is nil, via
HasNilValue,
called from
postgres,
sqlite and
spanner.
Every other cursor compiles to a plain
row-value
or
lexicographic
comparison. Under DESC NULLS LAST the NULL rows sort after a non-NULL cursor
value, and col < 'x' is NULL for them, so they are never returned.
writeNullSafeOrdered already emits
the right predicate,
(col < x OR col IS NULL), but nothing reaches it. Fixing the bindings does not
cover this, because here the cursor value is not NULL. The compiler has to know
the column is nullable, which the schema does not record today.

Reproduction

Failing tests are on the throwaway branch.
Each test pages a full list of sessions ordered by user_id, id with a page
size of two, and asserts every session comes back exactly once.

Postgres, with two anonymous sessions and two associated ones. Both anonymous
sessions are dropped on the first page, because Postgres orders NULLs last and
the cursor moves past them.

--- FAIL: TestListSessions_pagesAnonymousSessionsWhenSortingByUserID (0.01s)
    Error:      elements differ

                extra elements in list A:
                 "sess_01KZ99Z18F3WM97QYSAWRN5E23"
                 "sess_01KZ99Z18GKST7ZDW89WHTC4G0"

                listA (want, len=4):
                 "sess_01KZ99Z18F3WM97QYSAWRN5E23"
                 "sess_01KZ99Z18GKST7ZDW89WHTC4G0"
                 "sess_01KZ99Z18JBCDMK4Q92CDYJRFS"
                 "sess_01KZ99Z18KZC86GR97CDYT3ZJ2"

                listB (got, len=2):
                 "sess_01KZ99Z18JBCDMK4Q92CDYJRFS"
                 "sess_01KZ99Z18KZC86GR97CDYT3ZJ2"
    Messages:   every session must appear exactly once across all pages

SQLite and Spanner, with three anonymous sessions and a page size of two. They
order NULLs first, so the loss only shows once the NULL block spans a page
boundary and the cursor has to carry a NULL forward.

--- FAIL: TestListSessions_pagesMoreAnonymousSessionsThanFitOnAPage (0.00s)
    Error:      elements differ

                extra elements in list A:
                 "sess_01KZ99XCTTJ8CNTQ7EKRS46KN8"

                listA (want, len=3):
                 "sess_01KZ99XCTTJ8CNTQ7EKHD610CC"
                 "sess_01KZ99XCTTJ8CNTQ7EKKNHT77Z"
                 "sess_01KZ99XCTTJ8CNTQ7EKRS46KN8"

                listB (got, len=2):
                 "sess_01KZ99XCTTJ8CNTQ7EKHD610CC"
                 "sess_01KZ99XCTTJ8CNTQ7EKKNHT77Z"
    Messages:   every session must appear exactly once across all pages

Scope / Tasks

• Make a nil sort value reach the cursor as SQL NULL instead of a zero value,
  for every nullable binding listed above.
• Give string cursor values a nil branch so a NULL survives the token
  round-trip, as timestamps already do.
• State NULL ordering explicitly in the ORDER BY compiled by all three
  dialects, so they agree with each other and with what the null-aware compare
  helper assumes.
• Keep the null-aware compare helper and the ORDER BY it depends on consistent
  for both ascending and descending order.

Acceptance Criteria

• Paging a full list ordered by a nullable column returns every row exactly
  once on Postgres, SQLite and Spanner, including when the NULL rows span a
  page boundary.
• A nil sort value reaches the cursor as NULL rather than a zero value, and
  survives the token round-trip for string columns as well as timestamps.
• NULL rows order identically on all three dialects, matching what the
  null-aware compare helper assumes.
• These pass: internal/storage/v2/dialect/{postgres,sqlite,spanner}/session_pagination_test.go,
  taken from test/keyset-null-pagination.

Depends on

Sorting sessions by user_id is in the contract but cannot be implemented
correctly until this is fixed.

Resources

• ADR 027: cursor-based pagination