Reservoir Sampling is broken since DuckDB 1.2.0 #18099
Description
What happens?
Reservoir Sampling should produce an even distribution. However, it does not any more since 1.2.0.
When selecting a sample of 10.000 out of a population of 1.200.000, I would expect the q25 to be around 300.000, the q50 around 600.000 and the q75 around 900.000. Average should be around 600.000, and std should be around 346.410, just as the command
summarize select * from generate_series(1,1200000);produces.
> ./duckdb_1.1.0 -c "summarize select * from generate_series(1,1200000) using sample 10000 (reservoir);"
┌─────────────────┬─────────────┬─────────┬─────────┬───────────────┬─────────────┬────────────────────┬─────────┬─────────┬─────────┬───────┬─────────────────┐
│ column_name │ column_type │ min │ max │ approx_unique │ avg │ std │ q25 │ q50 │ q75 │ count │ null_percentage │
│ varchar │ varchar │ varchar │ varchar │ int64 │ varchar │ varchar │ varchar │ varchar │ varchar │ int64 │ decimal(9,2) │
├─────────────────┼─────────────┼─────────┼─────────┼───────────────┼─────────────┼────────────────────┼─────────┼─────────┼─────────┼───────┼─────────────────┤
│ generate_series │ BIGINT │ 73 │ 1199910 │ 12169 │ 594016.1984 │ 345544.44324113464 │ 293730 │ 588378 │ 890812 │ 10000 │ 0.00 │
└─────────────────┴─────────────┴─────────┴─────────┴───────────────┴─────────────┴────────────────────┴─────────┴─────────┴─────────┴───────┴─────────────────┘
> ./duckdb_1.1.1 -c "summarize select * from generate_series(1,1200000) using sample 10000 (reservoir);"
┌─────────────────┬─────────────┬─────────┬─────────┬───────────────┬─────────────┬───────────────────┬─────────┬─────────┬─────────┬───────┬─────────────────┐
│ column_name │ column_type │ min │ max │ approx_unique │ avg │ std │ q25 │ q50 │ q75 │ count │ null_percentage │
│ varchar │ varchar │ varchar │ varchar │ int64 │ varchar │ varchar │ varchar │ varchar │ varchar │ int64 │ decimal(9,2) │
├─────────────────┼─────────────┼─────────┼─────────┼───────────────┼─────────────┼───────────────────┼─────────┼─────────┼─────────┼───────┼─────────────────┤
│ generate_series │ BIGINT │ 160 │ 1199819 │ 10191 │ 594876.8176 │ 347942.9143118587 │ 294726 │ 592051 │ 898651 │ 10000 │ 0.00 │
└─────────────────┴─────────────┴─────────┴─────────┴───────────────┴─────────────┴───────────────────┴─────────┴─────────┴─────────┴───────┴─────────────────┘
> ./duckdb_1.1.2 -c "summarize select * from generate_series(1,1200000) using sample 10000 (reservoir);"
┌─────────────────┬─────────────┬─────────┬─────────┬───────────────┬─────────────┬────────────────────┬─────────┬─────────┬─────────┬───────┬─────────────────┐
│ column_name │ column_type │ min │ max │ approx_unique │ avg │ std │ q25 │ q50 │ q75 │ count │ null_percentage │
│ varchar │ varchar │ varchar │ varchar │ int64 │ varchar │ varchar │ varchar │ varchar │ varchar │ int64 │ decimal(9,2) │
├─────────────────┼─────────────┼─────────┼─────────┼───────────────┼─────────────┼────────────────────┼─────────┼─────────┼─────────┼───────┼─────────────────┤
│ generate_series │ BIGINT │ 33 │ 1199833 │ 10579 │ 592255.4678 │ 349385.92327861814 │ 287417 │ 586943 │ 893554 │ 10000 │ 0.00 │
└─────────────────┴─────────────┴─────────┴─────────┴───────────────┴─────────────┴────────────────────┴─────────┴─────────┴─────────┴───────┴─────────────────┘
> ./duckdb_1.1.3 -c "summarize select * from generate_series(1,1200000) using sample 10000 (reservoir);"
┌─────────────────┬─────────────┬─────────┬─────────┬───────────────┬─────────────┬────────────────────┬─────────┬─────────┬─────────┬───────┬─────────────────┐
│ column_name │ column_type │ min │ max │ approx_unique │ avg │ std │ q25 │ q50 │ q75 │ count │ null_percentage │
│ varchar │ varchar │ varchar │ varchar │ int64 │ varchar │ varchar │ varchar │ varchar │ varchar │ int64 │ decimal(9,2) │
├─────────────────┼─────────────┼─────────┼─────────┼───────────────┼─────────────┼────────────────────┼─────────┼─────────┼─────────┼───────┼─────────────────┤
│ generate_series │ BIGINT │ 120 │ 1199969 │ 8910 │ 599432.3383 │ 349524.12191578175 │ 297941 │ 597088 │ 904125 │ 10000 │ 0.00 │
└─────────────────┴─────────────┴─────────┴─────────┴───────────────┴─────────────┴────────────────────┴─────────┴─────────┴─────────┴───────┴─────────────────┘
> ./duckdb_1.2.0 -c "summarize select * from generate_series(1,1200000) using sample 10000 (reservoir);"
┌─────────────────┬─────────────┬─────────┬─────────┬───────────────┬─────────────┬────────────────────┬─────────┬─────────┬─────────┬───────┬─────────────────┐
│ column_name │ column_type │ min │ max │ approx_unique │ avg │ std │ q25 │ q50 │ q75 │ count │ null_percentage │
│ varchar │ varchar │ varchar │ varchar │ int64 │ varchar │ varchar │ varchar │ varchar │ varchar │ int64 │ decimal(9,2) │
├─────────────────┼─────────────┼─────────┼─────────┼───────────────┼─────────────┼────────────────────┼─────────┼─────────┼─────────┼───────┼─────────────────┤
│ generate_series │ BIGINT │ 44 │ 1199880 │ 11455 │ 439595.6158 │ 380611.92529244424 │ 82794 │ 348709 │ 769615 │ 10000 │ 0.00 │
└─────────────────┴─────────────┴─────────┴─────────┴───────────────┴─────────────┴────────────────────┴─────────┴─────────┴─────────┴───────┴─────────────────┘
> ./duckdb_1.2.1 -c "summarize select * from generate_series(1,1200000) using sample 10000 (reservoir);"
┌─────────────────┬─────────────┬─────────┬─────────┬───────────────┬─────────────┬───────────────────┬─────────┬─────────┬─────────┬───────┬─────────────────┐
│ column_name │ column_type │ min │ max │ approx_unique │ avg │ std │ q25 │ q50 │ q75 │ count │ null_percentage │
│ varchar │ varchar │ varchar │ varchar │ int64 │ varchar │ varchar │ varchar │ varchar │ varchar │ int64 │ decimal(9,2) │
├─────────────────┼─────────────┼─────────┼─────────┼───────────────┼─────────────┼───────────────────┼─────────┼─────────┼─────────┼───────┼─────────────────┤
│ generate_series │ BIGINT │ 9 │ 1199774 │ 8725 │ 439430.5701 │ 381151.6789006531 │ 82639 │ 348478 │ 777180 │ 10000 │ 0.00 │
└─────────────────┴─────────────┴─────────┴─────────┴───────────────┴─────────────┴───────────────────┴─────────┴─────────┴─────────┴───────┴─────────────────┘
> ./duckdb_1.2.2 -c "summarize select * from generate_series(1,1200000) using sample 10000 (reservoir);"
┌─────────────────┬─────────────┬─────────┬─────────┬───────────────┬─────────────┬────────────────────┬─────────┬─────────┬─────────┬───────┬─────────────────┐
│ column_name │ column_type │ min │ max │ approx_unique │ avg │ std │ q25 │ q50 │ q75 │ count │ null_percentage │
│ varchar │ varchar │ varchar │ varchar │ int64 │ varchar │ varchar │ varchar │ varchar │ varchar │ int64 │ decimal(9,2) │
├─────────────────┼─────────────┼─────────┼─────────┼───────────────┼─────────────┼────────────────────┼─────────┼─────────┼─────────┼───────┼─────────────────┤
│ generate_series │ BIGINT │ 7 │ 1199923 │ 11784 │ 437985.6615 │ 382649.83346572827 │ 83885 │ 335826 │ 770429 │ 10000 │ 0.00 │
└─────────────────┴─────────────┴─────────┴─────────┴───────────────┴─────────────┴────────────────────┴─────────┴─────────┴─────────┴───────┴─────────────────┘
> ./duckdb_1.3.1 -c "summarize select * from generate_series(1,1200000) using sample 10000 (reservoir);"
┌─────────────────┬─────────────┬─────────┬─────────┬───────────────┬─────────────┬────────────────────┬─────────┬─────────┬─────────┬───────┬─────────────────┐
│ column_name │ column_type │ min │ max │ approx_unique │ avg │ std │ q25 │ q50 │ q75 │ count │ null_percentage │
│ varchar │ varchar │ varchar │ varchar │ int64 │ varchar │ varchar │ varchar │ varchar │ varchar │ int64 │ decimal(9,2) │
├─────────────────┼─────────────┼─────────┼─────────┼───────────────┼─────────────┼────────────────────┼─────────┼─────────┼─────────┼───────┼─────────────────┤
│ generate_series │ BIGINT │ 98 │ 1199807 │ 9774 │ 429680.5171 │ 379747.11901310633 │ 80385 │ 325108 │ 757635 │ 10000 │ 0.00 │
└─────────────────┴─────────────┴─────────┴─────────┴───────────────┴─────────────┴────────────────────┴─────────┴─────────┴─────────┴───────┴─────────────────┘
Nightly:
> ./duckdb -c "summarize select * from generate_series(1,1200000) using sample 10000 (reservoir);"
┌─────────────────┬─────────────┬─────────┬─────────┬───────────────┬─────────────┬───────────────────┬─────────┬─────────┬─────────┬───────┬─────────────────┐
│ column_name │ column_type │ min │ max │ approx_unique │ avg │ std │ q25 │ q50 │ q75 │ count │ null_percentage │
│ varchar │ varchar │ varchar │ varchar │ int64 │ varchar │ varchar │ varchar │ varchar │ varchar │ int64 │ decimal(9,2) │
├─────────────────┼─────────────┼─────────┼─────────┼───────────────┼─────────────┼───────────────────┼─────────┼─────────┼─────────┼───────┼─────────────────┤
│ generate_series │ BIGINT │ 4 │ 1199803 │ 9732 │ 432538.4575 │ 382967.5797989835 │ 79044 │ 321902 │ 763352 │ 10000 │ 0.00 │
└─────────────────┴─────────────┴─────────┴─────────┴───────────────┴─────────────┴───────────────────┴─────────┴─────────┴─────────┴───────┴─────────────────┘
As you can see, the q25 was around 300k until version 1.1.3 and after that, it goes down to around 80k. The std seams to be somehow OK, but the percentiles indicate that the lower ranges are oversampled?
To Reproduce
summarize select * from generate_series(1,1200000) using sample 10000 (reservoir);OS:
Linux
DuckDB Version:
1.3.1
DuckDB Client:
CLI
Hardware:
No response
Full Name:
Fabian Krüger
Affiliation:
IBIS Prof. Thome AG
What is the latest build you tested with? If possible, we recommend testing with the latest nightly build.
I have tested with a nightly build
Did you include all relevant data sets for reproducing the issue?
Yes
Did you include all code required to reproduce the issue?
- Yes, I have
Did you include all relevant configuration (e.g., CPU architecture, Python version, Linux distribution) to reproduce the issue?
- Yes, I have