Repository navigation
Commit 44db469
## Which issue does this PR close?
- Closes apache#23953
## Rationale for this change
This PR makes three improvements to non-distinct
`PercentileContAccumulator` and `MedianAccumulator`, inspired by recent
work on `percentile_cont(DISTINCT)` (apache#23946):
1. Switch from SipHash to foldhash for internal hash maps
2. Add a null-free fast path to `update_batch` and `retract_batch`
3. Raise an error if we attempt to retract an unknown value in
`retract_batch`, rather than silently ignoring it.
Benchmarks:
percentile_cont no_nulls window=256 -61.1% (249.0 -> 96.6 us)
percentile_cont with_nulls window=256 -59.4% (232.7 -> 94.5 us)
percentile_cont no_nulls window=4096 -50.9% (756.3 -> 370.4 us)
percentile_cont with_nulls window=4096 -48.2% (552.2 -> 286.2 us)
percentile_cont no_nulls window=16384 -47.3% (2.311 -> 1.218 ms)
percentile_cont with_nulls window=16384 -42.0% (1.465 -> 0.851 ms)
median no_nulls window=256 -62.8% (247.0 -> 92.0 us)
median with_nulls window=256 -59.8% (228.8 -> 92.0 us)
median no_nulls window=4096 -40.0% (411.4 -> 246.6 us)
median with_nulls window=4096 -39.4% (364.4 -> 221.0 us)
median no_nulls window=16384 -31.5% (1.107 -> 0.759 ms)
median with_nulls window=16384 -32.9% (0.947 -> 0.637 ms)
## What changes are included in this PR?
See above.
## Are these changes tested?
Yes: existing tests pass, new tests added for the null-free fast path
and the improved error handling.
## Are there any user-facing changes?
No.
1 parent fb75a61 commit 44db469
2 files changed
Lines changed: 155 additions & 13 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
39 | 39 | | |
40 | 40 | | |
41 | 41 | | |
| 42 | + | |
42 | 43 | | |
43 | 44 | | |
44 | 45 | | |
45 | | - | |
| 46 | + | |
46 | 47 | | |
47 | 48 | | |
48 | 49 | | |
| |||
288 | 289 | | |
289 | 290 | | |
290 | 291 | | |
291 | | - | |
| 292 | + | |
| 293 | + | |
| 294 | + | |
| 295 | + | |
| 296 | + | |
| 297 | + | |
292 | 298 | | |
293 | 299 | | |
294 | 300 | | |
| |||
310 | 316 | | |
311 | 317 | | |
312 | 318 | | |
313 | | - | |
| 319 | + | |
| 320 | + | |
314 | 321 | | |
315 | 322 | | |
316 | | - | |
317 | | - | |
| 323 | + | |
| 324 | + | |
| 325 | + | |
| 326 | + | |
| 327 | + | |
| 328 | + | |
| 329 | + | |
| 330 | + | |
| 331 | + | |
318 | 332 | | |
319 | 333 | | |
320 | 334 | | |
| |||
335 | 349 | | |
336 | 350 | | |
337 | 351 | | |
| 352 | + | |
| 353 | + | |
| 354 | + | |
| 355 | + | |
| 356 | + | |
| 357 | + | |
| 358 | + | |
| 359 | + | |
| 360 | + | |
338 | 361 | | |
339 | 362 | | |
340 | 363 | | |
| |||
627 | 650 | | |
628 | 651 | | |
629 | 652 | | |
| 653 | + | |
| 654 | + | |
| 655 | + | |
| 656 | + | |
| 657 | + | |
| 658 | + | |
| 659 | + | |
| 660 | + | |
| 661 | + | |
| 662 | + | |
| 663 | + | |
| 664 | + | |
| 665 | + | |
| 666 | + | |
| 667 | + | |
| 668 | + | |
| 669 | + | |
| 670 | + | |
| 671 | + | |
| 672 | + | |
| 673 | + | |
| 674 | + | |
| 675 | + | |
| 676 | + | |
| 677 | + | |
| 678 | + | |
| 679 | + | |
| 680 | + | |
| 681 | + | |
| 682 | + | |
| 683 | + | |
| 684 | + | |
| 685 | + | |
| 686 | + | |
| 687 | + | |
| 688 | + | |
| 689 | + | |
| 690 | + | |
| 691 | + | |
| 692 | + | |
| 693 | + | |
| 694 | + | |
| 695 | + | |
| 696 | + | |
| 697 | + | |
| 698 | + | |
| 699 | + | |
| 700 | + | |
| 701 | + | |
| 702 | + | |
| 703 | + | |
| 704 | + | |
| 705 | + | |
| 706 | + | |
| 707 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
429 | 429 | | |
430 | 430 | | |
431 | 431 | | |
432 | | - | |
| 432 | + | |
| 433 | + | |
| 434 | + | |
| 435 | + | |
| 436 | + | |
| 437 | + | |
433 | 438 | | |
434 | 439 | | |
435 | 440 | | |
| |||
449 | 454 | | |
450 | 455 | | |
451 | 456 | | |
452 | | - | |
| 457 | + | |
| 458 | + | |
453 | 459 | | |
454 | 460 | | |
455 | | - | |
456 | | - | |
| 461 | + | |
| 462 | + | |
| 463 | + | |
| 464 | + | |
| 465 | + | |
| 466 | + | |
| 467 | + | |
| 468 | + | |
| 469 | + | |
457 | 470 | | |
458 | 471 | | |
459 | 472 | | |
| |||
474 | 487 | | |
475 | 488 | | |
476 | 489 | | |
| 490 | + | |
| 491 | + | |
| 492 | + | |
| 493 | + | |
| 494 | + | |
| 495 | + | |
| 496 | + | |
| 497 | + | |
| 498 | + | |
477 | 499 | | |
478 | 500 | | |
479 | 501 | | |
| |||
876 | 898 | | |
877 | 899 | | |
878 | 900 | | |
879 | | - | |
| 901 | + | |
| 902 | + | |
880 | 903 | | |
881 | 904 | | |
| 905 | + | |
| 906 | + | |
| 907 | + | |
| 908 | + | |
| 909 | + | |
| 910 | + | |
| 911 | + | |
| 912 | + | |
| 913 | + | |
| 914 | + | |
| 915 | + | |
| 916 | + | |
| 917 | + | |
| 918 | + | |
| 919 | + | |
| 920 | + | |
| 921 | + | |
| 922 | + | |
| 923 | + | |
| 924 | + | |
| 925 | + | |
| 926 | + | |
| 927 | + | |
| 928 | + | |
| 929 | + | |
| 930 | + | |
| 931 | + | |
| 932 | + | |
| 933 | + | |
| 934 | + | |
| 935 | + | |
| 936 | + | |
| 937 | + | |
| 938 | + | |
| 939 | + | |
| 940 | + | |
| 941 | + | |
| 942 | + | |
| 943 | + | |
| 944 | + | |
| 945 | + | |
| 946 | + | |
882 | 947 | | |
883 | 948 | | |
884 | 949 | | |
885 | 950 | | |
886 | 951 | | |
887 | 952 | | |
888 | | - | |
889 | | - | |
890 | | - | |
| 953 | + | |
| 954 | + | |
891 | 955 | | |
892 | 956 | | |
893 | 957 | | |
| |||
0 commit comments