Skip to content

Spillable broadcast/shuffled hash join #721

@richox

Description

@richox

Is your feature request related to a problem? Please describe.
currently hash joins use a monolithic in-memory hash table for joining, which may cause oom in the case where offheap memory is small.

Describe the solution you'd like
add a row/memory limit for building hash table. when exceeded, turn into a spill-merge method:

  1. build side data is shuffled into N buckets. (say N=1024)
  2. build buckets into separated hash tables, small buckets can be coalesced.
  3. shuffle probe side into the same N partitions.
  4. read each partition, join with the corresponding hash table.

Describe alternatives you've considered
this solves oom problem in most cases, however when there are data skewing, the shuffle does not work, we may fallback to sort-based joining in such situation.

Additional context
Add any other context or screenshots about the feature request here.

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions