Module sqljoin 

Join strategy: nested loop (the reference) and hash (the fast path).

Division of responsibility

The evaluator in crate::sqlselect decides what a query MEANS. This module decides only HOW the join is executed. Those are kept apart deliberately: an optimisation that can change an answer is not an optimisation, it is a bug with better throughput.

Why the hash table is not allowed to decide anything

A hash join works by partitioning rows into buckets, which assumes equality is an equivalence relation. In this engine it is NOT, because comparison is dynamically typed:

  1   =  '1'     TRUE    (number vs numeric string -> compared numerically)
  1   =  '1.0'   TRUE    (same)
 '1'  =  '1.0'   FALSE   (string vs string -> compared exactly)

Equality is therefore not transitive, and no bucketing scheme can reproduce nested-loop results by bucketing alone. So this module does not try.

hkey maps a value to a bucket, and the ONLY property it must have is:

if a = b evaluates to TRUE, then hkey(a) == hkey(b)

That is, no FALSE NEGATIVES. Collisions are harmless and expected — every candidate pair that survives the bucket lookup is then re-checked against the complete, unmodified ON expression by the evaluator itself. The hash table shrinks the candidate set; the evaluator still decides the answer.

That is what makes equivalence with the nested loop provable rather than merely tested: both paths end up asking the same question of the same expression, and the fast path only skips pairs that the invariant above guarantees would have answered “no”.

The asymmetry is the whole safety argument, and it was checked by mutation rather than assumed. Breaking the invariant — bucketing numeric strings as text, so 1 = '1' is no longer found — fails seven differential tests. Adding false POSITIVES, by giving NULL an ordinary bucket, changes no answer at all. Only one direction can be wrong, which is why this module is allowed to be approximate and the evaluator is not.

Row order

Buckets hold right-hand row INDICES in ascending order, and probing walks left rows in order. A nested loop over the same inputs emits pairs in exactly that order too, so the two strategies agree row-for-row — not just as sets. Differential tests can compare ordered lists, which is a far sharper assertion than comparing sorted ones.

Structs

HashSide

Right-hand rows indexed by their key bucket.

JoinChoice

What actually ran, per join, for EXPLAIN and for benchmark honesty.

Enums

HKey

A bucket identity for one value.

JoinExec

Which execution strategy to use for joins.

Strategy

Constants

AUTO_HASH_MIN_PAIRS

Below this many candidate pairs, a nested loop is simply cheaper — building a hash table costs an allocation per distinct key and a clone of every right row’s key values, which a handful of comparisons does not repay.

Functions

choose

The strategy to use, given a plan and the actual relation sizes.

hash_keys

The equality key pairs a hash join can use, as (left expr, right expr).

hkey

The bucket a value belongs to, or None when the value can never match.