apache / apache/pinot

Lookup join: fold constants out of the post-lookup filter, and accept join conditions a filter can satisfy

Open
#19,229 1 comment 0 reactions 0 assignees View on GitHub
multi-stage query
Dominant language
Java
Stars
6.1k
Forks
1.5k
Avg merge
2d 3h
Merged PRs (30d)
195

Description

Two follow-ups raised by @timothy-e while reviewing #19210, deferred so that the bug fix stayed reviewable. They are
independent of each other and can be split if that helps.

Background: #19210 makes `LookupJoinOperator` compile a key plan that maps every dimension table primary key column to
its value source. Pass 1 fills a position from a join key. Pass 2 fills a position that pass 1 left open from a
`dim_column = constant` condition.

## 1. Do not evaluate a condition after the lookup when the key already enforces it

> Could we improve perf by following up with a change that allows us to apply both filters during the hashmap lookup,
> to avoid materializing rows just to filter them out later?

One clarification on the premise: no row is materialized and then discarded today. `JoinedRowView` is a lazy view over
the left and right rows, and `toArray` runs only after the filters pass. The waste is the evaluator call and, in one
case, the map probe itself.

There are two distinct cases, and they want different treatments.

**A constant that pass 2 folded into the key.** The condition is then guaranteed by the lookup, so evaluating it again
per row can only ever return true. `_nonEquiEvaluators` is built from every entry of `JoinNode.getNonEquiConditions()`
before the key plan is compiled, and nothing removes the folded ones. This hits the headline query from #19188, where
`dim.currency = 'gbp'` is the only non-equi condition and is fully consumed by pass 2, so the `isEmpty()` fast path is
never taken. Fix: have `compileKeyPlan` report which condition indices it consumed and skip those when building the
evaluators.

**A constant on a position that a join key already filled**, for example
`ON dim.currency = fact.currency AND dim.rate_start_date = fact.rate_start_date AND dim.currency = 'gbp'`. Here the
condition is not redundant. It is the only thing enforcing the constant, and #19210 deliberately keeps it as a filter
so that the join does not silently widen. It can still be applied earlier: that key position reads `leftRow[i]`, so
`dim.currency = 'gbp'` is equivalent to `leftRow[i] = 'gbp'`, which can be checked before the probe rather than after
it. That skips the map lookup for rows that cannot match.

Better still, the planner could infer `fact.currency = 'gbp'` and push it into the fact table scan.
`PinotJoinPushTransitivePredicatesRule` does push left inferred predicates, and only blocks the right side for lookup
joins, but it does not fire for this shape today. A test in #19210 relies on that: the `usd` fact row still reaches the
join, which is what lets the test tell a correct implementation apart from one that lets the constant overwrite the
join key. Worth understanding why the inference does not happen before choosing between the planner fix and the
runtime one.

## 2. Accept join conditions that a post-lookup filter can satisfy

> Both of these seem like they could be added as filters after the join, which would increase our SQL compatibility?

#19210 rejects two shapes that it could instead support:

- **A join key on a dimension column outside the primary key**, for example `AND dim.rate = fact.amount`. The row
returned by the lookup already carries that column, because the right side projects the whole dimension schema, so
the condition can run after the lookup as
`EQUALS(InputRef(leftColumnId), InputRef(leftColumnSize + rightColumnId))` on the existing `TransformOperand` path.
- **More than one join key on the same primary key column**, for example `ON dim.c = fact.a AND dim.c = fact.b`. The
first fills the key position and the rest become the same kind of post-lookup filter.

Both are rejected today only because dropping the surplus condition would silently return rows that do not match it,
which is worse than an error. A filter is better than either.

Left join semantics come out right without extra work: a row that finds a primary key match but fails the extra filter
falls through to the existing null padding branch.

Two things to handle:

- Semi and anti joins project the left columns only, so their result schema cannot address a dimension column. #19210
rejects a non-equi condition for those two join types for this reason. Either keep rejecting these shapes for semi
and anti joins, or build their evaluators against a left plus right schema.
- Calcite records `filterNulls` per join key, but `JoinNode` does not carry it, so a synthesized condition would use
`=` semantics. That matches what `HashJoinOperator` already does.

A primary key column that nothing determines must stay an error. There is no point lookup to perform, so the only
alternatives are an error or a planner level fallback to a hash join.

## Not included

Two other points from the same review are already addressed in #19210: the constant is no longer converted in the
operator, since the planner coerces the operands of a comparison and the operator now checks that, and the operator
test now names its column ids. The `BYTES` primary key question became #19228, because it is a dimension table
bug rather than a lookup join one.

Contributor guide

Open the contributing guide

Research direction

Start by reading LookupJoinOperator, compileKeyPlan, JoinNode.getNonEquiConditions(), and PinotJoinPushTransitivePredicatesRule, then inspect the tests added or referenced by #19210. Done means consumed conditions are not re-evaluated, eligible conditions are checked before or after lookup without widening results, and primary-key and semi/anti join constraints remain correct.

Written by the indexing model from the issue text.

Assessment

Tech stack
java, sql
Domain
databases
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.