Skip to content

Replace the MapOffset tuple with an enum #25332

Description

@CuteChuanChuan

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:

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.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions