Skip to main content

Module join_executor

radixdb_executor

Module join_executor 

Source
Expand description

Modern streaming JOIN executor using Volcano-style operators.

This module provides high-performance JOIN execution with:

  • Hash Join: Build smaller side, probe larger side with O(N+M) complexity
  • Merge Join: O(N+M) when inputs are pre-sorted on join keys
  • Nested Loop: O(N*M) fallback for non-equality joins or small tables
  • Early Termination: LIMIT stops execution immediately
  • Residual Filters: Non-equality conditions applied during streaming

§Architecture

JoinRequest
    │
    ▼
┌─────────────────────────────────┐
│ JoinExecutor::execute()         │
│  1. Analyze join condition      │
│  2. Select optimal algorithm    │
│  3. Execute with streaming      │
│  4. Early terminate at LIMIT    │
└─────────────────────────────────┘
    │
    ▼
JoinResult { rows, columns }

§Design Decisions & Tradeoffs

§Hybrid Execution: Streaming vs Parallel

This executor uses a hybrid approach that dynamically chooses between Volcano-style streaming and parallel bulk processing based on query characteristics:

§Streaming Volcano Path (default for small datasets or small LIMIT)

  • When: Build side < 10,000 rows OR LIMIT ≤ 1,000
  • Benefits:
    • O(1) memory for probe side (streaming, not materialized)
    • Early termination: LIMIT 10 stops after 10 rows
    • Low latency to first row (important for interactive queries)
    • Composable operators (Filter → Join → Project → Limit)

§Parallel Hash Join Path (for large analytical queries)

  • When: Build side ≥ 10,000 rows AND (no LIMIT or LIMIT > 1,000)
  • Benefits:
    • Parallel hash build using a pre-admitted fixed-width atomic table
    • Parallel probe with Rayon work-stealing
    • 2-4x speedup on multi-core systems for large joins
    • Atomic tracking for OUTER join unmatched rows

§Why Not Always Parallel?

Parallel execution has overhead (task scheduling, synchronization). For:

  • Small datasets: overhead exceeds benefit
  • Small LIMIT: streaming stops early; parallel computes full result then truncates

§Merge Join Boundary

The binary entry point currently receives materialized relation batches, but MergeJoinOperator itself consumes its certified ordered inputs one row at a time. Only matching duplicate-key groups are blocking state, and their owner is bounded before execution:

left ordered operator  ┐
                       ├→ bounded streaming MergeJoinOperator
right ordered operator ┘

§Bloom Filter Optimization

Bloom filters can accelerate hash joins by filtering probe rows that definitely won’t match before touching the hash table. This is particularly effective for:

  • High selectivity joins (few matches relative to probe size)
  • Multi-way joins (filter cascades through the plan)

Query planning can build a runtime bloom filter and wrap the probe input in BloomFilterOperator before handing it to the streaming join executor.

Structs§

JoinAnalysis
Analysis of a join operation for algorithm selection.
JoinExecutor
Modern streaming join executor.
JoinInputOrderings
Physical ordering certificates for both sides of one JOIN edge.
JoinRequest
Request to execute a join operation.
JoinResult
Result of a streaming join execution.
RuntimeJoinDecision
Runtime join decision produced by the planner and consumed by physical JOIN.
StreamingJoinRequest
Request to execute a streaming hash join.

Enums§

JoinRows
RuntimeJoinAlgorithm
Runtime join algorithm selection.

Type Aliases§

StreamingJoinResult