Repository navigation
Commit 198ab43
authored
perf(pwmj): build output batches from buffered runs and one streamed … (#26287)
## Which issue does this PR close?
- Part of #18221 (and the PiecewiseMergeJoin EPIC #17427).
## Rationale for this change
On large inputs the classic `PiecewiseMergeJoin` (Inner/Left/Right/Full)
can be slower than `NestedLoopJoin`. For example, before #25840, `l JOIN
r ON l.a < r.b` over 100K×100K rows at the default `target_partitions`
took 1.41s with PWMJ and 1.26s with NLJ.
A profile of the 1K×1M case (`sample`, `target_partitions = 1`) shows
the time goes to copying output rather than to comparisons:
| where | share of busy samples |
|---|---|
| `take` repeating each matched streamed row | 32% |
| `BatchCoalescer` `memmove` of every column | 30% |
| downstream `sum` (the query itself) | 10% |
| per-streamed-row fixed cost (`RecordBatch`, allocations, coalescer
bookkeeping) | ~13% |
For every matched streamed row, the join takes
`UInt32Array::from_value(row, count)`, gathers the streamed row `count`
times, slices the buffered suffix, and builds a `RecordBatch` from them.
`BatchCoalescer` then copies all of it again, so the streamed columns
are written twice. #25840 made finding each row's first match a binary
search and settles never-matching rows before the sort, but it kept this
emission path, so on current `main` the cost above is still paid for
every matched streamed row.
## What changes are included in this PR?
The classic join builds each output batch directly, and `BatchCoalescer`
is removed from this path.
Matched rows:
- The output is kept as runs: `(buffered start, len)`, paired with one
streamed row index per output row.
- Once `batch_size` rows are pending, or the stream batch ends:
- Buffered columns are copied run by run with
`MutableArrayData::try_extend`, which is a `memcpy` for fixed-width
types.
- Streamed columns are gathered with one `take` per column.
Rows that match nothing are emitted with null columns for the other
side, in batches of at most `batch_size`:
- Streamed rows that can never match (`Right`/`Full`), which #25840
settles before the sort, are selected with one `filter_record_batch` and
emitted as slices of its output (`push_unmatched_streamed`). When every
row of a stream batch is unmatched, `filter` returns the input columns
as a slice and copies nothing.
- Unmatched buffered rows (`Left`/`Full`), in the final pass, are the
prefix before the `min_marked` watermark plus any trailing NULL keys
(#26043). They are copied out of the buffered batch
(`push_unmatched_buffered`), not sliced: a slice would keep the whole
buffered batch alive and report its full buffers to downstream memory
accounting once per output batch
## Benchmarks
The pwmj suite from #25839
(100K buffered keys, 2M streamed rows, five match regimes ×
INNER/LEFT/RIGHT/FULL). Reproduce with:
`cargo run -p datafusion-benchmarks --release --bin benchmark_runner --
pwmj`
| regime | main (ms) | this PR (ms) | speedup |
|---|---|---|---|
| no_match, null_heavy: Inner, Left | 2.2–2.3 | 2.1 | 1.05× |
| no_match, null_heavy: Right, Full | 3.2–3.3 | 2.4–2.5 | **1.29–1.33×**
|
| half_match | 231–233 | 27–29 | **8.1–8.4×** |
| selective | 453–455 | 47–48 | **9.5–9.7×** |
| all_match (200M output rows) | 167–168 | 159–161 | 1.05–1.06× |
## What is the testing strategy for this PR?
Six new unit tests in `classic_join.rs`:
- `join_full_less_than_splits_suffixes_across_batches`: at `batch_size =
4`, a buffered suffix straddles an output batch, and never-matching
streamed rows, matched rows and unmatched buffered rows all appear. It
asserts both the rows and the batch sizes `[1, 4, 2, 1]`.
- `join_inner_less_than_one_row_completes_several_batches`: one streamed
row whose buffered suffix fills several output batches.
- `join_right_less_than_empty_buffered`: a Right join with an empty
buffered side, where every streamed row is padded with nulls.
- `join_right_less_than_never_matching_rows_split_by_batch_size`: more
never-matching streamed rows than `batch_size`, which must be split into
batches of at most `batch_size`, in input order, ahead of the matched
rows.
- `join_left_less_than_unmatched_prefix_and_trailing_nulls`: a Left join
on `<` whose unmatched buffered rows are a prefix longer than
`batch_size` plus trailing NULL keys, which sort last for `<`.
- `join_left_unmatched_buffered_batches_report_own_memory`: each
unmatched-buffered output batch reports only its own rows' memory, not
the whole buffered batch.
## Are there any user-facing changes?
No API changes. `EXPLAIN ANALYZE` reports a smaller `output_bytes` for
`PiecewiseMergeJoin`, because output batches no longer share the
coalescer's buffers (`explain_analyze.slt`: 128.0 KB → 96.0 B).1 parent 2099174 commit 198ab43
3 files changed
Lines changed: 763 additions & 163 deletions
File tree
- datafusion
- core/tests/fuzz_cases
- physical-plan/src/joins/piecewise_merge_join
- sqllogictest/test_files
| 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 | | |
| |||
1667 | 1668 | | |
1668 | 1669 | | |
1669 | 1670 | | |
1670 | | - | |
| 1671 | + | |
| 1672 | + | |
| 1673 | + | |
| 1674 | + | |
| 1675 | + | |
| 1676 | + | |
| 1677 | + | |
| 1678 | + | |
| 1679 | + | |
| 1680 | + | |
| 1681 | + | |
| 1682 | + | |
| 1683 | + | |
| 1684 | + | |
| 1685 | + | |
| 1686 | + | |
| 1687 | + | |
| 1688 | + | |
| 1689 | + | |
| 1690 | + | |
| 1691 | + | |
1671 | 1692 | | |
1672 | 1693 | | |
1673 | 1694 | | |
| 1695 | + | |
1674 | 1696 | | |
1675 | 1697 | | |
1676 | 1698 | | |
1677 | | - | |
| 1699 | + | |
| 1700 | + | |
| 1701 | + | |
| 1702 | + | |
| 1703 | + | |
1678 | 1704 | | |
1679 | | - | |
1680 | | - | |
| 1705 | + | |
| 1706 | + | |
| 1707 | + | |
| 1708 | + | |
| 1709 | + | |
| 1710 | + | |
1681 | 1711 | | |
1682 | 1712 | | |
1683 | 1713 | | |
| |||
1686 | 1716 | | |
1687 | 1717 | | |
1688 | 1718 | | |
| 1719 | + | |
1689 | 1720 | | |
1690 | 1721 | | |
1691 | | - | |
1692 | | - | |
| 1722 | + | |
| 1723 | + | |
1693 | 1724 | | |
1694 | 1725 | | |
1695 | 1726 | | |
| |||
1705 | 1736 | | |
1706 | 1737 | | |
1707 | 1738 | | |
| 1739 | + | |
1708 | 1740 | | |
1709 | 1741 | | |
1710 | 1742 | | |
| |||
1717 | 1749 | | |
1718 | 1750 | | |
1719 | 1751 | | |
1720 | | - | |
1721 | | - | |
1722 | | - | |
1723 | | - | |
| 1752 | + | |
| 1753 | + | |
| 1754 | + | |
| 1755 | + | |
| 1756 | + | |
1724 | 1757 | | |
1725 | 1758 | | |
1726 | 1759 | | |
1727 | | - | |
| 1760 | + | |
1728 | 1761 | | |
1729 | 1762 | | |
1730 | 1763 | | |
1731 | | - | |
| 1764 | + | |
| 1765 | + | |
1732 | 1766 | | |
1733 | 1767 | | |
1734 | 1768 | | |
| |||
1807 | 1841 | | |
1808 | 1842 | | |
1809 | 1843 | | |
| 1844 | + | |
| 1845 | + | |
| 1846 | + | |
| 1847 | + | |
1810 | 1848 | | |
1811 | 1849 | | |
1812 | 1850 | | |
| 1851 | + | |
1813 | 1852 | | |
1814 | 1853 | | |
1815 | 1854 | | |
| |||
1833 | 1872 | | |
1834 | 1873 | | |
1835 | 1874 | | |
1836 | | - | |
1837 | | - | |
| 1875 | + | |
| 1876 | + | |
| 1877 | + | |
| 1878 | + | |
| 1879 | + | |
| 1880 | + | |
1838 | 1881 | | |
1839 | 1882 | | |
1840 | 1883 | | |
| |||
1857 | 1900 | | |
1858 | 1901 | | |
1859 | 1902 | | |
| 1903 | + | |
1860 | 1904 | | |
1861 | 1905 | | |
1862 | 1906 | | |
| |||
1875 | 1919 | | |
1876 | 1920 | | |
1877 | 1921 | | |
| 1922 | + | |
1878 | 1923 | | |
1879 | 1924 | | |
1880 | 1925 | | |
| |||
1891 | 1936 | | |
1892 | 1937 | | |
1893 | 1938 | | |
| 1939 | + | |
| 1940 | + | |
| 1941 | + | |
| 1942 | + | |
| 1943 | + | |
| 1944 | + | |
| 1945 | + | |
| 1946 | + | |
| 1947 | + | |
| 1948 | + | |
| 1949 | + | |
| 1950 | + | |
| 1951 | + | |
| 1952 | + | |
| 1953 | + | |
| 1954 | + | |
| 1955 | + | |
| 1956 | + | |
| 1957 | + | |
| 1958 | + | |
| 1959 | + | |
| 1960 | + | |
| 1961 | + | |
| 1962 | + | |
| 1963 | + | |
| 1964 | + | |
| 1965 | + | |
| 1966 | + | |
| 1967 | + | |
| 1968 | + | |
1894 | 1969 | | |
1895 | | - | |
1896 | | - | |
| 1970 | + | |
| 1971 | + | |
1897 | 1972 | | |
1898 | 1973 | | |
1899 | 1974 | | |
| |||
1902 | 1977 | | |
1903 | 1978 | | |
1904 | 1979 | | |
1905 | | - | |
| 1980 | + | |
| 1981 | + | |
1906 | 1982 | | |
1907 | 1983 | | |
1908 | 1984 | | |
| |||
1913 | 1989 | | |
1914 | 1990 | | |
1915 | 1991 | | |
1916 | | - | |
1917 | | - | |
| 1992 | + | |
| 1993 | + | |
| 1994 | + | |
| 1995 | + | |
1918 | 1996 | | |
1919 | 1997 | | |
1920 | | - | |
| 1998 | + | |
| 1999 | + | |
| 2000 | + | |
| 2001 | + | |
1921 | 2002 | | |
1922 | 2003 | | |
1923 | 2004 | | |
| |||
1965 | 2046 | | |
1966 | 2047 | | |
1967 | 2048 | | |
1968 | | - | |
| 2049 | + | |
| 2050 | + | |
| 2051 | + | |
| 2052 | + | |
| 2053 | + | |
| 2054 | + | |
| 2055 | + | |
1969 | 2056 | | |
1970 | | - | |
| 2057 | + | |
1971 | 2058 | | |
1972 | 2059 | | |
1973 | 2060 | | |
| |||
1982 | 2069 | | |
1983 | 2070 | | |
1984 | 2071 | | |
| 2072 | + | |
1985 | 2073 | | |
1986 | 2074 | | |
1987 | 2075 | | |
1988 | 2076 | | |
1989 | 2077 | | |
| 2078 | + | |
1990 | 2079 | | |
1991 | 2080 | | |
1992 | 2081 | | |
1993 | 2082 | | |
1994 | | - | |
1995 | | - | |
| 2083 | + | |
| 2084 | + | |
1996 | 2085 | | |
1997 | 2086 | | |
1998 | 2087 | | |
1999 | 2088 | | |
| 2089 | + | |
2000 | 2090 | | |
2001 | 2091 | | |
2002 | 2092 | | |
2003 | 2093 | | |
2004 | 2094 | | |
2005 | 2095 | | |
2006 | | - | |
| 2096 | + | |
2007 | 2097 | | |
2008 | 2098 | | |
2009 | 2099 | | |
| |||
2014 | 2104 | | |
2015 | 2105 | | |
2016 | 2106 | | |
2017 | | - | |
| 2107 | + | |
| 2108 | + | |
| 2109 | + | |
| 2110 | + | |
| 2111 | + | |
| 2112 | + | |
| 2113 | + | |
2018 | 2114 | | |
2019 | 2115 | | |
2020 | 2116 | | |
2021 | 2117 | | |
| 2118 | + | |
2022 | 2119 | | |
2023 | 2120 | | |
2024 | 2121 | | |
2025 | 2122 | | |
2026 | | - | |
2027 | | - | |
| 2123 | + | |
| 2124 | + | |
2028 | 2125 | | |
2029 | 2126 | | |
2030 | 2127 | | |
2031 | 2128 | | |
| 2129 | + | |
2032 | 2130 | | |
2033 | 2131 | | |
2034 | 2132 | | |
2035 | 2133 | | |
2036 | 2134 | | |
2037 | 2135 | | |
2038 | | - | |
| 2136 | + | |
2039 | 2137 | | |
2040 | 2138 | | |
2041 | 2139 | | |
| |||
2141 | 2239 | | |
2142 | 2240 | | |
2143 | 2241 | | |
2144 | | - | |
| 2242 | + | |
2145 | 2243 | | |
2146 | 2244 | | |
2147 | 2245 | | |
2148 | 2246 | | |
2149 | 2247 | | |
| 2248 | + | |
2150 | 2249 | | |
2151 | 2250 | | |
2152 | 2251 | | |
2153 | 2252 | | |
2154 | 2253 | | |
| 2254 | + | |
2155 | 2255 | | |
2156 | 2256 | | |
2157 | 2257 | | |
| |||
0 commit comments