77 lines
2.3 KiB
Markdown
77 lines
2.3 KiB
Markdown
|
# TGK Ordering Enforcement
|
||
|
|
|
||
|
|
Status: Draft
|
||
|
|
Scope: Canonical ordering rules for TGK/STORE/1 and where to enforce them in adapters and query pipelines.
|
||
|
|
|
||
|
|
---
|
||
|
|
|
||
|
|
# 1. Purpose
|
||
|
|
|
||
|
|
TGK/STORE/1 defines a canonical deterministic ordering for all edge and neighbor query results. This document records the rule and the enforcement points so implementations do not drift.
|
||
|
|
|
||
|
|
---
|
||
|
|
|
||
|
|
# 2. Canonical Ordering Rules
|
||
|
|
|
||
|
|
## 2.1 Edge Ordering
|
||
|
|
|
||
|
|
All adjacency and scan results MUST be ordered by:
|
||
|
|
|
||
|
|
1. For each edge `(edge_ref, body)`, form:
|
||
|
|
|
||
|
|
`order_key(edge_ref) = hash_id_bytes || digest_bytes`
|
||
|
|
|
||
|
|
2. `hash_id_bytes` is `edge_ref.hash_id` encoded as big-endian `u16`.
|
||
|
|
3. `digest_bytes` is the raw `edge_ref.digest`.
|
||
|
|
4. Sort edges in ascending lexicographic order of `order_key(edge_ref)`.
|
||
|
|
|
||
|
|
This is the normative ordering defined by TGK/STORE/1 and is equivalent to sorting by canonical `ReferenceBytes`.
|
||
|
|
|
||
|
|
## 2.2 Neighbor Ordering
|
||
|
|
|
||
|
|
If `neighbors` is implemented, neighbor results MUST be ordered by:
|
||
|
|
|
||
|
|
1. For each node `n`, form:
|
||
|
|
|
||
|
|
`node_order_key(n) = hash_id_bytes || digest_bytes`
|
||
|
|
|
||
|
|
2. `hash_id_bytes` is `n.hash_id` encoded as big-endian `u16`.
|
||
|
|
3. `digest_bytes` is the raw `n.digest`.
|
||
|
|
4. Sort neighbors in ascending lexicographic order of `node_order_key(n)`.
|
||
|
|
|
||
|
|
---
|
||
|
|
|
||
|
|
# 3. Enforcement Points
|
||
|
|
|
||
|
|
Ordering MUST be enforced by TGK/STORE/1 logic, not by backend defaults.
|
||
|
|
|
||
|
|
Acceptable enforcement points:
|
||
|
|
|
||
|
|
1. Adapter layer (preferred): apply ordering before returning `GraphEdgeView` lists.
|
||
|
|
2. Canonical result transformation layer: a shared sorting function used by all adapters.
|
||
|
|
|
||
|
|
Disallowed enforcement:
|
||
|
|
|
||
|
|
1. Relying on JanusGraph traversal order.
|
||
|
|
2. Relying on Elasticsearch sort order.
|
||
|
|
3. Any backend-specific implicit ordering.
|
||
|
|
|
||
|
|
---
|
||
|
|
|
||
|
|
# 4. Test Requirements
|
||
|
|
|
||
|
|
Conformance tests MUST verify:
|
||
|
|
|
||
|
|
1. Adjacency results are ordered per the canonical `(hash_id, digest)` rule.
|
||
|
|
2. `scan_edges` results follow the same ordering per page.
|
||
|
|
3. `neighbors` results use the canonical node ordering if the operation is exposed.
|
||
|
|
4. Cross-backend equivalence: the same snapshot yields identical ordered lists.
|
||
|
|
|
||
|
|
---
|
||
|
|
|
||
|
|
# 5. Implementation Notes
|
||
|
|
|
||
|
|
1. Sorting uses the canonical `ReferenceBytes` ordering for `edge_ref` and `node` references.
|
||
|
|
2. Ordering is snapshot-relative; it must be stable for a fixed snapshot.
|
||
|
|
3. If ES is used for candidate retrieval, the authoritative layer must re-apply ordering.
|