Repository navigation
Commit bc1be2c
authored
perf: stop dictionary work growing with the group count (apache#26703)
## Which issue does this PR close?
- Closes apache#26696.
## Rationale for this change
Queries that group on a high-cardinality dictionary column slow down as
the group count grows. On ClickBench `hits_partitioned` with
`enable_rle_to_dictionary = true`, this PR takes the suite from 78.8 s
to 42.8 s, with Q33 and Q34 about 3.5x faster and peak memory slightly
lower ([bot
run](apache#26703 (comment))).
A hash aggregate builds its output once and emits it in `batch_size`
slices, and slicing a `DictionaryArray` keeps every value. Every slice
therefore carries every group's value, so hashing, functions such as
`lower`, the repartition coalescer and the final aggregate do work per
slice that grows with the group count.
## What changes are included in this PR?
Start reading at `next_batch` in
`aggregates/aggregate_hash_table/common.rs`.
- **Aggregate output, the main gain.** A slice with more values than
rows now holds only the values its rows reference. No threshold is
needed: each group is emitted once, so the cost is fixed per group.
- **A bound for other batches.** Filters and scans also keep whole
dictionaries, so `hash_dictionary` and the new `map_dictionary_values`
handle at most `MAX_DICTIONARY_VALUES_PER_ROW` (64) values per row and
compact past that. Too high only gives up an improvement, while too low
makes cheap work slower: `lower` and `upper` break even at about 40
values per row with keys in random order. The filter and scan queries I
measured showed no visible difference, so this is a guard, not a
measured speedup.
- **`compact_dictionary`** does both, taking each referenced value once.
`take(values, keys)` copies per row, and multi-column group keys repeat
dictionary keys, so it can overflow `i32` offsets, need more rows than
the key type holds, and copy a long value thousands of times.
- **`map_dictionary_values`** replaces
`dictionary.with_values(f(values))` in the string functions, Spark
`hex`, `array_agg`, `regexp_replace` and `substr`, and `clippy.toml`
disallows calling `with_values` directly. If `f` fails, it retries on
only the referenced values, because `f` can see values no row
references. This replaces `substr`'s own fallback.
Each aggregate slice now has its own values `Arc`, so the hash cache
proposed in apache#26816 would miss on these slices. The two haven't been
measured together.
## Benchmarks
| ClickBench partitioned | main | this PR |
|---|---|---|
| Total | 78.8 s | 42.8 s |
| Q33 | 14.9 s | 4.4 s |
| Q34 | 14.8 s | 4.1 s |
| Q18 | 7.6 s | 2.3 s |
| Peak memory | 13.1 GiB | 12.7 GiB |
Q35, Q32 and Q40 read 1.05x to 1.10x slower by minimum. None groups on a
dictionary column, so this PR only adds a type check per output batch
for them, and the bot's noise is about 5-7% per query.
<details><summary>Local runs on a busy 12-core laptop: `lower`, memory
limits, filter queries</summary>
Results were identical on every query. Treat small differences as noise.
`lower` over a dictionary GROUP BY, which ClickBench doesn't cover:
```sql
SELECT lower(s), c FROM (
SELECT "SearchPhrase" s, COUNT(*) c FROM hits WHERE "SearchPhrase" <> '' GROUP BY s
) ORDER BY c DESC, 1 LIMIT 10;
```
| partitions | 12 | 24 | 32 | 48 | 64 |
|---|---|---|---|---|---|
| ratio to main | 0.08x | 0.14x | 0.16x | 0.24x | 0.22x |
Q33 under `--memory-limit`, one run each:
| limit | main | this PR |
|---|---|---|
| 12g | fails: TopK resources exhausted | 6.3 s |
| 8g | 23.6 s | 16.4 s |
| 6g | 31.2 s | 19.4 s |
| 4g | 20.2 s | 14.3 s |
Filter and scan queries using `reverse`, `initcap`, `LIKE` and hashing
after a filter, with the bound at 40: 0.94x to 1.05x of main.
</details>
## What is the testing strategy for this PR?
- `dictionary.slt` compares each function on aggregate output and on
filter output with the same function on the decoded value. The
comparison is projected, because a filter on the group key is pushed
below the aggregate.
- Unit tests cover `next_batch`, `map_dictionary_values` and hashing:
repeated keys, NULL groups, more rows than the key type holds, and a
value too long to copy per row.
- The `dictionary_sliced` case in
`datafusion/common/benches/with_hashes.rs` covers 8 and 128 values per
row.
## Are there any user-facing changes?
No behavior changes. `datafusion_common::utils` gains
`compact_dictionary`, `map_dictionary_values` and
`MAX_DICTIONARY_VALUES_PER_ROW`.1 parent 4bf32cb commit bc1be2c
21 files changed
Lines changed: 683 additions & 123 deletions
File tree
- datafusion
- common
- benches
- src
- utils
- functions-aggregate/src
- functions/src
- core
- regex
- string
- unicode
- physical-plan/src/aggregates/aggregate_hash_table
- spark/src/function/math
- sqllogictest/test_files
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
5 | 5 | | |
6 | 6 | | |
7 | 7 | | |
| 8 | + | |
| 9 | + | |
8 | 10 | | |
9 | 11 | | |
10 | 12 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
59 | 59 | | |
60 | 60 | | |
61 | 61 | | |
| 62 | + | |
62 | 63 | | |
63 | 64 | | |
64 | 65 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
7 | 7 | | |
8 | 8 | | |
9 | 9 | | |
10 | | - | |
| 10 | + | |
11 | 11 | | |
12 | 12 | | |
13 | 13 | | |
| |||
394 | 394 | | |
395 | 395 | | |
396 | 396 | | |
| 397 | + | |
| 398 | + | |
| 399 | + | |
| 400 | + | |
| 401 | + | |
| 402 | + | |
| 403 | + | |
| 404 | + | |
| 405 | + | |
| 406 | + | |
| 407 | + | |
| 408 | + | |
| 409 | + | |
| 410 | + | |
| 411 | + | |
| 412 | + | |
397 | 413 | | |
398 | 414 | | |
399 | 415 | | |
| |||
407 | 423 | | |
408 | 424 | | |
409 | 425 | | |
| 426 | + | |
| 427 | + | |
| 428 | + | |
| 429 | + | |
| 430 | + | |
| 431 | + | |
| 432 | + | |
| 433 | + | |
410 | 434 | | |
411 | 435 | | |
412 | 436 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
4 | 4 | | |
5 | 5 | | |
6 | 6 | | |
| 7 | + | |
| 8 | + | |
7 | 9 | | |
8 | 10 | | |
9 | 11 | | |
| |||
656 | 658 | | |
657 | 659 | | |
658 | 660 | | |
659 | | - | |
| 661 | + | |
| 662 | + | |
| 663 | + | |
| 664 | + | |
| 665 | + | |
660 | 666 | | |
661 | 667 | | |
662 | 668 | | |
| |||
671 | 677 | | |
672 | 678 | | |
673 | 679 | | |
| 680 | + | |
| 681 | + | |
674 | 682 | | |
675 | 683 | | |
676 | 684 | | |
| |||
1836 | 1844 | | |
1837 | 1845 | | |
1838 | 1846 | | |
| 1847 | + | |
| 1848 | + | |
| 1849 | + | |
| 1850 | + | |
| 1851 | + | |
| 1852 | + | |
| 1853 | + | |
| 1854 | + | |
| 1855 | + | |
| 1856 | + | |
| 1857 | + | |
| 1858 | + | |
| 1859 | + | |
| 1860 | + | |
| 1861 | + | |
| 1862 | + | |
| 1863 | + | |
| 1864 | + | |
| 1865 | + | |
| 1866 | + | |
| 1867 | + | |
| 1868 | + | |
| 1869 | + | |
| 1870 | + | |
| 1871 | + | |
| 1872 | + | |
| 1873 | + | |
| 1874 | + | |
| 1875 | + | |
| 1876 | + | |
| 1877 | + | |
| 1878 | + | |
| 1879 | + | |
| 1880 | + | |
| 1881 | + | |
| 1882 | + | |
| 1883 | + | |
| 1884 | + | |
| 1885 | + | |
| 1886 | + | |
| 1887 | + | |
| 1888 | + | |
| 1889 | + | |
| 1890 | + | |
| 1891 | + | |
| 1892 | + | |
| 1893 | + | |
| 1894 | + | |
| 1895 | + | |
| 1896 | + | |
| 1897 | + | |
| 1898 | + | |
| 1899 | + | |
| 1900 | + | |
| 1901 | + | |
| 1902 | + | |
| 1903 | + | |
| 1904 | + | |
| 1905 | + | |
| 1906 | + | |
| 1907 | + | |
| 1908 | + | |
| 1909 | + | |
| 1910 | + | |
| 1911 | + | |
| 1912 | + | |
| 1913 | + | |
| 1914 | + | |
| 1915 | + | |
| 1916 | + | |
| 1917 | + | |
| 1918 | + | |
| 1919 | + | |
| 1920 | + | |
| 1921 | + | |
| 1922 | + | |
| 1923 | + | |
| 1924 | + | |
| 1925 | + | |
| 1926 | + | |
| 1927 | + | |
| 1928 | + | |
| 1929 | + | |
| 1930 | + | |
| 1931 | + | |
1839 | 1932 | | |
1840 | 1933 | | |
1841 | 1934 | | |
| |||
0 commit comments