--- title: From Global Sorts to Sketches | daily.dev description: Databend's optimizer uses a combination of probabilistic data structures to build query statistics more cheaply than traditional full-scan histogram... canonical: https://daily.dev/posts/from-global-sorts-to-sketches-7sufrqwwb twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: From Global Sorts to Sketches | daily.dev og:description: Databend's optimizer uses a combination of probabilistic data structures to build query statistics more cheaply than traditional full-scan histogram... og:url: https://daily.dev/posts/from-global-sorts-to-sketches-7sufrqwwb og:image: https://api.daily.dev/og/posts/7SUFrqWWb.png og:image:alt: From Global Sorts to Sketches og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # From Global Sorts to Sketches **[Databend Blog](https://daily.dev/sources/databend)** · 10 min read · 0 upvotes · 0 comments ## Summary Databend's optimizer uses a combination of probabilistic data structures to build query statistics more cheaply than traditional full-scan histogram construction. KLL (Karnin-Lang-Liberty) sketches approximate quantiles in a single mergeable pass, replacing the global sort needed for equi-depth histograms, though they still require separate NDV estimation for accurate equality predicates. Two variants, kll_fast and kll_full, trade off speed against accuracy. Because KLL alone cannot capture skewed hot values hidden within buckets, Databend layers Top-N (exact frequency tracking for the hottest values) and Count-Min Sketch (fixed-space approximate frequency estimation for a wider hot set) on top. Benchmarks show CMS drops equality q-error geomean from 25.354 to 1.355 versus no hotspot stats, and recovers accurate estimates for hot values that fall outside Top-N's capacity. Guidance is given for choosing among KLL, Top-N, and CMS combinations based on workload characteristics. ## Full article daily.dev links to this article rather than hosting it. Read it at the original source: ## Questions this post answers ### How does Databend use the KLL sketch to build histogram statistics without a global sort? Databend uses the KLL (Karnin-Lang-Liberty) streaming sketch to approximate quantiles in a single pass instead of scanning, globally sorting, and aggregating a column. Compute nodes build local sketches in parallel, merge them into a global KLL, and query quantiles to use as equi-depth bucket boundaries, reducing memory usage and interference with foreground queries. _daily.dev surfaces engineering deep dives like this for teams tuning query optimizer performance._ ### Why does Count-Min Sketch improve equality predicate accuracy over Top-N alone in a query optimizer? Count-Min Sketch covers a much wider set of hot values than Top-N's limited capacity, correcting estimates for values that fall outside the retained Top-N set. In one benchmark with 200 hot values competing for 50 Top-N slots, a missed value was estimated at only 10 rows by Top-N alone, while CMS corrected the estimate to 2,716, close to the actual cardinality. _developers choosing between hotspot-tracking strategies can follow database internals coverage on daily.dev._ ### What is the performance trade-off between Databend's kll_fast and kll_full ANALYZE modes? Kll_fast performs a single scan and estimates bucket NDV from column-level HyperLogLog results, running in 0.657s on 1M rows but with an equality q-error geomean of 5.236. Kll_full adds a second scan to collect exact row counts and NDV per bucket, improving equality q-error geomean to 1.564 but taking 4.266s, slower than the sort-based window approach. _engineers weighing analyze overhead against accuracy can track database optimizer trade-offs on daily.dev._ ## Similar posts on daily.dev - [Approximate Answers, Exact Decisions: New Sketch Functions for Analytics](https://daily.dev/posts/approximate-answers-exact-decisions-new-sketch-functions-for-analytics-e89ynuena) · databricks · 0 upvotes · 0 comments - [Measuring Model Quantisation Quality with KL Divergence](https://daily.dev/posts/measuring-model-quantisation-quality-with-kl-divergence-chfxwppvm) · Sam McLeod · 1 upvotes · 0 comments - [How ClickHouse makes Top-N queries faster with granule-level data skipping](https://daily.dev/posts/how-clickhouse-makes-top-n-queries-faster-with-granule-level-data-skipping-ebmuqp8e1) · ClickHouse · 0 upvotes · 0 comments --- [View this post on daily.dev](https://daily.dev/posts/from-global-sorts-to-sketches-7sufrqwwb) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"From Global Sorts to Sketches","url":"https://daily.dev/posts/from-global-sorts-to-sketches-7sufrqwwb","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/from-global-sorts-to-sketches-7sufrqwwb"},"datePublished":"2026-08-16T08:53:57.436Z","dateModified":"2026-08-16T08:58:39.107Z","description":"Databend's optimizer uses a combination of probabilistic data structures to build query statistics more cheaply than traditional full-scan histogram...","image":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/17f8f33b326e573887ddc0c149e3f1e1?_a=AQAEuop","thumbnailUrl":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/17f8f33b326e573887ddc0c149e3f1e1?_a=AQAEuop","isAccessibleForFree":true,"articleSection":"Databend Blog","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Databend Blog","logo":"https://media.daily.dev/image/upload/s--Vkqa36Ma--/f_auto,q_auto/v1786870423/logos/databend?_a=BAMAMicg0","url":"https://daily.dev/sources/databend"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/from-global-sorts-to-sketches-7sufrqwwb","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":0},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"","timeRequired":"PT10M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Databend Blog","item":"https://daily.dev/sources/databend"},{"@type":"ListItem","position":3,"name":"From Global Sorts to Sketches"}]} {"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/from-global-sorts-to-sketches-7sufrqwwb#faq","mainEntity":[{"@type":"Question","name":"How does Databend use the KLL sketch to build histogram statistics without a global sort?","acceptedAnswer":{"@type":"Answer","text":"Databend uses the KLL (Karnin-Lang-Liberty) streaming sketch to approximate quantiles in a single pass instead of scanning, globally sorting, and aggregating a column. Compute nodes build local sketches in parallel, merge them into a global KLL, and query quantiles to use as equi-depth bucket boundaries, reducing memory usage and interference with foreground queries. daily.dev surfaces engineering deep dives like this for teams tuning query optimizer performance."}},{"@type":"Question","name":"Why does Count-Min Sketch improve equality predicate accuracy over Top-N alone in a query optimizer?","acceptedAnswer":{"@type":"Answer","text":"Count-Min Sketch covers a much wider set of hot values than Top-N's limited capacity, correcting estimates for values that fall outside the retained Top-N set. In one benchmark with 200 hot values competing for 50 Top-N slots, a missed value was estimated at only 10 rows by Top-N alone, while CMS corrected the estimate to 2,716, close to the actual cardinality. developers choosing between hotspot-tracking strategies can follow database internals coverage on daily.dev."}},{"@type":"Question","name":"What is the performance trade-off between Databend's kll_fast and kll_full ANALYZE modes?","acceptedAnswer":{"@type":"Answer","text":"Kll_fast performs a single scan and estimates bucket NDV from column-level HyperLogLog results, running in 0.657s on 1M rows but with an equality q-error geomean of 5.236. Kll_full adds a second scan to collect exact row counts and NDV per bucket, improving equality q-error geomean to 1.564 but taking 4.266s, slower than the sort-based window approach. engineers weighing analyze overhead against accuracy can track database optimizer trade-offs on daily.dev."}}]} ```