Repository navigation
Labels
enhancementNew feature or requestNew feature or request
Description
Is your feature request related to a problem or challenge?
Working on #25272 (issue: #25077 ) raised a question about MapOffset, the resume point of chunked hash map lookups (JoinHashMapType::get_matched_indices_with_limit_offset).
MapOffset is (usize, Option<u64>) and encodes several distinct states by convention:
(0, None): nothing of this probe batch has been consumed yet(row, None): resume atrow, from the head of its chain(row, Some(next))withnext != 0: resume in the middle ofrow's chain(row, Some(0)):row's chain is finished (0is the end-of-chain sentinel), so this is the same position as(row + 1, None)
plus the outer None returned when the batch is exhausted.
This causes a few problems:
- Magic-value comparisons.
HashJoinStream::process_probe_batchusesstate.offset == (0, None)to detect the first chunk of a probe batch. That relies on an invariant that isn't documented: a returned offset is never(0, None), because every path returning(row, None)has already moved past at least one probe row (givenlimit > 0), while resuming mid-chain on row 0 yields(0, Some(_)). - Two encodings of the same position, whose meaning depends on the reader. The chain traversal decodes
(row, Some(0))asrow + 1, but the unique-key fast paths (join_hash_map.rs,array_map.rs) read onlyoffset.0, so they would treat it asrow. They are correct only because they never produceSome. - Unnamed positional fields, e.g.
offset.0injoin_hash_map.rsandarray_map.rs.
Describe the solution you'd like
Replace the tuple with an enum, for example:
enum ProbeOffset {
Start,
AtRow { row: usize },
MidChain { row: usize, next: u64 },
}(row, Some(0))becomesAtRow { row: row + 1 }, so each position has a single encoding.- Keep the outer
Optionfor "batch exhausted" rather than adding aDonevariant, sinceDoneis never a valid starting offset. state.offset == (0, None)becomes a check forProbeOffset::Start. This makes the invariant explicit, although it is still upheld by convention rather than by the type.- If another resume point is added later, the compiler forces every call site to handle it.
Describe alternatives you've considered
- Keep the tuple and document it. Add a doc comment on
MapOffsetdescribing the states and the(0, None)invariant. No API change, but correctness still relies on convention, and the two encodings of the same position remain. - An enum without
Start. The first-chunk check becomesAtRow { row: 0 }. This avoids having bothStartandAtRow { row: 0 }describe the same position, at the cost of keeping a value comparison.
Additional context
Costs I can see:
get_matched_indices_with_limit_offsetis part ofJoinHashMapType, which is public (although documented as mainly intended for internal use), so this would be an API change.- It touches every implementation (
JoinHashMapU32,JoinHashMapU64,PruningJoinHashMap) as well asArrayMapandtraverse_chain. - Runtime cost should be nil: the offset is built once per lookup call rather than per row, and both representations are 24 bytes on 64-bit targets.
I'm happy to work on this if maintainers think it is worth the API change.
Metadata
Metadata
Assignees
Labels
enhancementNew feature or requestNew feature or request
Activity
jayzhan211 commentedon Sep 16, 2026
I think we don't need
Start🤔 , other looks good to meCuteChuanChuan commentedon Sep 16, 2026
Hi @jayzhan211 , thanks for taking a look!
Agreed.
StartandAtRow { row: 0 }would describe the same position, so keepingStartbrings back the duplicate encoding this change is meant to remove. I'll drop it and go with two variants:The first-chunk check then becomes
offset == ProbeOffset::AtRow { row: 0 }, and I'll document on the type that a returned offset is neverAtRow { row: 0 }, sinceHashJoinStream::process_probe_batchrelies on that.I'll open a PR for this. Thank you!
CuteChuanChuan commentedon Sep 16, 2026
take
refactor: replace MapOffset tuple with ProbeOffset enum (apache#26203)