[kv] Support ordered index range reads #5100

Search before asking

• I searched existing issues for ordered key encoding and memcomparable encoding and found no matching request.

Motivation

Applications such as Flink window processing need rows matching equality predicates on grouping fields and a range on another field. Reading the entire equality prefix and filtering afterward can read substantially more data than the requested window. Applications also need to consume those rows in forward or reverse index order.

Provide one logical query shape for primary-key and secondary indexes, preferring a usable primary-key path before a usable secondary-index path. Support asynchronous lookup returning all matching rows and paginated scan with an optional row limit.

Solution

Use schema-bound, prefix-preserving ordered key encoding, selected by the immutable creation-time table.kv.ordered-key.enabled property. Keep this property independent of the KV format version and preserve bucket-key encoding and routing.

Represent logical bounds with a generic Range<T>. Configure equality columns and the immediately following range column on Lookup, then supply values and bounds per invocation. Configure equality values and bounds on Scan before creating a scanner. Capture input values before returning control to callers.

Share ReadDirection.FORWARD and ReadDirection.REVERSE across both interfaces. Ordered single-bucket reads default to forward index order. Reverse traversal reverses every remaining index field, including the primary-key suffix. Explicit direction requires ordered keys. Apply scan limits in traversal order, while lookup returns every matching row.

A scan fixes its KV snapshot and direction across batches. Lookup uses a request-local fixed iterator view and preserves independent query bounds and directions within RPC batches. Confine explicit ordered scans to one index bucket and reject unsupported paths before opening scanners.

The first implementation executes primary-key prefixes containing all required bucket fields and partition equalities. Secondary-index execution can use the same logical conditions and direction contract. It must preserve candidate order through any primary-key fetches.

Anything else?

Compacted key bytes do not generally follow logical field order. Order-preserving encoding is required to translate logical bounds into RocksDB seek bounds. Existing tables require a data rewrite to adopt a different key encoding. Upgrade all participating clients and servers before enabling ordered keys.

The encoding design draws on the TiDB codec and TiKV byte encoding.

Willingness to contribute

• I'm willing to submit a PR!