DarkWanderer commented on PR #23851: URL: https://github.com/apache/datafusion/pull/23851#issuecomment-5306949059
Thanks for feedback @alamb Here is a benchmark on synthetic dataset mimicking the shape of observability traces data. The specific property that highlights the performance gain is - TraceIDs are pseudo-random (so stats-based pruning doesn't help), but are clustered in time. I imagine it would be applicable to any "needle in haystack" scan where the search key is clustered along sorting key. ## Wall-clock time Criterion, `measurement_time=20s`, `sample_size=10`. Reported as `[lower – mean – upper]` (95% CI). | query | variant | time | |---|---|---| | trace_lookup | stats_only | 139.07 – **139.77** – 140.59 ms | | trace_lookup | dictionary | 16.570 – **16.668** – 16.745 ms | | trace_lookup | bloom_filter | 26.027 – **26.206** – 26.383 ms | | trace_lookup | bloom_and_dictionary | 12.515 – **12.557** – 12.632 ms | | trace_lookup_in | stats_only | 145.01 – **145.52** – 146.43 ms | | trace_lookup_in | dictionary | 17.070 – **17.141** – 17.280 ms | | trace_lookup_in | bloom_filter | 119.48 – **120.15** – 120.93 ms | | trace_lookup_in | bloom_and_dictionary | 16.675 – **17.050** – 17.262 ms | | tenant_not_in | stats_only | 110.58 – **111.31** – 111.95 ms | | tenant_not_in | dictionary | 42.035 – **43.480** – 44.281 ms | | tenant_not_in | bloom_filter | 111.48 – **111.89** – 112.35 ms | | tenant_not_in | bloom_and_dictionary | 41.197 – **43.731** – 45.428 ms | Dictionary pruning is ~comparable to bloom filter in wall clock, but importantly, doesn't require extra writes; also, it can be used together with bloom filtering, compounding the win. More importantly, it allows better performance for "in" and "not in" scenarios which degrade bloom performance or cannot be handled at all respectively. ## Bytes read This measures the efficiency gain from more precise page pruning. This win is not fully highlighted by using local SSD - but in S3-backed object-store context, I expect that reduction to have a much more pronounced effect. | query | variant | row groups kept | bytes_scanned | index bytes | data pages | |---|---|---|---|---|---| | trace_lookup | stats_only | 64/64 | 383.09MiB | 0 | 383.09MiB | | trace_lookup | dictionary | **1**/64 | 8.12MiB | 2.13MiB (dict) | 5.99MiB | | trace_lookup | bloom_filter | 4/64 | 24.07MiB | 129.00KiB (bloom) | 23.94MiB | | trace_lookup | bloom_and_dictionary | 1/64 | 6.25MiB | n/a | n/a | | trace_lookup_in | stats_only | 64/64 | 383.09MiB | 0 | 383.09MiB | | trace_lookup_in | dictionary | **1**/64 | 8.12MiB | 2.13MiB (dict) | 5.99MiB | | trace_lookup_in | bloom_filter | 50/64 | 299.42MiB | 129.00KiB (bloom) | 299.29MiB | | trace_lookup_in | bloom_and_dictionary | 1/64 | 7.78MiB | n/a | n/a | | tenant_not_in | stats_only | 64/64 | 335.96MiB | 0 | 335.96MiB | | tenant_not_in | dictionary | 16/64 | 84.45MiB | 4.43KiB (dict) | 84.45MiB | | tenant_not_in | bloom_filter | 64/64 | 335.96MiB | 2.94KiB (bloom) | 335.96MiB | | tenant_not_in | bloom_and_dictionary | 16/64 | 84.45MiB | n/a | n/a | Grain of salt: this dataset mimics a very specific domain I was optimizing for, I am not sure how well the wins translate to general use cases. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
