Internal #330: Quantile Performance #9461

hawkfish · 2023-10-25T00:15:34Z

Rewrite of moving quantile and mad to use better/faster data structures.

Add new window_init aggregate API to allow custom window functions to create global data structures
Compute and pass down statistics for frame computations to support global vs local performance optimisations
Add third party skip list code for thread-local implementations
Add (rewritten) third party merge sort tree code for global implementations
Extend MST SelectNth method to handle new EXCLUDE functionality
Fix problem with ValidityMask::Resize where it was always allocating memory instead of deferring if all rows were valid

fixes: duckdblabs/duckdb-internal#330

Add Python implementation of skip lists to libraries.

Convert basic scalar quantile window to use skip lists. Performance on 1e9 rows, single partition, 16 cores went from 11:11 to 00:36.

Convert scalar and list windowed quantile to use skip lists. Performance on 1e9 rows, single partition, 16 cores went from 11:11 to 00:36.

Create MST template for use in quantile and other aggregates.

* Define QuantileSortTree for quantile acceleration. * Add aggregate_wininit_t for constructing global windowing state. * Update aggregate_window_t to take optional global windowing state. * Add quantile WindowInit function (not used yet).

Call window initialisation if it is defined.

Switch quantile computations to use merge sort trees. MAD not converted yet.

Fix double decrement.

Add MIT License.

Toggle 32/64 bit versions.

Refactor, simplify and deploy to Median Absolute Deviation.

Plumb through statistics and extract min/max for ROWS.

Use frame expression statistics to choose between Skip Lists and Merge Sort Trees

Test statistics and handle no propagation situation.

Fix fanout misplacement.

Finish implementing and testing merge sort trees by supporting EXCLUDE/multiple frames.

Fix CI issues (formatting, includes)

Remove non-portable #pragma mark lines.

Standardise SubFrame typing.

Push subframes into the Merge Sort Tree.

hawkfish · 2023-10-30T20:06:49Z

I didn't have an in-depth look at src/core_functions/aggregate/holistic/quantile.cpp and src/include/duckdb/execution/merge_sort_tree.hpp yet. I can do that at a later point this week. I assume that I do not have to look at the skip list code?

The merge sort tree code is Adrian's but I modified it so we could compile it and we collaborated on adding the EXCLUDE changes. I also removed all his messy debugging code and added some whitespace.

The skip list code is a direct import of the code used by Python (it is a separate project). I just added a very simple one element memory pool (pooling is on their TODO list.) and you can look at the diff there (just routing new and delete through an internal class.)

Integrate Tania' feedback (thanks!)

carlopi

Cool results, I only took a look at the skiplist library, minor comments

third_party/skiplist/SkipList.cpp

Incorporate Carlo's review (thanks!)

Fix signed/unsigned portability issue and extra include.

Revert single-bit prng use as it trashes performance by 2x.

Mytherin

Thanks for the PR! Some minor comments. I also launched a NightlyTests to check the code coverage on this feature. Perhaps some more tests could be added after that to ensure the new code is fully tested? I'm not sure how many tests we have that correctly test all of the edge cases here.

src/include/duckdb/execution/window_segment_tree.hpp

src/include/duckdb/function/aggregate_function.hpp

src/execution/window_segment_tree.cpp

hawkfish · 2023-11-03T18:44:55Z

Thanks for the PR! Some minor comments. I also launched a NightlyTests to check the code coverage on this feature. Perhaps some more tests could be added after that to ensure the new code is fully tested? I'm not sure how many tests we have that correctly test all of the edge cases here.

Yeah there is coverage in the benchmark suite but I could certainly move those queries into a test_coverage file now that they are faster...

Clean them up in response to PR feedback. Note that ListWindow is being naughty and modifying the partition data, which is not thread-safe.

Restore the statistics API to use signed values. Add coverage tests for quantile variants.

Mytherin · 2023-11-08T15:26:50Z

Thanks! LGTM

