Repository navigation
Commit 7ca68cf
authored
perf: avoid quadratic metadata merging in union schemas (apache#26790)
## Which issue does this PR close?
Related to apache#17261. Complements the fast path for equal schemas added in
apache#24389.
Benchmark coverage is reviewed in apache#26791. This PR is stacked on its
benchmark-only commit `cfc6594b5`; the [optimization-only
diff](apache/datafusion@cfc6594...c5f9d3e)
contains the schema change and regression test.
## Rationale for this change
Constructing a union with unequal input schemas can take quadratic time
in the number of children. The fallback merges every input's field
metadata before checking whether that candidate field is nullable. With
non-nullable fields, the same full merge is repeated for every child.
Select the first nullable field (or the first field when none are
nullable) before merging metadata. This makes the fallback linear in
child count for a fixed number of fields and metadata entries per input.
The shared helper also serves `InterleaveExec`.
## What changes are included in this PR?
- Merge metadata once per output field, preserving the selected field,
leftmost name, and existing metadata conflict precedence.
- Add a test that constructs and executes unions with non-nullable
inputs, first/middle/last nullable inputs, conflicting and distinct
metadata keys, and checks output rows.
## What is the testing strategy for this PR?
Benchmarks use upstream `c18e5d974` plus the benchmark extension, Rust
1.99.1, `release-nonlto`, and an Apple M5 Pro. The table averages two
interleaved runs per binary, with 20 Criterion samples per run. Schemas
have 10 fields and two metadata entries per field.
| Non-nullable schema case | Children | Upstream | Patched | Speedup |
| --- | ---: | ---: | ---: | ---: |
| Last child's metadata differs | 10 | 141 µs | 62 µs | 2.3× |
| Last child's metadata differs | 100 | 9.24 ms | 0.66 ms | 14.1× |
| Last child's metadata differs | 1,000 | 877 ms | 7.40 ms | 118.6× |
| Field names differ | 10 | 140 µs | 60 µs | 2.3× |
| Field names differ | 100 | 9.38 ms | 0.66 ms | 14.3× |
| Field names differ | 1,000 | 866 ms | 7.36 ms | 117.6× |
The controls with nullable fields or equal schemas at 4,000 children
varied from -0.8% to +6.3% on this shared machine. Background builds
affected some measurements, so the larger SQL cases with sorted unions
were also checked in a tighter alternating sequence, with four runs per
binary:
| SQL planning case | Upstream | Patched | Change |
| --- | ---: | ---: | ---: |
| 50 columns, Int64 | 38.61 ms | 38.40 ms | -0.5% |
| 50 columns, UInt64 | 139.48 ms | 139.63 ms | +0.1% |
These results establish the constructor improvement independently of
apache#17261; they do not establish an improvement in the SQL planning
workloads. The original extended logical-planning benchmark only calls
logical optimization and does not exercise this physical schema helper.
To run the benchmark cases from apache#26791:
```sh
cargo bench --profile release-nonlto -p datafusion-physical-plan --bench union_schema -- union_exec_try_new_non_nullable
```
## Are there any user-facing changes?
Faster construction of unions and interleaves with unequal schemas and
non-nullable fields. Schema behavior and public APIs are preserved.
AI assistance: OpenAI Codex.1 parent 8f77b41 commit 7ca68cf
2 files changed
Lines changed: 110 additions & 30 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
12 | 12 | | |
13 | 13 | | |
14 | 14 | | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
15 | 18 | | |
16 | 19 | | |
17 | 20 | | |
| |||
32 | 35 | | |
33 | 36 | | |
34 | 37 | | |
35 | | - | |
| 38 | + | |
36 | 39 | | |
37 | 40 | | |
38 | | - | |
| 41 | + | |
39 | 42 | | |
40 | 43 | | |
41 | 44 | | |
| |||
107 | 110 | | |
108 | 111 | | |
109 | 112 | | |
110 | | - | |
| 113 | + | |
111 | 114 | | |
| 115 | + | |
112 | 116 | | |
113 | 117 | | |
114 | 118 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
33 | 33 | | |
34 | 34 | | |
35 | 35 | | |
36 | | - | |
| 36 | + | |
37 | 37 | | |
38 | 38 | | |
39 | 39 | | |
| |||
970 | 970 | | |
971 | 971 | | |
972 | 972 | | |
973 | | - | |
974 | | - | |
| 973 | + | |
| 974 | + | |
975 | 975 | | |
976 | 976 | | |
977 | 977 | | |
| |||
1003 | 1003 | | |
1004 | 1004 | | |
1005 | 1005 | | |
1006 | | - | |
1007 | | - | |
1008 | | - | |
| 1006 | + | |
| 1007 | + | |
| 1008 | + | |
| 1009 | + | |
1009 | 1010 | | |
1010 | 1011 | | |
1011 | | - | |
1012 | | - | |
1013 | | - | |
1014 | | - | |
1015 | | - | |
1016 | | - | |
1017 | | - | |
1018 | | - | |
1019 | | - | |
1020 | | - | |
1021 | | - | |
1022 | | - | |
1023 | | - | |
1024 | | - | |
1025 | | - | |
1026 | | - | |
1027 | | - | |
1028 | | - | |
1029 | | - | |
1030 | | - | |
| 1012 | + | |
| 1013 | + | |
| 1014 | + | |
| 1015 | + | |
| 1016 | + | |
| 1017 | + | |
| 1018 | + | |
| 1019 | + | |
| 1020 | + | |
| 1021 | + | |
| 1022 | + | |
| 1023 | + | |
| 1024 | + | |
| 1025 | + | |
| 1026 | + | |
| 1027 | + | |
| 1028 | + | |
1031 | 1029 | | |
1032 | 1030 | | |
1033 | 1031 | | |
| |||
1119 | 1117 | | |
1120 | 1118 | | |
1121 | 1119 | | |
1122 | | - | |
| 1120 | + | |
1123 | 1121 | | |
1124 | 1122 | | |
1125 | 1123 | | |
| |||
1725 | 1723 | | |
1726 | 1724 | | |
1727 | 1725 | | |
| 1726 | + | |
| 1727 | + | |
| 1728 | + | |
| 1729 | + | |
| 1730 | + | |
| 1731 | + | |
| 1732 | + | |
| 1733 | + | |
| 1734 | + | |
| 1735 | + | |
| 1736 | + | |
| 1737 | + | |
| 1738 | + | |
| 1739 | + | |
| 1740 | + | |
| 1741 | + | |
| 1742 | + | |
| 1743 | + | |
| 1744 | + | |
| 1745 | + | |
| 1746 | + | |
| 1747 | + | |
| 1748 | + | |
| 1749 | + | |
| 1750 | + | |
| 1751 | + | |
| 1752 | + | |
| 1753 | + | |
| 1754 | + | |
| 1755 | + | |
| 1756 | + | |
| 1757 | + | |
| 1758 | + | |
| 1759 | + | |
| 1760 | + | |
| 1761 | + | |
| 1762 | + | |
| 1763 | + | |
| 1764 | + | |
| 1765 | + | |
| 1766 | + | |
| 1767 | + | |
| 1768 | + | |
| 1769 | + | |
| 1770 | + | |
| 1771 | + | |
| 1772 | + | |
| 1773 | + | |
| 1774 | + | |
| 1775 | + | |
| 1776 | + | |
| 1777 | + | |
| 1778 | + | |
| 1779 | + | |
| 1780 | + | |
| 1781 | + | |
| 1782 | + | |
| 1783 | + | |
| 1784 | + | |
| 1785 | + | |
| 1786 | + | |
| 1787 | + | |
| 1788 | + | |
| 1789 | + | |
| 1790 | + | |
| 1791 | + | |
| 1792 | + | |
| 1793 | + | |
| 1794 | + | |
| 1795 | + | |
| 1796 | + | |
| 1797 | + | |
| 1798 | + | |
| 1799 | + | |
| 1800 | + | |
| 1801 | + | |
| 1802 | + | |
| 1803 | + | |
1728 | 1804 | | |
1729 | 1805 | | |
1730 | 1806 | | |
| |||
0 commit comments