| <!DOCTYPE html> |
| <html lang="en"> |
| <head> |
| <meta charset="UTF-8" /> |
| <meta name="viewport" content="width=device-width, initial-scale=1.0"> |
| <meta name="description" content="Apache Druid"> |
| <meta name="keywords" content="druid,kafka,database,analytics,streaming,real-time,real time,apache,open source"> |
| <meta name="author" content="Apache Software Foundation"> |
| |
| <title>Druid | Bloom Filter</title> |
| |
| <link rel="alternate" type="application/atom+xml" href="/feed"> |
| <link rel="shortcut icon" href="/img/favicon.png"> |
| |
| <link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.7.2/css/all.css" integrity="sha384-fnmOCqbTlWIlj8LyTjo7mOUStjsKC4pOpQbqyi7RrhN7udi9RwhKkMHpvLbHG9Sr" crossorigin="anonymous"> |
| |
| <link href='//fonts.googleapis.com/css?family=Open+Sans+Condensed:300,700,300italic|Open+Sans:300italic,400italic,600italic,400,300,600,700' rel='stylesheet' type='text/css'> |
| |
| <link rel="stylesheet" href="/css/bootstrap-pure.css?v=1.1"> |
| <link rel="stylesheet" href="/css/base.css?v=1.1"> |
| <link rel="stylesheet" href="/css/header.css?v=1.1"> |
| <link rel="stylesheet" href="/css/footer.css?v=1.1"> |
| <link rel="stylesheet" href="/css/syntax.css?v=1.1"> |
| <link rel="stylesheet" href="/css/docs.css?v=1.1"> |
| |
| <script> |
| (function() { |
| var cx = '000162378814775985090:molvbm0vggm'; |
| var gcse = document.createElement('script'); |
| gcse.type = 'text/javascript'; |
| gcse.async = true; |
| gcse.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + |
| '//cse.google.com/cse.js?cx=' + cx; |
| var s = document.getElementsByTagName('script')[0]; |
| s.parentNode.insertBefore(gcse, s); |
| })(); |
| </script> |
| |
| |
| </head> |
| |
| <body> |
| <!-- Start page_header include --> |
| <script src="//ajax.googleapis.com/ajax/libs/jquery/2.2.4/jquery.min.js"></script> |
| |
| <div class="top-navigator"> |
| <div class="container"> |
| <div class="left-cont"> |
| <a class="logo" href="/"><span class="druid-logo"></span></a> |
| </div> |
| <div class="right-cont"> |
| <ul class="links"> |
| <li class=""><a href="/technology">Technology</a></li> |
| <li class=""><a href="/use-cases">Use Cases</a></li> |
| <li class=""><a href="/druid-powered">Powered By</a></li> |
| <li class=""><a href="/docs/latest/design/">Docs</a></li> |
| <li class=""><a href="/community/">Community</a></li> |
| <li class="header-dropdown"> |
| <a>Apache</a> |
| <div class="header-dropdown-menu"> |
| <a href="https://www.apache.org/" target="_blank">Foundation</a> |
| <a href="https://www.apache.org/events/current-event" target="_blank">Events</a> |
| <a href="https://www.apache.org/licenses/" target="_blank">License</a> |
| <a href="https://www.apache.org/foundation/thanks.html" target="_blank">Thanks</a> |
| <a href="https://www.apache.org/security/" target="_blank">Security</a> |
| <a href="https://www.apache.org/foundation/sponsorship.html" target="_blank">Sponsorship</a> |
| </div> |
| </li> |
| <li class=" button-link"><a href="/downloads.html">Download</a></li> |
| </ul> |
| </div> |
| </div> |
| <div class="action-button menu-icon"> |
| <span class="fa fa-bars"></span> MENU |
| </div> |
| <div class="action-button menu-icon-close"> |
| <span class="fa fa-times"></span> MENU |
| </div> |
| </div> |
| |
| <script type="text/javascript"> |
| var $menu = $('.right-cont'); |
| var $menuIcon = $('.menu-icon'); |
| var $menuIconClose = $('.menu-icon-close'); |
| |
| function showMenu() { |
| $menu.fadeIn(100); |
| $menuIcon.fadeOut(100); |
| $menuIconClose.fadeIn(100); |
| } |
| |
| $menuIcon.click(showMenu); |
| |
| function hideMenu() { |
| $menu.fadeOut(100); |
| $menuIconClose.fadeOut(100); |
| $menuIcon.fadeIn(100); |
| } |
| |
| $menuIconClose.click(hideMenu); |
| |
| $(window).resize(function() { |
| if ($(window).width() >= 840) { |
| $menu.fadeIn(100); |
| $menuIcon.fadeOut(100); |
| $menuIconClose.fadeOut(100); |
| } |
| else { |
| $menu.fadeOut(100); |
| $menuIcon.fadeIn(100); |
| $menuIconClose.fadeOut(100); |
| } |
| }); |
| </script> |
| |
| <!-- Stop page_header include --> |
| |
| |
| <div class="container doc-container"> |
| |
| |
| |
| |
| <p> Looking for the <a href="/docs/0.20.0/">latest stable documentation</a>?</p> |
| |
| |
| <div class="row"> |
| <div class="col-md-9 doc-content"> |
| <p> |
| <a class="btn btn-default btn-xs visible-xs-inline-block visible-sm-inline-block" href="#toc">Table of Contents</a> |
| </p> |
| <!-- |
| ~ 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. |
| --> |
| |
| <h1 id="bloom-filter">Bloom Filter</h1> |
| |
| <p>This Apache Druid (incubating) extension adds the ability to both construct bloom filters from query results, and filter query results by testing |
| against a bloom filter. Make sure to <a href="../../operations/including-extensions.html">include</a> <code>druid-bloom-filter</code> as an |
| extension.</p> |
| |
| <p>A BloomFilter is a probabilistic data structure for performing a set membership check. A bloom filter is a good candidate |
| to use with Druid for cases where an explicit filter is impossible, e.g. filtering a query against a set of millions of |
| values.</p> |
| |
| <p>Following are some characteristics of BloomFilters: |
| - BloomFilters are highly space efficient when compared to using a HashSet. |
| - Because of the probabilistic nature of bloom filters, false positive results are possible (element was not actually |
| inserted into a bloom filter during construction, but <code>test()</code> says true) |
| - False negatives are not possible (if element is present then <code>test()</code> will never say false). |
| - The false positive probability of this implementation is currently fixed at 5%, but increasing the number of entries |
| that the filter can hold can decrease this false positive rate in exchange for overall size. |
| - Bloom filters are sensitive to number of elements that will be inserted in the bloom filter. During the creation of bloom filter expected number of entries must be specified. If the number of insertions exceed |
| the specified initial number of entries then false positive probability will increase accordingly.</p> |
| |
| <p>This extension is currently based on <code>org.apache.hive.common.util.BloomKFilter</code> from <code>hive-storage-api</code>. Internally, |
| this implementation uses Murmur3 as the hash algorithm.</p> |
| |
| <p>To construct a BloomKFilter externally with Java to use as a filter in a Druid query:</p> |
| <div class="highlight"><pre><code class="language-java" data-lang="java"><span></span><span class="n">BloomKFilter</span> <span class="n">bloomFilter</span> <span class="o">=</span> <span class="k">new</span> <span class="n">BloomKFilter</span><span class="o">(</span><span class="mi">1500</span><span class="o">);</span> |
| <span class="n">bloomFilter</span><span class="o">.</span><span class="na">addString</span><span class="o">(</span><span class="s">"value 1"</span><span class="o">);</span> |
| <span class="n">bloomFilter</span><span class="o">.</span><span class="na">addString</span><span class="o">(</span><span class="s">"value 2"</span><span class="o">);</span> |
| <span class="n">bloomFilter</span><span class="o">.</span><span class="na">addString</span><span class="o">(</span><span class="s">"value 3"</span><span class="o">);</span> |
| <span class="n">ByteArrayOutputStream</span> <span class="n">byteArrayOutputStream</span> <span class="o">=</span> <span class="k">new</span> <span class="n">ByteArrayOutputStream</span><span class="o">();</span> |
| <span class="n">BloomKFilter</span><span class="o">.</span><span class="na">serialize</span><span class="o">(</span><span class="n">byteArrayOutputStream</span><span class="o">,</span> <span class="n">bloomFilter</span><span class="o">);</span> |
| <span class="n">String</span> <span class="n">base64Serialized</span> <span class="o">=</span> <span class="n">Base64</span><span class="o">.</span><span class="na">encodeBase64String</span><span class="o">(</span><span class="n">byteArrayOutputStream</span><span class="o">.</span><span class="na">toByteArray</span><span class="o">());</span> |
| </code></pre></div> |
| <p>This string can then be used in the native or sql Druid query.</p> |
| |
| <h2 id="filtering-queries-with-a-bloom-filter">Filtering queries with a Bloom Filter</h2> |
| |
| <h3 id="json-specification-of-bloom-filter">JSON Specification of Bloom Filter</h3> |
| <div class="highlight"><pre><code class="language-json" data-lang="json"><span></span><span class="p">{</span> |
| <span class="nt">"type"</span> <span class="p">:</span> <span class="s2">"bloom"</span><span class="p">,</span> |
| <span class="nt">"dimension"</span> <span class="p">:</span> <span class="err"><dimension_name></span><span class="p">,</span> |
| <span class="nt">"bloomKFilter"</span> <span class="p">:</span> <span class="err"><serialized_bytes_for_BloomKFilter></span><span class="p">,</span> |
| <span class="nt">"extractionFn"</span> <span class="p">:</span> <span class="err"><extraction_fn></span> |
| <span class="p">}</span> |
| </code></pre></div> |
| <table><thead> |
| <tr> |
| <th>Property</th> |
| <th>Description</th> |
| <th>required?</th> |
| </tr> |
| </thead><tbody> |
| <tr> |
| <td><code>type</code></td> |
| <td>Filter Type. Should always be <code>bloom</code></td> |
| <td>yes</td> |
| </tr> |
| <tr> |
| <td><code>dimension</code></td> |
| <td>The dimension to filter over.</td> |
| <td>yes</td> |
| </tr> |
| <tr> |
| <td><code>bloomKFilter</code></td> |
| <td>Base64 encoded Binary representation of <code>org.apache.hive.common.util.BloomKFilter</code></td> |
| <td>yes</td> |
| </tr> |
| <tr> |
| <td><code>extractionFn</code></td> |
| <td><a href="../../querying/dimensionspecs.html#extraction-functions">Extraction function</a> to apply to the dimension values</td> |
| <td>no</td> |
| </tr> |
| </tbody></table> |
| |
| <h3 id="serialized-format-for-bloomkfilter">Serialized Format for BloomKFilter</h3> |
| |
| <p>Serialized BloomKFilter format:</p> |
| |
| <ul> |
| <li>1 byte for the number of hash functions.</li> |
| <li>1 big endian int(That is how OutputStream works) for the number of longs in the bitset</li> |
| <li>big endian longs in the BloomKFilter bitset</li> |
| </ul> |
| |
| <p>Note: <code>org.apache.hive.common.util.BloomKFilter</code> provides a serialize method which can be used to serialize bloom filters to outputStream.</p> |
| |
| <h3 id="filtering-sql-queries">Filtering SQL Queries</h3> |
| |
| <p>Bloom filters can be used in SQL <code>WHERE</code> clauses via the <code>bloom_filter_test</code> operator:</p> |
| <div class="highlight"><pre><code class="language-sql" data-lang="sql"><span></span><span class="k">SELECT</span> <span class="k">COUNT</span><span class="p">(</span><span class="o">*</span><span class="p">)</span> <span class="k">FROM</span> <span class="n">druid</span><span class="p">.</span><span class="n">foo</span> <span class="k">WHERE</span> <span class="n">bloom_filter_test</span><span class="p">(</span><span class="o"><</span><span class="n">expr</span><span class="o">></span><span class="p">,</span> <span class="s1">'<serialized_bytes_for_BloomKFilter>'</span><span class="p">)</span> |
| </code></pre></div> |
| <h3 id="expression-and-virtual-column-support">Expression and Virtual Column Support</h3> |
| |
| <p>The bloom filter extension also adds a bloom filter <a href="../../misc/math-expr.html">Druid expression</a> which shares syntax |
| with the SQL operator.</p> |
| <div class="highlight"><pre><code class="language-sql" data-lang="sql"><span></span><span class="n">bloom_filter_test</span><span class="p">(</span><span class="o"><</span><span class="n">expr</span><span class="o">></span><span class="p">,</span> <span class="s1">'<serialized_bytes_for_BloomKFilter>'</span><span class="p">)</span> |
| </code></pre></div> |
| <h2 id="bloom-filter-query-aggregator">Bloom Filter Query Aggregator</h2> |
| |
| <p>Input for a <code>bloomKFilter</code> can also be created from a druid query with the <code>bloom</code> aggregator. Note that it is very |
| important to set a reasonable value for the <code>maxNumEntries</code> parameter, which is the maximum number of distinct entries |
| that the bloom filter can represent without increasing the false postive rate. It may be worth performing a query using |
| one of the unique count sketches to calculate the value for this parameter in order to build a bloom filter appropriate |
| for the query. </p> |
| |
| <h3 id="json-specification-of-bloom-filter-aggregator">JSON Specification of Bloom Filter Aggregator</h3> |
| <div class="highlight"><pre><code class="language-json" data-lang="json"><span></span><span class="p">{</span> |
| <span class="nt">"type"</span><span class="p">:</span> <span class="s2">"bloom"</span><span class="p">,</span> |
| <span class="nt">"name"</span><span class="p">:</span> <span class="err"><output_field_name></span><span class="p">,</span> |
| <span class="nt">"maxNumEntries"</span><span class="p">:</span> <span class="err"><maximum_number_of_elements_for_BloomKFilter></span> |
| <span class="s2">"field"</span><span class="p">:</span> <span class="err"><dimension_spec></span> |
| <span class="p">}</span> |
| </code></pre></div> |
| <table><thead> |
| <tr> |
| <th>Property</th> |
| <th>Description</th> |
| <th>required?</th> |
| </tr> |
| </thead><tbody> |
| <tr> |
| <td><code>type</code></td> |
| <td>Aggregator Type. Should always be <code>bloom</code></td> |
| <td>yes</td> |
| </tr> |
| <tr> |
| <td><code>name</code></td> |
| <td>Output field name</td> |
| <td>yes</td> |
| </tr> |
| <tr> |
| <td><code>field</code></td> |
| <td><a href="../../querying/dimensionspecs.html">DimensionSpec</a> to add to <code>org.apache.hive.common.util.BloomKFilter</code></td> |
| <td>yes</td> |
| </tr> |
| <tr> |
| <td><code>maxNumEntries</code></td> |
| <td>Maximum number of distinct values supported by <code>org.apache.hive.common.util.BloomKFilter</code>, default <code>1500</code></td> |
| <td>no</td> |
| </tr> |
| </tbody></table> |
| |
| <h3 id="example">Example</h3> |
| <div class="highlight"><pre><code class="language-json" data-lang="json"><span></span><span class="p">{</span> |
| <span class="nt">"queryType"</span><span class="p">:</span> <span class="s2">"timeseries"</span><span class="p">,</span> |
| <span class="nt">"dataSource"</span><span class="p">:</span> <span class="s2">"wikiticker"</span><span class="p">,</span> |
| <span class="nt">"intervals"</span><span class="p">:</span> <span class="p">[</span> <span class="s2">"2015-09-12T00:00:00.000/2015-09-13T00:00:00.000"</span> <span class="p">],</span> |
| <span class="nt">"granularity"</span><span class="p">:</span> <span class="s2">"day"</span><span class="p">,</span> |
| <span class="nt">"aggregations"</span><span class="p">:</span> <span class="p">[</span> |
| <span class="p">{</span> |
| <span class="nt">"type"</span><span class="p">:</span> <span class="s2">"bloom"</span><span class="p">,</span> |
| <span class="nt">"name"</span><span class="p">:</span> <span class="s2">"userBloom"</span><span class="p">,</span> |
| <span class="nt">"maxNumEntries"</span><span class="p">:</span> <span class="mi">100000</span><span class="p">,</span> |
| <span class="nt">"field"</span><span class="p">:</span> <span class="p">{</span> |
| <span class="nt">"type"</span><span class="p">:</span><span class="s2">"default"</span><span class="p">,</span> |
| <span class="nt">"dimension"</span><span class="p">:</span><span class="s2">"user"</span><span class="p">,</span> |
| <span class="nt">"outputType"</span><span class="p">:</span> <span class="s2">"STRING"</span> |
| <span class="p">}</span> |
| <span class="p">}</span> |
| <span class="p">]</span> |
| <span class="p">}</span> |
| </code></pre></div> |
| <p>response</p> |
| <div class="highlight"><pre><code class="language-json" data-lang="json"><span></span><span class="p">[{</span><span class="nt">"timestamp"</span><span class="p">:</span><span class="s2">"2015-09-12T00:00:00.000Z"</span><span class="p">,</span><span class="nt">"result"</span><span class="p">:{</span><span class="nt">"userBloom"</span><span class="p">:</span><span class="s2">"BAAAJhAAAA..."</span><span class="p">}}]</span> |
| </code></pre></div> |
| <p>These values can then be set in the filter specification described above. </p> |
| |
| <p>Ordering results by a bloom filter aggregator, for example in a TopN query, will perform a comparatively expensive |
| linear scan <em>of the filter itself</em> to count the number of set bits as a means of approximating how many items have been |
| added to the set. As such, ordering by an alternate aggregation is recommended if possible. </p> |
| |
| <h3 id="sql-bloom-filter-aggregator">SQL Bloom Filter Aggregator</h3> |
| |
| <p>Bloom filters can be computed in SQL expressions with the <code>bloom_filter</code> aggregator:</p> |
| <div class="highlight"><pre><code class="language-sql" data-lang="sql"><span></span><span class="k">SELECT</span> <span class="n">BLOOM_FILTER</span><span class="p">(</span><span class="o"><</span><span class="n">expression</span><span class="o">></span><span class="p">,</span> <span class="o"><</span><span class="k">max</span> <span class="nb">number</span> <span class="k">of</span> <span class="n">entries</span><span class="o">></span><span class="p">)</span> <span class="k">FROM</span> <span class="n">druid</span><span class="p">.</span><span class="n">foo</span> <span class="k">WHERE</span> <span class="n">dim2</span> <span class="o">=</span> <span class="s1">'abc'</span> |
| </code></pre></div> |
| <p>but requires the setting <code>druid.sql.planner.serializeComplexValues</code> to be set to <code>true</code>. Bloom filter results in an SQL |
| response are serialized into a base64 string, which can then be used in subsequent queries as a filter.</p> |
| |
| </div> |
| <div class="col-md-3"> |
| <div class="searchbox"> |
| <gcse:searchbox-only></gcse:searchbox-only> |
| </div> |
| <div id="toc" class="nav toc hidden-print"> |
| </div> |
| </div> |
| </div> |
| </div> |
| |
| <!-- Start page_footer include --> |
| <footer class="druid-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/latest/">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="GitHub" href="https://github.com/apache/druid" target="_blank"><span class="fab fa-github"></span></a> |
| </div> |
| <div class="text-center license"> |
| Copyright © 2020 <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> |
| |
| <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> |
| <script> |
| function trackDownload(type, url) { |
| ga('send', 'event', 'download', type, url); |
| } |
| </script> |
| <script src="//code.jquery.com/jquery.min.js"></script> |
| <script src="//maxcdn.bootstrapcdn.com/bootstrap/3.2.0/js/bootstrap.min.js"></script> |
| <script src="/assets/js/druid.js"></script> |
| <!-- stop page_footer include --> |
| |
| |
| <script> |
| $(function() { |
| $(".toc").load("/docs/0.15.0-incubating/toc.html"); |
| |
| // There is no way to tell when .gsc-input will be async loaded into the page so just try to set a placeholder until it works |
| var tries = 0; |
| var timer = setInterval(function() { |
| tries++; |
| if (tries > 300) clearInterval(timer); |
| var searchInput = $('input.gsc-input'); |
| if (searchInput.length) { |
| searchInput.attr('placeholder', 'Search'); |
| clearInterval(timer); |
| } |
| }, 100); |
| }); |
| </script> |
| </body> |
| </html> |
