CuteChuanChuan opened a new issue, #25332:
URL: https://github.com/apache/datafusion/issues/25332
### 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 at `row`, from the head of its chain
- `(row, Some(next))` with `next != 0`: resume in the middle of `row`'s chain
- `(row, Some(0))`: `row`'s chain is finished (`0` is 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_batch` uses
`state.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 (given `limit > 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))` as `row + 1`, but the
unique-key fast paths (`join_hash_map.rs`, `array_map.rs`) read only
`offset.0`, so they would treat it as `row`. They are correct only because they
never produce `Some`.
- **Unnamed positional fields**, e.g. `offset.0` in `join_hash_map.rs` and
`array_map.rs`.
### Describe the solution you'd like
Replace the tuple with an enum, for example:
```rust
enum ProbeOffset {
Start,
AtRow { row: usize },
MidChain { row: usize, next: u64 },
}
```
- `(row, Some(0))` becomes `AtRow { row: row + 1 }`, so each position has a
single encoding.
- Keep the outer `Option` for "batch exhausted" rather than adding a `Done`
variant, since `Done` is never a valid starting offset.
- `state.offset == (0, None)` becomes a check for `ProbeOffset::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 `MapOffset`
describing 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 becomes `AtRow { row: 0
}`. This avoids having both `Start` and `AtRow { 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_offset` is part of `JoinHashMapType`,
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 as `ArrayMap` and `traverse_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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
