TopNRowNumber In-Memory Rank Ordering and Partition Stream Parity in Meta Velox

Engineering objective

System challenge

TopNRowNumber's in-memory max-heap was drained directly into output buffers, emitting retained rows in descending rank order within each partition. Conversely, the spilled execution path and WindowNode emitted ascending per-partition rank order, creating execution-path-dependent behavior and subtle downstream query inconsistencies.

Constraints

Working within real limits

• ✕Preserve zero-copy vectorized batch emissions where possible
• ✕Ensure row_number, rank, and dense_rank maintain exact monotonic progression
• ✕Maintain the verified that no global ordering across partitions is guaranteed
• ✕Pass Velox native operator regression test battery with ASAN/TSAN verification

Approach

How it was built

1. 01

   Reordered retained in-memory partition rows into ascending per-partition rank sequence before vector batch projection.

2. 02

   Synchronized rank, dense_rank, and row_number calculation across in-memory and spilled operators.

3. 03

   Authored deterministic exact-order regression tests contrasting WindowNode vs TopNRowNumber across in-memory and spilled execution paths.

Technical validation

Implementation evidence

Observable engineering evidence. Discipline: MERGED UPSTREAM

Public evidence

Review the upstream contribution

Outcome

What was delivered

• Unified execution behavior between in-memory and spilled TopNRowNumber execution

• Guaranteed ascending per-partition rank ordering across all execution modalities

• Merged into upstream facebookincubator/velox core repository (merge commit 8612db5)

Technologies

Stack and tools

Previous and Next Engineering Systems