Merge pull request duckdb/duckdb#9392 from lnkuiper/parquet_encryption Merge pull request duckdb/duckdb#9461 from hawkfish/merge-sort-trees Merge pull request duckdb/duckdb#8788 from alnkesq/capi_create_enum_type Merge pull request duckdb/duckdb#9513 from Tmonster/5614-database-invalidated Merge pull request duckdb/duckdb#9622 from Mytherin/typescoping Merge pull request duckdb/duckdb#9615 from hawkfish/strptime-infinity Merge pull request duckdb/duckdb#9627 from Mytherin/attachifnotexists Merge pull request duckdb/duckdb#9648 from samansmink/add-keep-alive-toggle Merge pull request duckdb/duckdb#9638 from taniabogatsch/bench-refactor Merge pull request duckdb/duckdb#9651 from Mytherin/getenv

Richard Wesley and others added 30 commits September 21, 2023 18:23

Internal duckdb#330: Import Skip Lists

087dc99

Add Python implementation of skip lists to libraries.

Merge branch 'main' into window-median

977a104

Internal duckdb#330: Quantile Skip Lists

c764e4a

Convert basic scalar quantile window to use skip lists. Performance on 1e9 rows, single partition, 16 cores went from 11:11 to 00:36.

Internal duckdb#330: Quantile Skip Lists

7a46fbe

Convert scalar and list windowed quantile to use skip lists. Performance on 1e9 rows, single partition, 16 cores went from 11:11 to 00:36.

Merge branch 'quantile-value' into window-median

9c1ebff

Merge branch 'main' into window-median

885544a

Internal duckdb#330: Merge Sort Trees

2d537bc

Create MST template for use in quantile and other aggregates.

Internal duckdb#330: Window Global Init

f3daf20

* Define QuantileSortTree for quantile acceleration. * Add aggregate_wininit_t for constructing global windowing state. * Update aggregate_window_t to take optional global windowing state. * Add quantile WindowInit function (not used yet).

Merge branch 'feature' into merge-sort-trees

76ecd14

Internal duckdb#330: Window Global Init

ec53015

Call window initialisation if it is defined.

Merge branch 'main' into merge-sort-trees

becc78f

Internal duckdb#330: Quantile Merge Sort Trees

c4b338a

Switch quantile computations to use merge sort trees. MAD not converted yet.

Internal duckdb#330: Quantile Merge Sort Trees

b92640d

Fix double decrement.

Internal duckdb#330: Quantile Merge Sort Trees

5bc021c

Add MIT License.

Internal duckdb#330: Quantile Merge Sort Trees

8c915da

Toggle 32/64 bit versions.

Merge branch 'feature' into merge-sort-trees

90f6aed

Internal duckdb#330: MAD Merge Sort Trees

a097ddc

Refactor, simplify and deploy to Median Absolute Deviation.

Merge branch 'feature' into window-median

2372d1c

Merge branch 'window-median' into merge-sort-trees

dac3e45

Internal duckdb#330: Window Frame Statistics

dcbc1c1

Plumb through statistics and extract min/max for ROWS.

Internal duckdb#330: Quantile Statistics

bdfad06

Use frame expression statistics to choose between Skip Lists and Merge Sort Trees

Merge branch 'feature' into merge-sort-trees

2266429

Internal duckdb#330: Window EXCLUDE Statistics

8225dfc

Test statistics and handle no propagation situation.

Internal duckdb#330: Merge Sort Trees

b20a841

Fix fanout misplacement.

Internal duckdb#330: Merge Sort Tree EXCLUDE

a9ef0e9

Finish implementing and testing merge sort trees by supporting EXCLUDE/multiple frames.

Merge branch 'feature' into merge-sort-trees

4c155a2

Internal duckdb#330: Merge Sort Trees

924d264

Fix CI issues (formatting, includes)

Internal duckdb#330: Import Skip Lists

8902ce7

Remove non-portable #pragma mark lines.

