Repository navigation
Commit 132234d
perf: read NOT NULL tuple elements of a multi-column NOT IN as scope keys (apache#26214)
## Which issue does this PR close?
- Closes apache#26088.
## Rationale for this change
A multi-column `(a, b) NOT IN (SELECT x, y ...)` plans as a null-aware
hash join that decides UNKNOWN per build row. Without correlation keys,
every row with a NULL in any tuple element is paired with every row on
the other side, so the NULL path costs O(rows x NULL-valued rows).
A tuple element that cannot be NULL in scope on either side never makes
the tuple comparison UNKNOWN: against a definite value it is either
equal, which leaves the other elements to decide, or a definite
mismatch, which makes the comparison FALSE. It only selects which rows a
NULL in another element is compared with, which is exactly what a
correlation scope key does. For example, with `b` and `y` NOT NULL, a
NULL `a` only needs to be compared with the subquery rows whose `y`
equals its `b`.
## What changes are included in this PR?
- **Decorrelation** (`build_join`): for a null-aware tuple, the elements
are partitioned by `may_be_null_in_scope`, keeping their order within
each group. The elements that can be NULL come first and are the `NOT
IN` value keys (`null_aware_value_keys` counts only them); the others
follow as scope keys, before any correlation keys. The "value keys
first" layout is unchanged, so the hash join already narrows the NULL
candidate pairs through its scope hash map.
- All elements NOT NULL: the join is not null-aware, as before.
- Exactly one nullable element: `V = 1`, a scalar `NOT IN` on that
element correlated by the others.
- `LeftMark` (projection / `OR`) is reordered the same way and stays
three-valued exact.
- A NOT NULL element that is not a hashable equi-join key now stays in
the join filter like any correlation instead of being rejected. A
nullable one is still rejected.
- An element of the `Null`, dictionary, run-end encoded or union type,
or one that reads a column of such a type (e.g. under a coercion cast),
always stays a value key: an array of these types can hold a NULL
without a null bit, so its field's nullability does not rule out a NULL.
A run-end encoded element is therefore still rejected, as before.
- **Hash join** (`not_in.rs`): the hash table over the build rows' scope
keys is now built on the first probe row with a NULL value key, instead
of with the build side. Only such rows look it up, so a probe side
without NULLs no longer pays for a second hash table over the build
side. Since this PR sends more multi-column `NOT IN`s through the
scope-key path, this keeps the no-NULL case (Q10) at the cost of `main`.
- A cross product with marks on the build rows fills chunks of a batch
with unmarked build rows. It keeps the first batch of probe rows for all
chunks and produces the rest again, from the first of them, only for a
chunk that those leave with unmarked rows, rather than collecting every
build row index or every probe index first.
- If the memory pool declines either scope map (the lazy one over all
build rows, or the one over the NULL-valued build rows), the join pairs
those rows with every row on the other side and checks scope equality
per pair, as the all-value-key layout does, instead of failing the
query. A declined lazy scope map is not cached: the next probe batch
with a NULL value key tries to reserve it again.
- When the sampled estimate rejects pairing by hash groups, the per-row
lookups now stop once they waste as many matches again; the remaining
rows are then sorted by hash and paired by group. This covers a hot
scope value among rare ones, which the estimate alone misses.
- A volatile element is never made a scope key by a filter proof:
`key_may_be_null_in_scope` returns true for a volatile key. This also
fixes the scalar `NOT IN` with a volatile expression, which uses the
same check.
- Docs: `Join::null_aware_value_keys`,
`HashJoinExec::null_aware_value_keys` and the 56.0.0 upgrade guide
describe the new key layout.
- The Q11 / Q12 comments of the `null_aware_join` benchmark now describe
the scope-key path: their `z` column (`value % 1000`) is NOT NULL. A new
Q13 covers a low-cardinality scope key: `(o.id_n50, o.k) NOT IN (...)`
with a NOT NULL `k` of 16 distinct values. A new Q14 covers a hot scope
value: `hk` holds one value for 3/4 of the rows and rare values for the
rest.
## What is the testing strategy for this PR?
- `null_aware_anti_join.slt`: EXPLAIN plans for the reordering, with a
correlation, with two nullable elements and one NOT NULL element, a
constant element, NOT NULL on the outer side only (not reordered), a
mark join, a nullable element made a scope key by a correlated filter
that rejects NULL, and a dictionary under a coercion cast on either side
(stays a value key).
- `null_aware_multi_column.slt` (batch size matrix): results with NOT
NULL elements for `LeftAnti` and `LeftMark`, correlated subqueries, two
nullable elements and a scope key, a constant element, a run-end encoded
element (rejected), and a nullable element made a scope key by a
correlated filter that rejects NULL (NULL scope keys reach the join).
- `null_aware_join_fuzz.rs`: NOT NULL columns on both sides and seven
mixed shapes, compared with the `NOT EXISTS ... IS NOT FALSE` reference.
Placing the NOT NULL elements first fails this fuzz on its first seed.
- `hash_join/exec.rs`: a unit test that the scope map is only built (and
charged to `build_mem_used`) when the probe side has a NULL value key
and that the join falls back when the memory pool declines it, a test of
the same fallback for the scope map over the NULL-valued build rows, and
a test with more NULL-valued probe rows in one batch than the batch
size, whose rows past the first batch decide build rows.
- `not_in.rs`: `hot_scope_among_rare_ones_is_grouped` bounds the matches
walked for a hot scope value among rare ones, for marks on both sides,
and `declined_scope_map_is_built_once_memory_is_free` checks that a
declined scope map is built once the pool has room.
- `decorrelate_predicate_subquery.rs`: a volatile key with a
NULL-rejecting correlation stays null-aware.
- `core/tests/sql/joins.rs`: dictionary and `Null` elements under
inferred non-nullable fields keep the tuple result UNKNOWN.
- `not_in.rs`: `cross_product_chunks_the_build_rows` bounds the build
rows held at once and counts the walks of the probe rows and the rows
they read, including when exactly a batch of probe rows leaves a chunk
unmarked, and `cross_product_fills_chunks_with_unmarked_build_rows`
bounds the pairs when few build rows are left unmarked.
- `roundtrip_logical_plan.rs`: the existing multi-column case had only
NOT NULL `VALUES` columns for `b`/`y`, so its `b` now holds a NULL and
the case keeps covering two value keys.
Benchmark `null_aware_join` against `main` (criterion mean, average of
alternating runs):
| NAJ_ROWS | Q10 (no NULL) | Q11 (1% NULL in subquery) | Q12 (1% NULL in
outer) | Q13 (16-value scope key) |
|---|---|---|---|---|
| 10000 | 0.32 ms -> 0.34 ms | 3.31 ms -> 0.35 ms | 0.48 ms -> 0.36 ms |
78.8 ms -> 0.80 ms |
| 20000 | 0.38 ms -> 0.38 ms | 6.10 ms -> 0.43 ms | 0.56 ms -> 0.44 ms |
162 ms -> 0.99 ms |
Q01 to Q09 are unchanged. Q14 (10k rows, `ci` profile) takes 23 ms,
against 899 ms with the grouping rule before the hot-scope fix and 709
ms with both elements as value keys. Q13 depends on apache#25679: before it,
the same shape took 20.5 / 41.3 ms on this branch.
## Are there any user-facing changes?
Faster multi-column `NOT IN` when some tuple elements are NOT NULL.
Plans show fewer `NOT IN` value keys (`null_aware(value_keys=N)`) for
such tuples. No API change.
---------
Co-authored-by: Isaac <[email protected]>1 parent 2f4d087 commit 132234d
17 files changed
Lines changed: 1505 additions & 186 deletions
File tree
- benchmarks/sql_benchmarks/null_aware_join
- benchmarks
- init
- datafusion
- core/tests
- fuzz_cases
- sql
- expr/src/logical_plan
- optimizer/src
- physical-plan/src/joins
- hash_join
- proto/tests/cases
- sqllogictest/test_files
- docs/source/library-user-guide/upgrading
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
25 | 25 | | |
26 | 26 | | |
27 | 27 | | |
28 | | - | |
29 | | - | |
30 | | - | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
31 | 32 | | |
32 | 33 | | |
33 | 34 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
26 | 26 | | |
27 | 27 | | |
28 | 28 | | |
29 | | - | |
30 | | - | |
31 | | - | |
32 | | - | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
33 | 33 | | |
34 | 34 | | |
35 | 35 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
8 | 8 | | |
9 | 9 | | |
10 | 10 | | |
| 11 | + | |
11 | 12 | | |
12 | 13 | | |
13 | 14 | | |
14 | 15 | | |
15 | 16 | | |
16 | 17 | | |
17 | | - | |
| 18 | + | |
18 | 19 | | |
19 | 20 | | |
20 | 21 | | |
| |||
23 | 24 | | |
24 | 25 | | |
25 | 26 | | |
26 | | - | |
| 27 | + | |
| 28 | + | |
27 | 29 | | |
28 | 30 | | |
29 | 31 | | |
| |||
33 | 35 | | |
34 | 36 | | |
35 | 37 | | |
36 | | - | |
| 38 | + | |
| 39 | + | |
37 | 40 | | |
38 | 41 | | |
39 | 42 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
8 | 8 | | |
9 | 9 | | |
10 | 10 | | |
11 | | - | |
| 11 | + | |
12 | 12 | | |
13 | 13 | | |
14 | 14 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
8 | 8 | | |
9 | 9 | | |
10 | 10 | | |
| 11 | + | |
| 12 | + | |
11 | 13 | | |
12 | 14 | | |
13 | 15 | | |
| |||
31 | 33 | | |
32 | 34 | | |
33 | 35 | | |
34 | | - | |
| 36 | + | |
35 | 37 | | |
36 | 38 | | |
37 | 39 | | |
38 | | - | |
| 40 | + | |
| 41 | + | |
39 | 42 | | |
40 | 43 | | |
41 | 44 | | |
| |||
129 | 132 | | |
130 | 133 | | |
131 | 134 | | |
| 135 | + | |
| 136 | + | |
| 137 | + | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
| 145 | + | |
| 146 | + | |
| 147 | + | |
| 148 | + | |
| 149 | + | |
| 150 | + | |
132 | 151 | | |
133 | 152 | | |
134 | 153 | | |
| |||
166 | 185 | | |
167 | 186 | | |
168 | 187 | | |
169 | | - | |
170 | | - | |
171 | | - | |
172 | | - | |
| 188 | + | |
| 189 | + | |
| 190 | + | |
| 191 | + | |
| 192 | + | |
| 193 | + | |
| 194 | + | |
| 195 | + | |
| 196 | + | |
| 197 | + | |
| 198 | + | |
| 199 | + | |
| 200 | + | |
| 201 | + | |
173 | 202 | | |
174 | 203 | | |
175 | 204 | | |
176 | | - | |
| 205 | + | |
177 | 206 | | |
178 | 207 | | |
179 | 208 | | |
| |||
183 | 212 | | |
184 | 213 | | |
185 | 214 | | |
186 | | - | |
| 215 | + | |
187 | 216 | | |
188 | 217 | | |
189 | 218 | | |
190 | 219 | | |
191 | 220 | | |
192 | | - | |
| 221 | + | |
193 | 222 | | |
194 | 223 | | |
195 | 224 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
688 | 688 | | |
689 | 689 | | |
690 | 690 | | |
| 691 | + | |
| 692 | + | |
| 693 | + | |
| 694 | + | |
| 695 | + | |
| 696 | + | |
| 697 | + | |
| 698 | + | |
| 699 | + | |
| 700 | + | |
| 701 | + | |
| 702 | + | |
| 703 | + | |
| 704 | + | |
| 705 | + | |
| 706 | + | |
| 707 | + | |
| 708 | + | |
| 709 | + | |
| 710 | + | |
| 711 | + | |
| 712 | + | |
| 713 | + | |
| 714 | + | |
| 715 | + | |
| 716 | + | |
| 717 | + | |
| 718 | + | |
| 719 | + | |
| 720 | + | |
| 721 | + | |
| 722 | + | |
| 723 | + | |
| 724 | + | |
| 725 | + | |
| 726 | + | |
| 727 | + | |
| 728 | + | |
| 729 | + | |
| 730 | + | |
| 731 | + | |
| 732 | + | |
| 733 | + | |
| 734 | + | |
| 735 | + | |
| 736 | + | |
| 737 | + | |
| 738 | + | |
| 739 | + | |
| 740 | + | |
| 741 | + | |
| 742 | + | |
| 743 | + | |
| 744 | + | |
| 745 | + | |
| 746 | + | |
| 747 | + | |
| 748 | + | |
| 749 | + | |
| 750 | + | |
| 751 | + | |
| 752 | + | |
| 753 | + | |
| 754 | + | |
| 755 | + | |
| 756 | + | |
| 757 | + | |
| 758 | + | |
| 759 | + | |
| 760 | + | |
| 761 | + | |
| 762 | + | |
| 763 | + | |
| 764 | + | |
| 765 | + | |
| 766 | + | |
| 767 | + | |
| 768 | + | |
| 769 | + | |
| 770 | + | |
| 771 | + | |
| 772 | + | |
| 773 | + | |
| 774 | + | |
| 775 | + | |
| 776 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
4644 | 4644 | | |
4645 | 4645 | | |
4646 | 4646 | | |
4647 | | - | |
| 4647 | + | |
| 4648 | + | |
| 4649 | + | |
4648 | 4650 | | |
4649 | 4651 | | |
4650 | 4652 | | |
| |||
0 commit comments