| <!DOCTYPE html><html lang="en"><head><meta charSet="utf-8"/><meta http-equiv="X-UA-Compatible" content="IE=edge"/><title>DataSketches KLL Sketch module · Apache Druid</title><meta name="viewport" content="width=device-width, initial-scale=1.0"/><link rel="canonical" href="https://druid.apache.org/docs/26.0.0/development/extensions-core/datasketches-kll.html"/><meta name="generator" content="Docusaurus"/><meta name="description" content="<!--"/><meta name="docsearch:language" content="en"/><meta name="docsearch:version" content="26.0.0" /><meta property="og:title" content="DataSketches KLL Sketch module · Apache Druid"/><meta property="og:type" content="website"/><meta property="og:url" content="https://druid.apache.org/index.html"/><meta property="og:description" content="<!--"/><meta property="og:image" content="https://druid.apache.org/img/druid_nav.png"/><meta name="twitter:card" content="summary"/><meta name="twitter:image" content="https://druid.apache.org/img/druid_nav.png"/><link rel="shortcut icon" href="/img/favicon.png"/><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/docsearch.js@2/dist/cdn/docsearch.min.css"/><link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/styles/default.min.css"/><script async="" src="https://www.googletagmanager.com/gtag/js?id=UA-131010415-1"></script><script> |
| window.dataLayer = window.dataLayer || []; |
| function gtag(){dataLayer.push(arguments); } |
| gtag('js', new Date()); |
| gtag('config', 'UA-131010415-1'); |
| </script><link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.7.2/css/all.css"/><link rel="stylesheet" href="/css/code-block-buttons.css"/><script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/clipboard.js/2.0.4/clipboard.min.js"></script><script type="text/javascript" src="/js/code-block-buttons.js"></script><script src="/js/scrollSpy.js"></script><link rel="stylesheet" href="/css/main.css"/><script src="/js/codetabs.js"></script></head><body class="sideNavVisible separateOnPageNav"><div class="fixedHeaderContainer"><div class="headerWrapper wrapper"><header><a href="/"><img class="logo" src="/img/druid_nav.png" alt="Apache Druid"/></a><div class="navigationWrapper navigationSlider"><nav class="slidingNav"><ul class="nav-site nav-site-internal"><li class=""><a href="/technology" target="_self">Technology</a></li><li class=""><a href="/use-cases" target="_self">Use Cases</a></li><li class=""><a href="/druid-powered" target="_self">Powered By</a></li><li class=""><a href="/docs/26.0.0/design/index.html" target="_self">Docs</a></li><li class=""><a href="/community/" target="_self">Community</a></li><li class=""><a href="https://www.apache.org" target="_self">Apache</a></li><li class=""><a href="/downloads.html" target="_self">Download</a></li><li class="navSearchWrapper reactNavSearchWrapper"><input type="text" id="search_input_react" placeholder="Search" title="Search"/></li></ul></nav></div></header></div></div><div class="navPusher"><div class="docMainWrapper wrapper"><div class="container mainContainer docsContainer"><div class="wrapper"><div class="post"><header class="postHeader"><a class="edit-page-link button" href="https://github.com/apache/druid/edit/master/docs/development/extensions-core/datasketches-kll.md" target="_blank" rel="noreferrer noopener">Edit</a><h1 id="__docusaurus" class="postHeaderTitle">DataSketches KLL Sketch module</h1></header><article><div><span><!-- |
| ~ Licensed to the Apache Software Foundation (ASF) under one |
| ~ or more contributor license agreements. See the NOTICE file |
| ~ distributed with this work for additional information |
| ~ regarding copyright ownership. The ASF licenses this file |
| ~ to you under the Apache License, Version 2.0 (the |
| ~ "License"); you may not use this file except in compliance |
| ~ with the License. You may obtain a copy of the License at |
| ~ |
| ~ http://www.apache.org/licenses/LICENSE-2.0 |
| ~ |
| ~ Unless required by applicable law or agreed to in writing, |
| ~ software distributed under the License is distributed on an |
| ~ "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| ~ KIND, either express or implied. See the License for the |
| ~ specific language governing permissions and limitations |
| ~ under the License. |
| --> |
| <p>This module provides Apache Druid aggregators based on numeric quantiles KllFloatsSketch and KllDoublesSketch from <a href="https://datasketches.apache.org/">Apache DataSketches</a> library. KLL quantiles sketch is a mergeable streaming algorithm to estimate the distribution of values, and approximately answer queries about the rank of a value, probability mass function of the distribution (PMF) or histogram, cumulative distribution function (CDF), and quantiles (median, min, max, 95th percentile and such). See <a href="https://datasketches.apache.org/docs/Quantiles/QuantilesOverview">Quantiles Sketch Overview</a>. This document applies to both KllFloatsSketch and KllDoublesSketch. Only one of them will be used in the examples.</p> |
| <p>There are three major modes of operation:</p> |
| <ol> |
| <li>Ingesting sketches built outside of Druid (say, with Pig or Hive)</li> |
| <li>Building sketches from raw data during ingestion</li> |
| <li>Building sketches from raw data at query time</li> |
| </ol> |
| <p>To use this aggregator, make sure you <a href="/docs/26.0.0/development/extensions.html#loading-extensions">include</a> the extension in your config file:</p> |
| <pre><code class="hljs"><span class="hljs-attr">druid.extensions.loadList</span>=[<span class="hljs-string">"druid-datasketches"</span>] |
| </code></pre> |
| <p>For additional sketch types supported in Druid, see <a href="/docs/26.0.0/development/extensions-core/datasketches-extension.html">DataSketches extension</a>.</p> |
| <h2><a class="anchor" aria-hidden="true" id="aggregator"></a><a href="#aggregator" aria-hidden="true" class="hash-link"><svg class="hash-link-icon" aria-hidden="true" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a>Aggregator</h2> |
| <p>The result of the aggregation is a KllFloatsSketch or KllDoublesSketch that is the union of all sketches either built from raw data or read from the segments.</p> |
| <pre><code class="hljs css language-json">{ |
| <span class="hljs-attr">"type"</span> : <span class="hljs-string">"KllDoublesSketch"</span>, |
| <span class="hljs-attr">"name"</span> : <output_name>, |
| <span class="hljs-attr">"fieldName"</span> : <metric_name>, |
| <span class="hljs-attr">"k"</span>: <parameter that controls size and accuracy> |
| } |
| </code></pre> |
| <table> |
| <thead> |
| <tr><th>Property</th><th>Description</th><th>Required?</th></tr> |
| </thead> |
| <tbody> |
| <tr><td><code>type</code></td><td>Either "KllFloatsSketch" or "KllDoublesSketch"</td><td>yes</td></tr> |
| <tr><td><code>name</code></td><td>A String for the output (result) name of the calculation.</td><td>yes</td></tr> |
| <tr><td><code>fieldName</code></td><td>String for the name of the input field, which may contain sketches or raw numeric values.</td><td>yes</td></tr> |
| <tr><td><code>k</code></td><td>Parameter that determines the accuracy and size of the sketch. Higher k means higher accuracy but more space to store sketches. Must be from 8 to 65535. See <a href="https://datasketches.apache.org/docs/KLL/KLLAccuracyAndSize.html">KLL Sketch Accuracy and Size</a>.</td><td>no, defaults to 200</td></tr> |
| <tr><td><code>maxStreamLength</code></td><td>This parameter defines the number of items that can be presented to each sketch before it may need to move from off-heap to on-heap memory. This is relevant to query types that use off-heap memory, including <a href="/docs/26.0.0/querying/topnquery.html">TopN</a> and <a href="/docs/26.0.0/querying/groupbyquery.html">GroupBy</a>. Ideally, should be set high enough such that most sketches can stay off-heap.</td><td>no, defaults to 1000000000</td></tr> |
| </tbody> |
| </table> |
| <h2><a class="anchor" aria-hidden="true" id="post-aggregators"></a><a href="#post-aggregators" aria-hidden="true" class="hash-link"><svg class="hash-link-icon" aria-hidden="true" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a>Post aggregators</h2> |
| <h3><a class="anchor" aria-hidden="true" id="quantile"></a><a href="#quantile" aria-hidden="true" class="hash-link"><svg class="hash-link-icon" aria-hidden="true" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a>Quantile</h3> |
| <p>This returns an approximation to the value that would be preceded by a given fraction of a hypothetical sorted version of the input stream.</p> |
| <pre><code class="hljs css language-json">{ |
| "type" : "KllDoublesSketchToQuantile", |
| "name": <output name>, |
| "field" : <post aggregator that refers to a KllDoublesSketch (fieldAccess or another post aggregator)>, |
| "fraction" : <fractional position in the hypothetical sorted stream, number from 0 to 1 inclusive> |
| } |
| </code></pre> |
| <h3><a class="anchor" aria-hidden="true" id="quantiles"></a><a href="#quantiles" aria-hidden="true" class="hash-link"><svg class="hash-link-icon" aria-hidden="true" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a>Quantiles</h3> |
| <p>This returns an array of quantiles corresponding to a given array of fractions</p> |
| <pre><code class="hljs css language-json">{ |
| "type" : "KllDoublesSketchToQuantiles", |
| "name": <output name>, |
| "field" : <post aggregator that refers to a KllDoublesSketch (fieldAccess or another post aggregator)>, |
| "fractions" : <array of fractional positions in the hypothetical sorted stream, number from 0 to 1 inclusive> |
| } |
| </code></pre> |
| <h3><a class="anchor" aria-hidden="true" id="histogram"></a><a href="#histogram" aria-hidden="true" class="hash-link"><svg class="hash-link-icon" aria-hidden="true" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a>Histogram</h3> |
| <p>This returns an approximation to the histogram given an array of split points that define the histogram bins or a number of bins (not both). An array of <i>m</i> unique, monotonically increasing split points divide the real number line into <i>m+1</i> consecutive disjoint intervals. The definition of an interval is inclusive of the left split point and exclusive of the right split point. If the number of bins is specified instead of split points, the interval between the minimum and maximum values is divided into the given number of equally-spaced bins.</p> |
| <pre><code class="hljs css language-json">{ |
| "type" : "KllDoublesSketchToHistogram", |
| "name": <output name>, |
| "field" : <post aggregator that refers to a KllDoublesSketch (fieldAccess or another post aggregator)>, |
| "splitPoints" : <array of split points (optional)>, |
| "numBins" : <number of bins (optional, defaults to 10)> |
| } |
| </code></pre> |
| <h3><a class="anchor" aria-hidden="true" id="rank"></a><a href="#rank" aria-hidden="true" class="hash-link"><svg class="hash-link-icon" aria-hidden="true" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a>Rank</h3> |
| <p>This returns an approximation to the rank of a given value that is the fraction of the distribution less than that value.</p> |
| <pre><code class="hljs css language-json">{ |
| <span class="hljs-attr">"type"</span> : <span class="hljs-string">"KllDoublesSketchToRank"</span>, |
| <span class="hljs-attr">"name"</span>: <output name>, |
| <span class="hljs-attr">"field"</span> : <post aggregator that refers to a KllDoublesSketch (fieldAccess or another post aggregator)>, |
| <span class="hljs-attr">"value"</span> : <value> |
| } |
| </code></pre> |
| <h3><a class="anchor" aria-hidden="true" id="cdf"></a><a href="#cdf" aria-hidden="true" class="hash-link"><svg class="hash-link-icon" aria-hidden="true" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a>CDF</h3> |
| <p>This returns an approximation to the Cumulative Distribution Function given an array of split points that define the edges of the bins. An array of <i>m</i> unique, monotonically increasing split points divide the real number line into <i>m+1</i> consecutive disjoint intervals. The definition of an interval is inclusive of the left split point and exclusive of the right split point. The resulting array of fractions can be viewed as ranks of each split point with one additional rank that is always 1.</p> |
| <pre><code class="hljs css language-json">{ |
| <span class="hljs-attr">"type"</span> : <span class="hljs-string">"KllDoublesSketchToCDF"</span>, |
| <span class="hljs-attr">"name"</span>: <output name>, |
| <span class="hljs-attr">"field"</span> : <post aggregator that refers to a KllDoublesSketch (fieldAccess or another post aggregator)>, |
| <span class="hljs-attr">"splitPoints"</span> : <array of split points> |
| } |
| </code></pre> |
| <h3><a class="anchor" aria-hidden="true" id="sketch-summary"></a><a href="#sketch-summary" aria-hidden="true" class="hash-link"><svg class="hash-link-icon" aria-hidden="true" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a>Sketch Summary</h3> |
| <p>This returns a summary of the sketch that can be used for debugging. This is the result of calling toString() method.</p> |
| <pre><code class="hljs css language-json">{ |
| <span class="hljs-attr">"type"</span> : <span class="hljs-string">"KllDoublesSketchToString"</span>, |
| <span class="hljs-attr">"name"</span>: <output name>, |
| <span class="hljs-attr">"field"</span> : <post aggregator that refers to a KllDoublesSketch (fieldAccess or another post aggregator)> |
| } |
| </code></pre> |
| </span></div></article></div><div class="docs-prevnext"></div></div></div><nav class="onPageNav"><ul class="toc-headings"><li><a href="#aggregator">Aggregator</a></li><li><a href="#post-aggregators">Post aggregators</a><ul class="toc-headings"><li><a href="#quantile">Quantile</a></li><li><a href="#quantiles">Quantiles</a></li><li><a href="#histogram">Histogram</a></li><li><a href="#rank">Rank</a></li><li><a href="#cdf">CDF</a></li><li><a href="#sketch-summary">Sketch Summary</a></li></ul></li></ul></nav></div><footer class="nav-footer druid-footer" id="footer"><div class="container"><div class="text-center"><p><a href="/technology">Technology</a> · <a href="/use-cases">Use Cases</a> · <a href="/druid-powered">Powered by Druid</a> · <a href="/docs/26.0.0/">Docs</a> · <a href="/community/">Community</a> · <a href="/downloads.html">Download</a> · <a href="/faq">FAQ</a></p></div><div class="text-center"><a title="Join the user group" href="https://groups.google.com/forum/#!forum/druid-user" target="_blank"><span class="fa fa-comments"></span></a> · <a title="Follow Druid" href="https://twitter.com/druidio" target="_blank"><span class="fab fa-twitter"></span></a> · <a title="Download via Apache" href="https://www.apache.org/dyn/closer.cgi?path=/incubator/druid/{{ site.druid_versions[0].versions[0].version }}/apache-druid-{{ site.druid_versions[0].versions[0].version }}-bin.tar.gz" target="_blank"><span class="fas fa-feather"></span></a> · <a title="GitHub" href="https://github.com/apache/druid" target="_blank"><span class="fab fa-github"></span></a></div><div class="text-center license">Copyright © 2022 <a href="https://www.apache.org/" target="_blank">Apache Software Foundation</a>.<br/>Except where otherwise noted, licensed under <a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/">CC BY-SA 4.0</a>.<br/>Apache Druid, Druid, and the Druid logo are either registered trademarks or trademarks of The Apache Software Foundation in the United States and other countries.</div></div></footer></div><script type="text/javascript" src="https://cdn.jsdelivr.net/npm/docsearch.js@2/dist/cdn/docsearch.min.js"></script><script> |
| document.addEventListener('keyup', function(e) { |
| if (e.target !== document.body) { |
| return; |
| } |
| // keyCode for '/' (slash) |
| if (e.keyCode === 191) { |
| const search = document.getElementById('search_input_react'); |
| search && search.focus(); |
| } |
| }); |
| </script><script> |
| var search = docsearch({ |
| appId: 'CPK9PMSCEY', |
| apiKey: 'd4ef4ffe3a2f0c7d1e34b062fd98736b', |
| indexName: 'apache_druid', |
| inputSelector: '#search_input_react', |
| algoliaOptions: {"facetFilters":["language:en","version:26.0.0"]} |
| }); |
| </script></body></html> |