Internal duckdb#330: Merge Sort Tree EXCLUDE

eb396b3

Standardise SubFrame typing.

Internal duckdb#330: Quantile EXCLUDE

37f2ea0

Push subframes into the Merge Sort Tree.

Internal duckdb#330: Quantile Performance Review

300e8c0

Integrate Tania' feedback (thanks!)

github-actions bot marked this pull request as draft October 30, 2023 20:34

carlopi reviewed Oct 30, 2023

View reviewed changes

third_party/skiplist/SkipList.cpp Show resolved Hide resolved

third_party/skiplist/SkipList.cpp Show resolved Hide resolved

hawkfish added 6 commits October 30, 2023 14:49

Internal duckdb#330: Quantile Performance Review

67f0fd4

Incorporate Carlo's review (thanks!)

Internal duckdb#330: Quantile Performance Review

2afe92e

Fix signed/unsigned portability issue and extra include.

Merge branch 'feature' into merge-sort-trees

a61e3c4

Merge branch 'feature' into merge-sort-trees

2f48590

Merge branch 'feature' into merge-sort-trees

3312fac

Internal duckdb#330: Quantile Performance Review

9ae5eb7

Revert single-bit prng use as it trashes performance by 2x.

hawkfish marked this pull request as ready for review November 1, 2023 19:09

hawkfish requested a review from hannes November 1, 2023 20:36

Mytherin reviewed Nov 3, 2023

View reviewed changes

src/include/duckdb/execution/window_segment_tree.hpp Outdated Show resolved Hide resolved

src/include/duckdb/function/aggregate_function.hpp Outdated Show resolved Hide resolved

src/execution/window_segment_tree.cpp Outdated Show resolved Hide resolved

Maxxen approved these changes Nov 3, 2023

View reviewed changes

Maxxen mentioned this pull request Nov 3, 2023

Don't reset validity target count #9565

Merged

Richard Wesley added 2 commits November 3, 2023 12:00

Internal duckdb#330: Custom Window APIs

bbe7fe0

Clean them up in response to PR feedback. Note that ListWindow is being naughty and modifying the partition data, which is not thread-safe.

Internal duckdb#330: Quantile Performance Feedback

1016a51

Restore the statistics API to use signed values. Add coverage tests for quantile variants.

github-actions bot marked this pull request as draft November 3, 2023 21:34

hawkfish marked this pull request as ready for review November 3, 2023 22:38

hawkfish added 2 commits November 7, 2023 07:43

Merge branch 'main' into merge-sort-trees

6af08b8

Merge branch 'feature' into merge-sort-trees

dd779a4

github-actions bot marked this pull request as draft November 7, 2023 15:55

hawkfish marked this pull request as ready for review November 7, 2023 15:56

Mytherin changed the base branch from feature to main November 8, 2023 15:19

Mytherin changed the base branch from main to feature November 8, 2023 15:19

Mytherin merged commit aad21f3 into duckdb:feature Nov 8, 2023

hawkfish deleted the merge-sort-trees branch November 8, 2023 16:55

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Internal #330: Quantile Performance #9461

Internal #330: Quantile Performance #9461

Uh oh!

hawkfish commented Oct 25, 2023

Uh oh!

hawkfish commented Oct 30, 2023

Uh oh!

carlopi left a comment

Uh oh!

Uh oh!

Uh oh!

Mytherin left a comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

hawkfish commented Nov 3, 2023

Uh oh!

Mytherin commented Nov 8, 2023

Uh oh!

Uh oh!

Internal #330: Quantile Performance #9461

Internal #330: Quantile Performance #9461

Uh oh!

Conversation

hawkfish commented Oct 25, 2023

Uh oh!

hawkfish commented Oct 30, 2023

Uh oh!

carlopi left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Mytherin left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

hawkfish commented Nov 3, 2023

Uh oh!

Mytherin commented Nov 8, 2023

Uh oh!

Uh oh!