| <!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 | Maximum Performance with Minimum Storage: Data Compression in Druid</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 --> |
| |
| |
| <link rel="stylesheet" href="/css/blogs.css"> |
| |
| <div class="blog druid-header"> |
| <div class="row"> |
| <div class="col-md-8 col-md-offset-2"> |
| <div class="title-image-wrap"> |
| |
| <div class="title-spacer"></div> |
| <img class="title-image" src="http://metamarkets.com/wp-content/uploads/2012/09/Computer_Chip-470x3401-470x288.jpeg" alt="Maximum Performance with Minimum Storage: Data Compression in Druid"/> |
| |
| </div> |
| </div> |
| </div> |
| </div> |
| |
| <div class="container blog"> |
| <div class="row"> |
| <div class="col-md-8 col-md-offset-2"> |
| <div class="blog-entry"> |
| <h1>Maximum Performance with Minimum Storage: Data Compression in Druid</h1> |
| <p class="text-muted">by <span class="author text-uppercase">Fangjin Yang</span> · September 21, 2012</p> |
| |
| <p>The Metamarkets solution allows for arbitrary exploration of massive data sets. Powered by Druid, our in-house distributed data store and processor, users can filter time series and top list queries based on Boolean expressions of dimension values. Given that some of our dataset dimensions contain millions of unique values, the subset of things that may match a particular filter expression may be quite large. To design for these challenges, we needed a fast and accurate (not a fast and approximate) solution, and we once again found ourselves buried under a stack of papers, looking for an answer.</p> |
| |
| <h2 id="from-justin-bieber-to-ones-and-zeros">From Justin Bieber to Ones and Zeros</h2> |
| |
| <p>To better understand how Druid stores dimension values, consider the following data set: |
| <table border="1" cellspacing="0" cellpadding="5px"> |
| <tbody> |
| <tr> |
| <td valign="top" width="104">Timestamp</td> |
| <td valign="top" width="68">Publisher</td> |
| <td valign="top" width="52">Advertiser</td> |
| <td valign="top" width="49">Gender</td> |
| <td valign="top" width="50">Country</td> |
| <td valign="top" width="52">Impressions</td> |
| <td valign="top" width="48">Clicks</td> |
| <td valign="top" width="50">Revenue</td> |
| </tr> |
| <tr> |
| <td valign="top" width="104"> |
| <pre>2011-01-01T01:00:00Z</pre> |
| </td> |
| <td valign="top" width="68"> |
| <pre>bieberfever.com</pre> |
| </td> |
| <td valign="top" width="52"> |
| <pre>google.com</pre> |
| </td> |
| <td valign="top" width="49"> |
| <pre>Male</pre> |
| </td> |
| <td valign="top" width="50"> |
| <pre>USA</pre> |
| </td> |
| <td valign="top" width="52"> |
| <pre>1800</pre> |
| </td> |
| <td valign="top" width="48"> |
| <pre>25</pre> |
| </td> |
| <td valign="top" width="50"> |
| <pre>15.70</pre> |
| </td> |
| </tr> |
| <tr> |
| <td valign="top" width="104"> |
| <pre>2011-01-01T01:00:00Z</pre> |
| </td> |
| <td valign="top" width="68"> |
| <pre>bieberfever.com</pre> |
| </td> |
| <td valign="top" width="52"> |
| <pre>google.com</pre> |
| </td> |
| <td valign="top" width="49"> |
| <pre>Male</pre> |
| </td> |
| <td valign="top" width="50"> |
| <pre>USA</pre> |
| </td> |
| <td valign="top" width="52"> |
| <pre>2912</pre> |
| </td> |
| <td valign="top" width="48"> |
| <pre>42</pre> |
| </td> |
| <td valign="top" width="50"> |
| <pre>29.18</pre> |
| </td> |
| </tr> |
| <tr> |
| <td valign="top" width="104"> |
| <pre>2011-01-01T02:00:00Z</pre> |
| </td> |
| <td valign="top" width="68"> |
| <pre>ultratrimfast.com</pre> |
| </td> |
| <td valign="top" width="52"> |
| <pre>google.com</pre> |
| </td> |
| <td valign="top" width="49"> |
| <pre>Male</pre> |
| </td> |
| <td valign="top" width="50"> |
| <pre>USA</pre> |
| </td> |
| <td valign="top" width="52"> |
| <pre>1953</pre> |
| </td> |
| <td valign="top" width="48"> |
| <pre>17</pre> |
| </td> |
| <td valign="top" width="50"> |
| <pre>17.31</pre> |
| </td> |
| </tr> |
| <tr> |
| <td valign="top" width="104"> |
| <pre>2011-01-01T02:00:00Z</pre> |
| </td> |
| <td valign="top" width="68"> |
| <pre>ultratrimfast.com</pre> |
| </td> |
| <td valign="top" width="52"> |
| <pre>google.com</pre> |
| </td> |
| <td valign="top" width="49"> |
| <pre>Male</pre> |
| </td> |
| <td valign="top" width="50"> |
| <pre>USA</pre> |
| </td> |
| <td valign="top" width="52"> |
| <pre>3194</pre> |
| </td> |
| <td valign="top" width="48"> |
| <pre>170</pre> |
| </td> |
| <td valign="top" width="50"> |
| <pre>34.01</pre> |
| </td> |
| </tr> |
| </tbody> |
| </table></p> |
| |
| <p>Consider the publisher dimension (column) in the table above. For each unique publisher, we can form some representation indicating in which table rows a particular publisher is seen. We can store this information in a binary array where the array indices represent our rows. If a particular publisher is seen in a certain row, that array index is marked as ‘1’. For example:</p> |
| |
| <p>Bieberfever.com -> <code>[1, 2]</code> -> <code>[1][1][0][0]</code></p> |
| |
| <p>Ultratrimfast.com -> <code>[3, 4]</code> -> <code>[0][0][1][1]</code></p> |
| |
| <p>In the example above bieberfever.com is seen in rows 1 and 2. This mapping of dimension values to row indices forms an <a href="http://en.wikipedia.org/wiki/Inverted_index">inverted index</a> and is in fact how we store dimension information in Druid. If we want to know which rows contain bieberfever.com OR ultratrimfast.com, we can OR together the bieberfever.com and ultratrimfast.com arrays.</p> |
| |
| <p><code>[0][1][0][1] OR [1][0][1][0] = [1][1][1][1]</code></p> |
| |
| <p>This idea forms the basis of how to perform Boolean operations on large bitmap sets. A challenge still remains in that if each array consisted of millions or billions of entries and if we had to OR together millions of such arrays, performance can potentially become a major issue. Thankfully for us, most bitmap indices are either very sparse or very dense, which is something that can be leveraged for compression.</p> |
| |
| <p>Bit arrays, or bitmaps, are frequently employed in areas such as data warehousing and data mining to significantly reduce storage costs. Bitmap compression algorithms are a well-defined area of research and often utilize run-length encoding. Well known algorithms include Byte-aligned Bitmap Code, Word-Aligned Hybrid (WAH) code, and Partitioned Word-Aligned Hybrid (PWAH) compression.</p> |
| |
| <h2 id="a-concise-solution">A Concise Solution</h2> |
| |
| <p>Most word-aligned run-length encoding algorithms represent long sequences of ones and zeros in a single word. The word contains the length of the sequence and some information about whether it is a one fill or a zero fill. Sequences that contain a mixture of 0 and 1 bits are stored in 32 bit blocks known as literals. An example of word-aligned hybrid compression is shown below:</p> |
| |
| <p>Given a bitstream: <code>[10110...1][000...010][010...011]</code></p> |
| |
| <p>There are three separate 32 bit sequences in the bitstream.</p> |
| |
| <ol> |
| <li><p><code>[1]0110...1</code> - 31 "dirty" bits (a literal)</p></li> |
| <li><p><code>[00]0...010</code> - 31 x 2 zeros (a sequence of zeros)</p></li> |
| <li><p><code>[01]0...011</code> - 31 x 3 ones (a sequences of ones)</p></li> |
| </ol> |
| |
| <p><a href="http://ricerca.mat.uniroma3.it/users/colanton/docs/concise.pdf">Concise</a> bitmap compression introduces the concept of a mixed fill, where fills and literals can be represented in a single word. The author of the original Concise paper claims that Concise outperforms WAH by reducing the size of the compressed bitmaps by up to 50%. For mixed fill sequences, the first 2 bits indicate the type of fill (0 or 1). The next 5 bits can be used to indicate the position where bits flip from 0 to 1 or vice versa. An example of the Concise representation for the integer set {3, 5, 31-93, 1,024, 1,028, 1,040,187,422} is shown below:</p> |
| |
| <ol> |
| <li><p><code>[1]0...101000</code></p></li> |
| <li><p><code>[01][00000]0...01</code></p></li> |
| <li><p><code>[00][00001]0...11101</code></p></li> |
| <li><p><code>[1]0...100010</code></p></li> |
| <li><p><code>[00][00000]1...1011101</code></p></li> |
| <li><p><code>[1]10...0</code></p></li> |
| </ol> |
| |
| <h2 id="efficiency-at-scale">Efficiency at Scale</h2> |
| |
| <p>Although Concise compression can greatly reduce the size of resulting bitmaps, we still have the problem of performing efficient Boolean operations on top of a large number of Concise sets. Luckily, Concise sets share a very important property with other bitmap compression schemes: they can be operated on in their compressed form. The Boolean operations we care about are AND, OR, and NOT. The NOT operation is the most straightforward to implement. Literals are directly complemented and fills of zeros and ones are inverted. ANDing and ORing sets prove to be more challenging.</p> |
| |
| <p>Consider ORing two sets where one set is a long sequence of ones and the other set contains a shorter sequence of ones, a sequence of zeros, and some literals. If the sequence of ones in the first set is sufficiently long enough to encompass the second set, we don’t need to care about the second set at all (yay for Boolean logic!). Hence, when ORing sets, sequences of ones always have priority over sequences of zeros and literals. Similarly, a sequence of zeros can be ignored; the sequence contributes nothing to the overall Boolean logic. Extending this idea further with <em>n</em> sets, we can examine the first starting word of every set and determine if a one fill exists. If so, we can find the longest one fill and advance all the sets forward past this one fill. At this new stopping point, we repeat the search for the longest one fill. If no such fill exists, we search for all literals at that position, OR the literals together, and continue advancing forward. The same idea applies for ANDing sets, except now sequences of zeros have the highest priority. This pseudo-algorithm, combined with some additional logic to address mixed fills, was found to be sufficient to address our performance requirements.</p> |
| |
| <h2 id="results">Results</h2> |
| |
| <p>The following results were generated on a cc2.8xlarge system with a single thread, 2G heap, 512m young gen, and a forced GC between each run. The data set is a single day's worth of data collected from the <a href="https://dev.twitter.com/docs/streaming-apis/streams/public">Twitter garden hose</a> data stream. The data set contains 2, 272, 295 rows. The table below demonstrates a size comparison between Concise compressed sets and regular integer arrays for different dimensions. |
| <table border="1" cellspacing="0" cellpadding="5px"> |
| <tbody> |
| <tr> |
| <td valign="top" width="106">Dimension</td> |
| <td valign="top" width="93">Cardinality</td> |
| <td valign="top" width="94">Concise compressed size (bytes)</td> |
| <td valign="top" width="92">Integer array size (bytes)</td> |
| <td valign="top" width="94">Concise size as a % of integer array size</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">Has_mention</td> |
| <td valign="top" width="93">2</td> |
| <td valign="top" width="94">586,400</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">6.451627</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">Has_links</td> |
| <td valign="top" width="93">2</td> |
| <td valign="top" width="94">580,872</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">6.390808</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">Has_geo</td> |
| <td valign="top" width="93">2</td> |
| <td valign="top" width="94">144,004</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">1.584345</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">Is_retweet</td> |
| <td valign="top" width="93">2</td> |
| <td valign="top" width="94">584,592</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">6.431735</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">Is_viral</td> |
| <td valign="top" width="93">2</td> |
| <td valign="top" width="94">358,380</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">3.942930</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">User_lang</td> |
| <td valign="top" width="93">21</td> |
| <td valign="top" width="94">1,414,000</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">15.556959</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">User_time_zone</td> |
| <td valign="top" width="93">142</td> |
| <td valign="top" width="94">3,876,244</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">42.646795</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">URL_domain</td> |
| <td valign="top" width="93">31,165</td> |
| <td valign="top" width="94">1,562,428</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">17.189978</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">First_hashtag</td> |
| <td valign="top" width="93">100,728</td> |
| <td valign="top" width="94">1,837,144</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">20.212428</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">Rt_name</td> |
| <td valign="top" width="93">182,704</td> |
| <td valign="top" width="94">2,235,288</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">24.592846</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">Reply_to_name</td> |
| <td valign="top" width="93">620,421</td> |
| <td valign="top" width="94">5,673,504</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">62.420416</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">User_location</td> |
| <td valign="top" width="93">637,774</td> |
| <td valign="top" width="94">9,511,844</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">104.650188</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">User_mention_name</td> |
| <td valign="top" width="93">923,842</td> |
| <td valign="top" width="94">9,086,416</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">99.969590</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">User_name</td> |
| <td valign="top" width="93">1,784,369</td> |
| <td valign="top" width="94">16,000,028</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">176.033790</td> |
| </tr> |
| </tbody> |
| </table></p> |
| |
| <p>Total concise compressed size = 53, 451, 144 bytes</p> |
| |
| <p>Total integer array size = 127, 248, 520 bytes</p> |
| |
| <p>Overall, Concise compressed sets are about 42.005317% less than integer arrays.</p> |
| |
| <p>We also resorted the rows of the data set to maximize compression to see how the results would be affected.</p> |
| |
| <table border="1" cellspacing="0" cellpadding="5px"> |
| <tbody> |
| <tr> |
| <td valign="top" width="106">Dimension</td> |
| <td valign="top" width="93">Cardinality</td> |
| <td valign="top" width="94">Concise compressed size (bytes)</td> |
| <td valign="top" width="92">Integer array size (bytes)</td> |
| <td valign="top" width="94">Concise size as a % of integer array size</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">Has_mention</td> |
| <td valign="top" width="93">2</td> |
| <td valign="top" width="94">744</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">0.008186</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">Has_links</td> |
| <td valign="top" width="93">2</td> |
| <td valign="top" width="94">1,504</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">0.016547</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">Has_geo</td> |
| <td valign="top" width="93">2</td> |
| <td valign="top" width="94">2,840</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">0.031246</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">Is_retweet</td> |
| <td valign="top" width="93">2</td> |
| <td valign="top" width="94">1,616</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">0.017779</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">Is_viral</td> |
| <td valign="top" width="93">2</td> |
| <td valign="top" width="94">1,488</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">0.016371</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">User_lang</td> |
| <td valign="top" width="93">21</td> |
| <td valign="top" width="94">38,416</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">0.422656</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">User_time_zone</td> |
| <td valign="top" width="93">142</td> |
| <td valign="top" width="94">319,644</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">3.516753</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">URL_domain</td> |
| <td valign="top" width="93">31,165</td> |
| <td valign="top" width="94">700,752</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">7.709738</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">First_hashtag</td> |
| <td valign="top" width="93">100,728</td> |
| <td valign="top" width="94">1,505,292</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">16.561362</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">Rt_name</td> |
| <td valign="top" width="93">182,704</td> |
| <td valign="top" width="94">1,874,180</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">20.619902</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">Reply_to_name</td> |
| <td valign="top" width="93">620,421</td> |
| <td valign="top" width="94">5,404,108</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">59.456497</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">User_location</td> |
| <td valign="top" width="93">637,774</td> |
| <td valign="top" width="94">9,091,016</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">100.075340</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">User_mention_name</td> |
| <td valign="top" width="93">923,842</td> |
| <td valign="top" width="94">8,686,384</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">95.568401</td> |
| </tr> |
| <tr> |
| <td valign="top" width="106">User_name</td> |
| <td valign="top" width="93">1,784,369</td> |
| <td valign="top" width="94">16,204,900</td> |
| <td valign="top" width="92">9,089,180</td> |
| <td valign="top" width="94">178.287810</td> |
| </tr> |
| </tbody> |
| </table> |
| |
| <p>Total concise compressed size = 43,832,884 bytes</p> |
| |
| <p>Total integer array size = 127, 248, 520 bytes</p> |
| |
| <p>What is interesting to note is that after sorting, global compression only increased minimally. The total Concise set size to total integer array size is 34.448031%.</p> |
| |
| <p>To understand the performance implications of using Concise sets versus integer arrays, we choose several dimensions from our data set with varying cardinalities and generated Concise sets for every dimension value of every selected dimension. The histograms below indicate the size distribution of the generated Concise sets for a given dimension. Each test run randomly picked a given number of Concise sets and performed Boolean operations with them. Integer array representations of these Concise sets were then created and the same Boolean operations were run on the integer arrays. There were 100 runs per test case and the average run time required to perform a Boolean operation is shown for each dimension in the first of two tables below. The second table shows the performance results when the sets used in the Boolean operation alway include the largest (size) set of the dimension.</p> |
| |
| <h3 id="dimension-user_time_zone">Dimension: User_time_zone</h3> |
| |
| <p>Cardinality: 142</p> |
| |
| <p><img src="http://metamarkets.com/wp-content/uploads/2012/09/user_time_zone1-1024x768.png" alt="user_time_zone"></p> |
| |
| <table border="1" cellspacing="0" cellpadding="5px"> |
| <tbody> |
| <tr> |
| <td valign="top" width="96">Number of filter elements</td> |
| <td valign="top" width="96">OR operation with Concise set (ms)</td> |
| <td valign="top" width="96">OR operation with integer arrays (ms)</td> |
| <td valign="top" width="96">AND operations with Concise set (ms)</td> |
| <td valign="top" width="96">AND operation with integer arrays (ms)</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10</td> |
| <td valign="top" width="96">31</td> |
| <td valign="top" width="96">20</td> |
| <td valign="top" width="96">1</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25</td> |
| <td valign="top" width="96">66</td> |
| <td valign="top" width="96">53</td> |
| <td valign="top" width="96">2</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50</td> |
| <td valign="top" width="96">159</td> |
| <td valign="top" width="96">153</td> |
| <td valign="top" width="96">4</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">100</td> |
| <td valign="top" width="96">339</td> |
| <td valign="top" width="96">322</td> |
| <td valign="top" width="96">7</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| </tbody> |
| </table> |
| |
| <p>Always including the largest Concise set of the dimension:</p> |
| |
| <table border="1" cellspacing="0" cellpadding="5px"> |
| <tbody> |
| <tr> |
| <td valign="top" width="96">Number of filter elements</td> |
| <td valign="top" width="96">OR operation with Concise set (ms)</td> |
| <td valign="top" width="96">OR operation with integer arrays (ms)</td> |
| <td valign="top" width="96">AND operations with Concise set (ms)</td> |
| <td valign="top" width="96">AND operation with integer arrays (ms)</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10</td> |
| <td valign="top" width="96">44</td> |
| <td valign="top" width="96">77</td> |
| <td valign="top" width="96">1</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25</td> |
| <td valign="top" width="96">92</td> |
| <td valign="top" width="96">141</td> |
| <td valign="top" width="96">2</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50</td> |
| <td valign="top" width="96">184</td> |
| <td valign="top" width="96">223</td> |
| <td valign="top" width="96">4</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">100</td> |
| <td valign="top" width="96">398</td> |
| <td valign="top" width="96">419</td> |
| <td valign="top" width="96">8</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| </tbody> |
| </table> |
| |
| <p> </p> |
| |
| <h3 id="dimension-url_domain">Dimension: URL_domain</h3> |
| |
| <p>Cardinality: 31,165</p> |
| |
| <p><img src="http://metamarkets.com/wp-content/uploads/2012/09/url_domain-1024x768.png" alt="url_domain"></p> |
| |
| <table border="1" cellspacing="0" cellpadding="5px"> |
| <tbody> |
| <tr> |
| <td valign="top" width="96">Number of filter elements</td> |
| <td valign="top" width="96">OR operation with Concise set (ms)</td> |
| <td valign="top" width="96">OR operation with integer arrays (ms)</td> |
| <td valign="top" width="96">AND operations with Concise set (ms)</td> |
| <td valign="top" width="96">AND operation with integer arrays (ms)</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">2</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">100</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">1,000</td> |
| <td valign="top" width="96">8</td> |
| <td valign="top" width="96">24</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">1</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">5,000</td> |
| <td valign="top" width="96">54</td> |
| <td valign="top" width="96">132</td> |
| <td valign="top" width="96">3</td> |
| <td valign="top" width="96">57</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10,000</td> |
| <td valign="top" width="96">111</td> |
| <td valign="top" width="96">286</td> |
| <td valign="top" width="96">8</td> |
| <td valign="top" width="96">284</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25,000</td> |
| <td valign="top" width="96">348</td> |
| <td valign="top" width="96">779</td> |
| <td valign="top" width="96">22</td> |
| <td valign="top" width="96">1,925</td> |
| </tr> |
| </tbody> |
| </table> |
| |
| <p>Always including the largest Concise set of the dimension:</p> |
| |
| <table border="1" cellspacing="0" cellpadding="5px"> |
| <tbody> |
| <tr> |
| <td valign="top" width="96">Number of filter elements</td> |
| <td valign="top" width="96">OR operation with Concise set (ms)</td> |
| <td valign="top" width="96">OR operation with integer arrays (ms)</td> |
| <td valign="top" width="96">AND operations with Concise set (ms)</td> |
| <td valign="top" width="96">AND operation with integer arrays (ms)</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10</td> |
| <td valign="top" width="96">14</td> |
| <td valign="top" width="96">172</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25</td> |
| <td valign="top" width="96">17</td> |
| <td valign="top" width="96">242</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50</td> |
| <td valign="top" width="96">19</td> |
| <td valign="top" width="96">298</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">100</td> |
| <td valign="top" width="96">22</td> |
| <td valign="top" width="96">356</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">1,000</td> |
| <td valign="top" width="96">35</td> |
| <td valign="top" width="96">569</td> |
| <td valign="top" width="96">1</td> |
| <td valign="top" width="96">1</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">5,000</td> |
| <td valign="top" width="96">89</td> |
| <td valign="top" width="96">865</td> |
| <td valign="top" width="96">4</td> |
| <td valign="top" width="96">59</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10,000</td> |
| <td valign="top" width="96">158</td> |
| <td valign="top" width="96">1,050</td> |
| <td valign="top" width="96">9</td> |
| <td valign="top" width="96">289</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25,000</td> |
| <td valign="top" width="96">382</td> |
| <td valign="top" width="96">1,618</td> |
| <td valign="top" width="96">21</td> |
| <td valign="top" width="96">1,949</td> |
| </tr> |
| </tbody> |
| </table> |
| |
| <h3 id="dimension-rt_name">Dimension: RT_name</h3> |
| |
| <p>Cardinality: 182,704</p> |
| |
| <p><img src="http://metamarkets.com/wp-content/uploads/2012/09/rt_name1-1024x768.png" alt="rt_name"></p> |
| |
| <table border="1" cellspacing="0" cellpadding="5px"> |
| <tbody> |
| <tr> |
| <td valign="top" width="96">Number of filter elements</td> |
| <td valign="top" width="96">OR operation with Concise set (ms)</td> |
| <td valign="top" width="96">OR operation with integer arrays (ms)</td> |
| <td valign="top" width="96">AND operations with Concise set (ms)</td> |
| <td valign="top" width="96">AND operation with integer arrays (ms)</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">100</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">1,000</td> |
| <td valign="top" width="96">1</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">1</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">5,000</td> |
| <td valign="top" width="96">11</td> |
| <td valign="top" width="96">31</td> |
| <td valign="top" width="96">3</td> |
| <td valign="top" width="96">57</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10,000</td> |
| <td valign="top" width="96">25</td> |
| <td valign="top" width="96">68</td> |
| <td valign="top" width="96">7</td> |
| <td valign="top" width="96">284</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25,000</td> |
| <td valign="top" width="96">98</td> |
| <td valign="top" width="96">118</td> |
| <td valign="top" width="96">20</td> |
| <td valign="top" width="96">1,925</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50,000</td> |
| <td valign="top" width="96">224</td> |
| <td valign="top" width="96">292</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">100,000</td> |
| <td valign="top" width="96">521</td> |
| <td valign="top" width="96">727</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| </tbody> |
| </table> |
| |
| <p><strong>Note:</strong> for AND operations on 50,000+ items, our implementation of the array based approach produced StackOverflow exceptions. Instead of changing the implementation to something that didn't, we just decided not to do comparisons beyond that point.</p> |
| |
| <p>Always including the largest Concise set of the dimension:</p> |
| |
| <table border="1" cellspacing="0" cellpadding="5px"> |
| <tbody> |
| <tr> |
| <td valign="top" width="96">Number of filter elements</td> |
| <td valign="top" width="96">OR operation with Concise set (ms)</td> |
| <td valign="top" width="96">OR operation with integer arrays (ms)</td> |
| <td valign="top" width="96">AND operations with Concise set (ms)</td> |
| <td valign="top" width="96">AND operation with integer arrays (ms)</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10</td> |
| <td valign="top" width="96">14</td> |
| <td valign="top" width="96">168</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25</td> |
| <td valign="top" width="96">16</td> |
| <td valign="top" width="96">236</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50</td> |
| <td valign="top" width="96">18</td> |
| <td valign="top" width="96">289</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">100</td> |
| <td valign="top" width="96">20</td> |
| <td valign="top" width="96">348</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">1,000</td> |
| <td valign="top" width="96">29</td> |
| <td valign="top" width="96">551</td> |
| <td valign="top" width="96">1</td> |
| <td valign="top" width="96">1</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">5,000</td> |
| <td valign="top" width="96">44</td> |
| <td valign="top" width="96">712</td> |
| <td valign="top" width="96">4</td> |
| <td valign="top" width="96">59</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10,000</td> |
| <td valign="top" width="96">69</td> |
| <td valign="top" width="96">817</td> |
| <td valign="top" width="96">8</td> |
| <td valign="top" width="96">289</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25,000</td> |
| <td valign="top" width="96">161</td> |
| <td valign="top" width="96">986</td> |
| <td valign="top" width="96">20</td> |
| <td valign="top" width="96">1,949</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50,000</td> |
| <td valign="top" width="96">303</td> |
| <td valign="top" width="96">1,182</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| </tbody> |
| </table> |
| |
| <h3 id="dimension-user_location">Dimension: User_location</h3> |
| |
| <p>Cardinality: 637,774</p> |
| |
| <p><img src="http://metamarkets.com/wp-content/uploads/2012/09/user_location-1024x768.png" alt="user_location"></p> |
| |
| <table border="1" cellspacing="0" cellpadding="5px"> |
| <tbody> |
| <tr> |
| <td valign="top" width="96">Number of filter elements</td> |
| <td valign="top" width="96">OR operation with Concise set (ms)</td> |
| <td valign="top" width="96">OR operation with integer arrays (ms)</td> |
| <td valign="top" width="96">AND operations with Concise set (ms)</td> |
| <td valign="top" width="96">AND operation with integer arrays (ms)</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">100</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">1,000</td> |
| <td valign="top" width="96">2</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">1</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">5,000</td> |
| <td valign="top" width="96">15</td> |
| <td valign="top" width="96">7</td> |
| <td valign="top" width="96">3</td> |
| <td valign="top" width="96">57</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10,000</td> |
| <td valign="top" width="96">34</td> |
| <td valign="top" width="96">16</td> |
| <td valign="top" width="96">8</td> |
| <td valign="top" width="96">284</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25,000</td> |
| <td valign="top" width="96">138</td> |
| <td valign="top" width="96">54</td> |
| <td valign="top" width="96">21</td> |
| <td valign="top" width="96">1,927</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50,000</td> |
| <td valign="top" width="96">298</td> |
| <td valign="top" width="96">128</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">100,000</td> |
| <td valign="top" width="96">650</td> |
| <td valign="top" width="96">271</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">250,000</td> |
| <td valign="top" width="96">1,695</td> |
| <td valign="top" width="96">881</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">500,000</td> |
| <td valign="top" width="96">3,433</td> |
| <td valign="top" width="96">2,311</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| </tbody> |
| </table> |
| |
| <p>Always including the largest Concise set of the dimension: |
| <table border="1" cellspacing="0" cellpadding="5px"> |
| <tbody> |
| <tr> |
| <td valign="top" width="96">Number of filter elements</td> |
| <td valign="top" width="96">OR operation with Concise set (ms)</td> |
| <td valign="top" width="96">OR operation with integer arrays (ms)</td> |
| <td valign="top" width="96">AND operations with Concise set (ms)</td> |
| <td valign="top" width="96">AND operation with integer arrays (ms)</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10</td> |
| <td valign="top" width="96">14</td> |
| <td valign="top" width="96">47</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25</td> |
| <td valign="top" width="96">16</td> |
| <td valign="top" width="96">67</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50</td> |
| <td valign="top" width="96">18</td> |
| <td valign="top" width="96">80</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">100</td> |
| <td valign="top" width="96">20</td> |
| <td valign="top" width="96">97</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">1,000</td> |
| <td valign="top" width="96">29</td> |
| <td valign="top" width="96">153</td> |
| <td valign="top" width="96">1</td> |
| <td valign="top" width="96">1</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">5,000</td> |
| <td valign="top" width="96">48</td> |
| <td valign="top" width="96">206</td> |
| <td valign="top" width="96">4</td> |
| <td valign="top" width="96">59</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10,000</td> |
| <td valign="top" width="96">81</td> |
| <td valign="top" width="96">233</td> |
| <td valign="top" width="96">9</td> |
| <td valign="top" width="96">290</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25,000</td> |
| <td valign="top" width="96">190</td> |
| <td valign="top" width="96">294</td> |
| <td valign="top" width="96">21</td> |
| <td valign="top" width="96">1,958</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50,000</td> |
| <td valign="top" width="96">359</td> |
| <td valign="top" width="96">378</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| </tbody> |
| </table> |
| </p> |
| |
| <h3 id="dimension-user_name">Dimension: User_name</h3> |
| |
| <p>Cardinality: 1,784,369</p> |
| |
| <p><img src="http://metamarkets.com/wp-content/uploads/2012/09/user_name-1024x768.png" alt="user_name"></p> |
| |
| <table border="1" cellspacing="0" cellpadding="5px"> |
| <tbody> |
| <tr> |
| <td valign="top" width="96">Number of filter elements</td> |
| <td valign="top" width="96">OR operation with Concise set (ms)</td> |
| <td valign="top" width="96">OR operation with integer arrays (ms)</td> |
| <td valign="top" width="96">AND operations with Concise set (ms)</td> |
| <td valign="top" width="96">AND operation with integer arrays (ms)</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">100</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">1,000</td> |
| <td valign="top" width="96">1</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">1</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">5,000</td> |
| <td valign="top" width="96">7</td> |
| <td valign="top" width="96">2</td> |
| <td valign="top" width="96">3</td> |
| <td valign="top" width="96">57</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10,000</td> |
| <td valign="top" width="96">17</td> |
| <td valign="top" width="96">6</td> |
| <td valign="top" width="96">7</td> |
| <td valign="top" width="96">283</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25,000</td> |
| <td valign="top" width="96">74</td> |
| <td valign="top" width="96">19</td> |
| <td valign="top" width="96">21</td> |
| <td valign="top" width="96">1,928</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50,000</td> |
| <td valign="top" width="96">177</td> |
| <td valign="top" width="96">45</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">100,000</td> |
| <td valign="top" width="96">440</td> |
| <td valign="top" width="96">108</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">250,000</td> |
| <td valign="top" width="96">1,225</td> |
| <td valign="top" width="96">379</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">500,000</td> |
| <td valign="top" width="96">2,504</td> |
| <td valign="top" width="96">978</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">1,000,000</td> |
| <td valign="top" width="96">5,076</td> |
| <td valign="top" width="96">2,460</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">1,250,000</td> |
| <td valign="top" width="96">6,331</td> |
| <td valign="top" width="96">3,265</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">1,500,000</td> |
| <td valign="top" width="96">7,622</td> |
| <td valign="top" width="96">4,036</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">1,750,000</td> |
| <td valign="top" width="96">8,911</td> |
| <td valign="top" width="96">4,982</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| </tbody> |
| </table> |
| |
| <p>Always including the largest Concise set of the dimension: |
| <table border="1" cellspacing="0" cellpadding="5px"> |
| <tbody> |
| <tr> |
| <td valign="top" width="96">Number of filter elements</td> |
| <td valign="top" width="96">OR operation with Concise set (ms)</td> |
| <td valign="top" width="96">OR operation with integer arrays (ms)</td> |
| <td valign="top" width="96">AND operations with Concise set (ms)</td> |
| <td valign="top" width="96">AND operation with integer arrays (ms)</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">100</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">1,000</td> |
| <td valign="top" width="96">1</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">0</td> |
| <td valign="top" width="96">1</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">5,000</td> |
| <td valign="top" width="96">8</td> |
| <td valign="top" width="96">2</td> |
| <td valign="top" width="96">3</td> |
| <td valign="top" width="96">59</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">10,000</td> |
| <td valign="top" width="96">22</td> |
| <td valign="top" width="96">6</td> |
| <td valign="top" width="96">7</td> |
| <td valign="top" width="96">289</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">25,000</td> |
| <td valign="top" width="96">77</td> |
| <td valign="top" width="96">19</td> |
| <td valign="top" width="96">21</td> |
| <td valign="top" width="96">1,954</td> |
| </tr> |
| <tr> |
| <td valign="top" width="96">50,000</td> |
| <td valign="top" width="96">196</td> |
| <td valign="top" width="96">45</td> |
| <td valign="top" width="96">-</td> |
| <td valign="top" width="96">-</td> |
| </tr> |
| </tbody> |
| </table></p> |
| |
| </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="Download via Apache" href="https://www.apache.org/dyn/closer.cgi?path=/incubator/druid/0.16.1-incubating/apache-druid-0.16.1-incubating-bin.tar.gz" target="_blank"><span class="fas fa-feather"></span></a> ·  |
| <a title="GitHub" href="https://github.com/apache/incubator-druid" target="_blank"><span class="fab fa-github"></span></a> |
| </div> |
| <div class="text-center license"> |
| Copyright © 2019 <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 --> |
| |
| |
| </body> |
| </html> |
