Repository navigation
Commit 47794ff
authored
Improve planning speed: Fast path for
## Which issue does this close?
Complements apache#19792. Fits with the wide-`UnionExec` planning-cost work,
but originates from an InfluxDB issue.
## Rationale for this change
`union_schema` builds the output schema for `UnionExec` and
`InterleaveExec` by coercing field metadata and nullability across
**every** child. That merge is quadratic in the number of children: for
each output field it walks all inputs, and for each input it walks
*every other* input to union field-level metadata. For a union of `n`
children with `f` fields the construction cost is `O(n^2 * f)` (worse
when fields carry metadata).
For narrow unions this is insignificant. It matters when a plan fans a
single source out into many identical-schema children and unions them
back together -- e.g. a union assembled from repartitioned copies of the
same input. An instance like this occurred with InfluxDB: every child
schema was the same, so the merge, guaranteed to reproduce the first
child's schema, unnecessarily incurred the planning latency penalty from
`O(n^2 * f)` complexity.
### Relationship to apache#19792
`UnionExec` construction has two quadratic halves:
- **`with_new_children` / `PlanProperties`** -- addressed by apache#19792
(`with_new_children_and_same_properties`, `Arc<PlanProperties>`, the
properties fast path). Already on `main`.
- **`union_schema`** -- *not* covered by apache#19792 and still quadratic on
`main`.
This PR complements it by making `union_schema` skip the merge when it
can't change the result. It deliberately doesn't touch
`with_new_children`; that path is already handled.
## What changes are included?
A fast path at the top of `union_schema`: after taking
`inputs[0].schema()`, if every remaining child's schema is either the
**same allocation** (`Arc::ptr_eq`) or **structurally equal** (`==`) to
the first, return the first schema immediately. Otherwise we fall
through to the existing full merge, so behavior for genuinely
heterogeneous unions is byte-for-byte unchanged.
```rust
let first_schema = inputs[0].schema();
if inputs[1..].iter().all(|input| {
let schema = input.schema();
Arc::ptr_eq(&schema, &first_schema) || schema == first_schema
}) {
return Ok(first_schema);
}
```
`InterleaveExec` shares `union_schema`, so it gets the same speedup for
free.
## On the cost of the deep compare...
The natural objection (which came up before this PR): **doesn't the deep
`==` make the *unequal* case slower?** I'll paraphrase the prior
conclusions, risking verbosity to avoid rehashing the discussion.
Spoiler: it's not an issue.
- The equal case avoids the merge, and its check is cheap. The
shared-`Arc` case is settled by pointer comparison. The
distinct-but-equal case runs `Schema::eq`, which is allocation-free and
short-circuits on the first difference. Benchmarks show a small loss
versus a pointer-equality-only control (the theoretical floor) but it
still beats the full merge by a wide margin, and that advantage grows
with schema complexity.
- The adversarial worst case is bounded. The one shape where the scan is
pure overhead is `last_differs`: children `0..n-1` are equal and the
last diverges, so we scan `n` schemas, fail on the last, then merge
anyway. That's a single linear `==` pass bounded by the merge that
follows -- a constant fraction, not another factor of `n` -- and it
takes *thousands* of near-identical children differing only in the last
to hit.
- Ordinary unequal unions fail fast. `SELECT a ... UNION ALL SELECT b
...` differs at field 0, so `==` rejects on the first field (see
`names_differ`). And `UnionExec::try_new` already rejects misaligned
children, so the only divergence `union_schema` ever sees is top-level
(caught in the first pass).
## Benchmark results
New bench `datafusion/physical-plan/benches/union_schema.rs` measures
`UnionExec::try_new` construction over a flat schema and a nested/struct
schema, for the four child shapes above. Run interleaved (baseline /
patched alternated per cell) on a fixed-clock T2D VM.
### `union_schema` construction (lower is better)
| scenario | n | baseline (ms) | patched (ms) | change |
|---|---|---|---|---|
| union_exec_try_new/shared_arc | 100 | 0.263 | 0.042 | 6.2× |
| union_exec_try_new/shared_arc | 1000 | 2.60 | 0.429 | 6.1× |
| union_exec_try_new/shared_arc | 4000 | 10.5 | 1.74 | 6.0× |
| union_exec_try_new/content_equal | 100 | 0.262 | 0.042 | 6.2× |
| union_exec_try_new/content_equal | 1000 | 2.61 | 0.433 | 6.0× |
| union_exec_try_new/content_equal | 4000 | 10.5 | 1.74 | 6.0× |
| union_exec_try_new/last_differs | 4000 | ~98 | ~97 | flat (±1.5%) |
| union_exec_try_new/names_differ | 4000 | ~87 | ~87 | flat (±1%) |
| union_exec_try_new_nested/content_equal | 1000 | 2.68 | 0.431 | 6.2× |
| union_exec_try_new_nested/content_equal | 4000 | 10.8 | 1.73 | 6.2× |
The `last_differs` (adversarial: N-1 children equal, deep compare then
full merge) and `names_differ` (typical unequal: fails on the first
field) cells were re-measured with tight per-cell interleaving
(baseline/patched adjacent, 4 rounds) to control for variance: both are
within ±1.5%, straddling zero. Interpretation: the **deep compare cost
isn't observable end to end**.
### End-to-end planning: no regression (`sql_planner`)
`cargo bench --bench sql_planner` (TPC-H + ClickBench) run baseline vs
patched on the fixed-clock T2D VM. Every case lands within ±1% --
run-to-run noise -- with no case regressing beyond that noise. Notable
rows, including the union-heavy `sorted_union` cases the fast path is
meant to help:
| case | baseline (ms) | patched (ms) |
|---|---|---|
| physical_plan_tpcds_all | 995.9 ± 1.4 | 991.9 ± 1.9 |
| physical_plan_tpch_all | 60.4 ± 0.2 | 60.3 ± 0.1 |
| physical_sorted_union_order_by_50 | 349.9 ± 2.4 | 346.3 ± 2.7 |
| physical_sorted_union_order_by_10 | 12.3 ± 0.03 | 12.2 ± 0.07 |
| physical_select_all_from_1000 | 30.8 ± 0.25 | 30.7 ± 0.08 |
The full TPC-H q1-q22 and ClickBench sets are all flat (ratio is
1.00-1.01 in both directions). Separately, interleaving tests per-cell
(baseline and patched back-to-back, so run-to-run variance -- e.g.
thermal -- cancels rather than favoring one) for
`physical_join_distinct` + eight ClickBench queries (4 rounds) confirmed
the same thing: patched and baseline straddle zero; no systematic
regression from the deep compare.
## Testing
- `cargo test -p datafusion-physical-plan --lib union` -- all pass,
including a new `test_union_schema_fast_path_content_equal` that
exercises the `==` branch with pointer-distinct-but-equal schemas and
asserts the result matches the shared schema (i.e. identical to the
slow-path merge).
- `cargo clippy -p datafusion-physical-plan --lib -- -D warnings` --
clean.
- `cargo bench --bench union_schema` -- compiles and runs.
## Are there any user-facing changes?
No: planning-time performance change only, results and schema are
identical.
---------
Signed-off-by: Reid Kaufmann <[email protected]>union_schema when all children share a schema (apache#24389)1 parent bb45fb8 commit 47794ff
3 files changed
Lines changed: 209 additions & 0 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
108 | 108 | | |
109 | 109 | | |
110 | 110 | | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
111 | 115 | | |
112 | 116 | | |
113 | 117 | | |
| |||
| 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 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| 119 | + | |
| 120 | + | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
| 131 | + | |
| 132 | + | |
| 133 | + | |
| 134 | + | |
| 135 | + | |
| 136 | + | |
| 137 | + | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
| 145 | + | |
| 146 | + | |
| 147 | + | |
| 148 | + | |
| 149 | + | |
| 150 | + | |
| 151 | + | |
| 152 | + | |
| 153 | + | |
| 154 | + | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
| 158 | + | |
| 159 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
916 | 916 | | |
917 | 917 | | |
918 | 918 | | |
| 919 | + | |
| 920 | + | |
| 921 | + | |
| 922 | + | |
| 923 | + | |
| 924 | + | |
| 925 | + | |
| 926 | + | |
| 927 | + | |
| 928 | + | |
| 929 | + | |
| 930 | + | |
| 931 | + | |
| 932 | + | |
| 933 | + | |
| 934 | + | |
919 | 935 | | |
920 | 936 | | |
921 | 937 | | |
| |||
1627 | 1643 | | |
1628 | 1644 | | |
1629 | 1645 | | |
| 1646 | + | |
| 1647 | + | |
| 1648 | + | |
| 1649 | + | |
| 1650 | + | |
| 1651 | + | |
| 1652 | + | |
| 1653 | + | |
| 1654 | + | |
| 1655 | + | |
| 1656 | + | |
| 1657 | + | |
| 1658 | + | |
| 1659 | + | |
| 1660 | + | |
| 1661 | + | |
| 1662 | + | |
| 1663 | + | |
| 1664 | + | |
| 1665 | + | |
| 1666 | + | |
| 1667 | + | |
| 1668 | + | |
| 1669 | + | |
| 1670 | + | |
| 1671 | + | |
| 1672 | + | |
| 1673 | + | |
| 1674 | + | |
| 1675 | + | |
1630 | 1676 | | |
1631 | 1677 | | |
1632 | 1678 | | |
| |||
0 commit comments