You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kylin.apache.org by li...@apache.org on 2016/08/04 06:02:20 UTC
svn commit: r1755142 [2/2] - in /kylin/site: blog/2016/08/ blog/2016/08/01/
blog/2016/08/01/count-distinct-in-kylin/
blog/2016/08/01/count-distinct-in-kylin/index.html blog/index.html feed.xml
Modified: kylin/site/feed.xml
URL: http://svn.apache.org/viewvc/kylin/site/feed.xml?rev=1755142&r1=1755141&r2=1755142&view=diff
==============================================================================
--- kylin/site/feed.xml (original)
+++ kylin/site/feed.xml Thu Aug 4 06:02:20 2016
@@ -19,11 +19,118 @@
<description>Apache Kylin Home</description>
<link>http://kylin.apache.org/</link>
<atom:link href="http://kylin.apache.org/feed.xml" rel="self" type="application/rss+xml"/>
- <pubDate>Fri, 29 Jul 2016 06:59:27 -0700</pubDate>
- <lastBuildDate>Fri, 29 Jul 2016 06:59:27 -0700</lastBuildDate>
+ <pubDate>Thu, 04 Aug 2016 06:59:16 -0700</pubDate>
+ <lastBuildDate>Thu, 04 Aug 2016 06:59:16 -0700</lastBuildDate>
<generator>Jekyll v2.5.3</generator>
<item>
+ <title>Use Count Distinct in Apache Kylin</title>
+ <description><p>Since v.1.5.3</p>
+
+<h2 id="background">Background</h2>
+<p>Count Distinct is a commonly measure in OLAP analyze, usually used for uv, etc. Apache Kylin offers two kinds of count distinct, approximately and precisely, differs on resource and performance.</p>
+
+<h2 id="approximately-count-distinct">Approximately Count Distinct</h2>
+<p>Apache Kylin implements approximately count distinct using HyperLogLog algorithm, offered serveral precision, with the error rates from 9.75% to 1.22%. <br />
+The result of measure has theorically upper limit in size, as 2^N bytes. For the max precision N=16, the upper limit is 64KB, and the max error rate is 1.22%. <br />
+This implementation’s pros is fast caculating and storage resource saving, but can’t be used for precisely requirements.</p>
+
+<h2 id="precisely-count-distinct">Precisely Count Distinct</h2>
+<p>Apache Kylin also implements precisely count distinct based on bitmap. For the data with type tiny int(byte), small int(short) and int, project the value into the bitmap directly. For the data with type long, string and others, encode the value as String into a dict, and project the dict id into the bitmap.<br />
+The result of measure is the serialized data of bitmap, not just the count value. This makes sure that the rusult is always right with any roll-up, even across segments.<br />
+This implementation’s pros is precesily result, without error, but needs more storage resources. One result size maybe hundreds of MB, when the count distinct value over millions.</p>
+
+<h2 id="global-dictionary">Global Dictionary</h2>
+<p>Apache Kylin encode value into dictionay at the segment level by default. That means one same value in different segments maybe encoded into different id, which means the result of precisely count distinct maybe not correct.<br />
+We introduced Global Dictionary with ensurance that one same value always encode into same id in different segments, to resolve this problem. Meanwhile, the capacity of dict has expanded dramatically, upper to support 2G values in one dict. It can also be used to replace default dictionary which has 5M values limitation.<br />
+Current version has no UI for global dictionary yet, and the cube desc json shoule be modified to enable it:</p>
+
+<div class="highlighter-rouge"><pre class="highlight"><code>"dictionaries": [
+ {
+ "column": "SUCPAY_USERID",
+ "reuse": "USER_ID",
+ "builder": "org.apache.kylin.dict.GlobalDictionaryBuilder"
+ }
+]
+</code></pre>
+</div>
+
+<p>The <code class="highlighter-rouge">column</code> means the column which to be encoded, the <code class="highlighter-rouge">builder</code> specifies the dictionary builder, only <code class="highlighter-rouge">org.apache.kylin.dict.GlobalDictionaryBuilder</code> is available for now.<br />
+The ‘reuse` is used to optimize the dict of more than one columns based on one dataset, please refer the next section ‘Example’ for more details.<br />
+The global dictionay can’t be used for dimensiion encoding for now, that means if one column is used for dimension and count distinct measure in one cube, the dimension encoding should be others but not dict.</p>
+
+<h2 id="example">Example</h2>
+<p>Here’s some example data:<br />
+| DT | USER_ID | FLAG1 | FLAG2 | USER_ID_FLAG1 | USER_ID_FLAG2 |<br />
+| :———-: | :——: | :—: | :—: | :————-: | :————-: |<br />
+| 2016-06-08 | AAA | 1 | 1 | AAA | AAA |<br />
+| 2016-06-08 | BBB | 1 | 1 | BBB | BBB |<br />
+| 2016-06-08 | CCC | 0 | 1 | NULL | CCC |<br />
+| 2016-06-09 | AAA | 0 | 1 | NULL | AAA |<br />
+| 2016-06-09 | CCC | 1 | 0 | CCC | NULL |<br />
+| 2016-06-10 | BBB | 0 | 1 | NULL | BBB |</p>
+
+<p>There’s basic columns <code class="highlighter-rouge">DT</code>, <code class="highlighter-rouge">USER_ID</code>, <code class="highlighter-rouge">FLAG1</code>, <code class="highlighter-rouge">FLAG2</code>, and condition columns <code class="highlighter-rouge">USER_ID_FLAG1=if(FLAG1=1,USER_ID,null)</code>, <code class="highlighter-rouge">USER_ID_FLAG2=if(FLAG2=1,USER_ID,null)</code>. Supposed the cube is builded by day, has 3 segments.</p>
+
+<p>Without the global dictionay, the precisely count distinct in semgent is correct, but the roll-up acrros segments result is wrong. Here’s an example:</p>
+
+<div class="highlighter-rouge"><pre class="highlight"><code>select count(distinct user_id_flag1) from table where dt in ('2016-06-08', '2016-06-09')
+</code></pre>
+</div>
+<p>The result is 2 but not 3. The reason is that the dict in 2016-06-08 segment is AAA=&gt;1, BBB=&gt;1, and the dict in 2016-06-09 segment is CCC=&gt; 1.<br />
+With global dictionary config as below, the dict became as AAA=&gt;1, BBB=&gt;2, CCC=&gt;3, that will procude correct result.<br />
+<code class="highlighter-rouge">
+"dictionaries": [
+ {
+ "column": "USER_ID_FLAG1",
+ "builder": "org.apache.kylin.dict.GlobalDictionaryBuilder"
+ }
+]
+</code></p>
+
+<p>Actually, the data of USER_ID_FLAG1 and USER_ID_FLAG2 both are a subset of USER_ID dataset, that made the dictionary re-using possible. Just encode the USER_ID dataset, and config USER_ID_FLAG1 and USER_ID_FLAG2 resue USER_ID dict:<br />
+<code class="highlighter-rouge">
+"dictionaries": [
+ {
+ "column": "USER_ID",
+ "builder": "org.apache.kylin.dict.GlobalDictionaryBuilder"
+ },
+ {
+ "column": "USER_ID_FLAG1",
+ "reuse": "USER_ID",
+ "builder": "org.apache.kylin.dict.GlobalDictionaryBuilder"
+ },
+ {
+ "column": "USER_ID_FLAG2",
+ "reuse": "USER_ID",
+ "builder": "org.apache.kylin.dict.GlobalDictionaryBuilder"
+ }
+]
+</code></p>
+
+<h2 id="performance-tunning">Performance Tunning</h2>
+<p>When using global dictionary and the dictionary is large, the step ‘Build Base Cuboid Data’ may took long time. That mainly caused by the dictionary cache loading and eviction cost, since the dictionary size is bigger than mapper memory size. To solve this problem, overwrite the cube configuration as following, adjust the mapper size to 8GB:<br />
+<code class="highlighter-rouge">
+kylin.job.mr.config.override.mapred.map.child.java.opts=-Xmx8g
+kylin.job.mr.config.override.mapreduce.map.memory.mb=8500
+</code></p>
+
+<h2 id="conclusions">Conclusions</h2>
+<p>Here’s some basically pricipal to decide which kind of count distinct will be used:<br />
+ - If the result with error rate is acceptable, approximately way is always an better way<br />
+ - If you need precisely result, the only way is precisely count distinct<br />
+ - If you don’t need roll-up across segments, or the column data type is tinyint/smallint/int, or the values count is less than 5M, just use default dictionary; otherwise the global dictionary should be configured, and consider the reuse column optimization</p>
+</description>
+ <pubDate>Mon, 01 Aug 2016 11:30:00 -0700</pubDate>
+ <link>http://kylin.apache.org/blog/2016/08/01/count-distinct-in-kylin/</link>
+ <guid isPermaLink="true">http://kylin.apache.org/blog/2016/08/01/count-distinct-in-kylin/</guid>
+
+
+ <category>blog</category>
+
+ </item>
+
+ <item>
<title>Apache Kylin v1.5.3 正式发布</title>
<description><p>Apache Kylin社区非常高兴宣布Apache Kylin v1.5.3正式发布。</p>
@@ -394,131 +501,6 @@ Check the regionserver log, there should
</item>
<item>
- <title>Apache Kylin v1.5.2 Release Announcement</title>
- <description><p>The Apache Kylin community is pleased to announce the release of Apache Kylin v1.5.2.</p>
-
-<p>Apache Kylin is an open source Distributed Analytics Engine designed to provide SQL interface and multi-dimensional analysis (OLAP) on Hadoop supporting extremely large datasets, original contributed from eBay Inc.</p>
-
-<p>To download Apache Kylin v1.5.2 source code or binary package:<br />
-please visit the <a href="http://kylin.apache.org/download">download</a> page.</p>
-
-<p>This is a major release which brings more stable, robust and well management version, Apache Kylin community resolved about 76 issues including bug fixes, improvements, and few new features.</p>
-
-<h2 id="change-highlights">Change Highlights</h2>
-
-<p><strong>New Feature</strong></p>
-
-<ul>
- <li>Count distinct on any dimension should work even not a predefined measure <a href="https://issues.apache.org/jira/browse/KYLIN-1016">KYLIN-1016</a></li>
- <li>Support Hive View as Lookup Table <a href="https://issues.apache.org/jira/browse/KYLIN-1077">KYLIN-1077</a></li>
- <li>Display time column as partition column <a href="https://issues.apache.org/jira/browse/KYLIN-1441">KYLIN-1441</a></li>
- <li>Make Kylin run on MapR <a href="https://issues.apache.org/jira/browse/KYLIN-1515">KYLIN-1515</a></li>
- <li>Download diagnosis zip from GUI <a href="https://issues.apache.org/jira/browse/KYLIN-1600">KYLIN-1600</a></li>
- <li>support kylin on cdh 5.7 <a href="https://issues.apache.org/jira/browse/KYLIN-1672">KYLIN-1672</a></li>
-</ul>
-
-<p><strong>Improvement</strong></p>
-
-<ul>
- <li>Enhance mail notification <a href="https://issues.apache.org/jira/browse/KYLIN-869">KYLIN-869</a></li>
- <li>HiveColumnCardinalityJob should use configurations in conf/kylin_job_conf.xml <a href="https://issues.apache.org/jira/browse/KYLIN-955">KYLIN-955</a></li>
- <li>Enable deriving dimensions on non PK/FK <a href="https://issues.apache.org/jira/browse/KYLIN-1313">KYLIN-1313</a></li>
- <li>Improve performance of converting data to hfile <a href="https://issues.apache.org/jira/browse/KYLIN-1323">KYLIN-1323</a></li>
- <li>Tools to extract all cube/hybrid/project related metadata to facilitate diagnosing/debugging/* sharing <a href="https://issues.apache.org/jira/browse/KYLIN-1340">KYLIN-1340</a></li>
- <li>change RealizationCapacity from three profiles to specific numbers <a href="https://issues.apache.org/jira/browse/KYLIN-1381">KYLIN-1381</a></li>
- <li>quicker and better response to v2 storage engine’s rpc timeout exception <a href="https://issues.apache.org/jira/browse/KYLIN-1391">KYLIN-1391</a></li>
- <li>Memory hungry cube should select LAYER and INMEM cubing smartly <a href="https://issues.apache.org/jira/browse/KYLIN-1418">KYLIN-1418</a></li>
- <li>For GUI, to add one option “yyyy-MM-dd HH:MM:ss” for Partition Date Column <a href="https://issues.apache.org/jira/browse/KYLIN-1432">KYLIN-1432</a></li>
- <li>cuboid sharding based on specific column <a href="https://issues.apache.org/jira/browse/KYLIN-1453">KYLIN-1453</a></li>
- <li>attach a hyperlink to introduce new aggregation group <a href="https://issues.apache.org/jira/browse/KYLIN-1487">KYLIN-1487</a></li>
- <li>Move query cache back to query controller level <a href="https://issues.apache.org/jira/browse/KYLIN-1526">KYLIN-1526</a></li>
- <li>Hfile owner is not hbase <a href="https://issues.apache.org/jira/browse/KYLIN-1542">KYLIN-1542</a></li>
- <li>Make hbase encoding and block size configurable just like hbase compression <a href="https://issues.apache.org/jira/browse/KYLIN-1544">KYLIN-1544</a></li>
- <li>Refactor storage engine(v2) to be extension friendly <a href="https://issues.apache.org/jira/browse/KYLIN-1561">KYLIN-1561</a></li>
- <li>Add and use a separate kylin_job_conf.xml for in-mem cubing <a href="https://issues.apache.org/jira/browse/KYLIN-1566">KYLIN-1566</a></li>
- <li>Front-end work for KYLIN-1557 <a href="https://issues.apache.org/jira/browse/KYLIN-1567">KYLIN-1567</a></li>
- <li>Coprocessor thread voluntarily stop itself when it reaches timeout <a href="https://issues.apache.org/jira/browse/KYLIN-1578">KYLIN-1578</a></li>
- <li>IT preparation classes like BuildCubeWithEngine should exit with status code upon build * exception <a href="https://issues.apache.org/jira/browse/KYLIN-1579">KYLIN-1579</a></li>
- <li>Use 1 byte instead of 8 bytes as column indicator in fact distinct MR job <a href="https://issues.apache.org/jira/browse/KYLIN-1580">KYLIN-1580</a></li>
- <li>Specify region cut size in cubedesc and leave the RealizationCapacity in model as a hint <a href="https://issues.apache.org/jira/browse/KYLIN-1584">KYLIN-1584</a></li>
- <li>make MAX_HBASE_FUZZY_KEYS in GTScanRangePlanner configurable <a href="https://issues.apache.org/jira/browse/KYLIN-1585">KYLIN-1585</a></li>
- <li>show cube level configuration overwrites properties in CubeDesigner <a href="https://issues.apache.org/jira/browse/KYLIN-1587">KYLIN-1587</a></li>
- <li>enabling different block size setting for small column families <a href="https://issues.apache.org/jira/browse/KYLIN-1591">KYLIN-1591</a></li>
- <li>Add “isShardBy” flag in rowkey panel <a href="https://issues.apache.org/jira/browse/KYLIN-1599">KYLIN-1599</a></li>
- <li>Need not to shrink scan cache when hbase rows can be large <a href="https://issues.apache.org/jira/browse/KYLIN-1601">KYLIN-1601</a></li>
- <li>User could dump hbase usage for diagnosis <a href="https://issues.apache.org/jira/browse/KYLIN-1602">KYLIN-1602</a></li>
- <li>Bring more information in diagnosis tool <a href="https://issues.apache.org/jira/browse/KYLIN-1614">KYLIN-1614</a></li>
- <li>Use deflate level 1 to enable compression “on the fly” <a href="https://issues.apache.org/jira/browse/KYLIN-1621">KYLIN-1621</a></li>
- <li>Make the hll precision for data samping configurable <a href="https://issues.apache.org/jira/browse/KYLIN-1623">KYLIN-1623</a></li>
- <li>HyperLogLogPlusCounter will become inaccurate when there’re billions of entries <a href="https://issues.apache.org/jira/browse/KYLIN-1624">KYLIN-1624</a></li>
- <li>GC log overwrites old one after restart Kylin service <a href="https://issues.apache.org/jira/browse/KYLIN-1625">KYLIN-1625</a></li>
- <li>add backdoor toggle to dump binary cube storage response for further analysis <a href="https://issues.apache.org/jira/browse/KYLIN-1627">KYLIN-1627</a></li>
-</ul>
-
-<p><strong>Bug</strong></p>
-
-<ul>
- <li>column width is too narrow for timestamp field <a href="https://issues.apache.org/jira/browse/KYLIN-989">KYLIN-989</a></li>
- <li>cube data not updated after purge <a href="https://issues.apache.org/jira/browse/KYLIN-1197">KYLIN-1197</a></li>
- <li>Can not get more than one system admin email in config <a href="https://issues.apache.org/jira/browse/KYLIN-1305">KYLIN-1305</a></li>
- <li>Should check and ensure TopN measure has two parameters specified <a href="https://issues.apache.org/jira/browse/KYLIN-1551">KYLIN-1551</a></li>
- <li>Unsafe check of initiated in HybridInstance#init() <a href="https://issues.apache.org/jira/browse/KYLIN-1563">KYLIN-1563</a></li>
- <li>Select any column when adding a custom aggregation in GUI <a href="https://issues.apache.org/jira/browse/KYLIN-1569">KYLIN-1569</a></li>
- <li>Unclosed ResultSet in QueryService#getMetadata() <a href="https://issues.apache.org/jira/browse/KYLIN-1574">KYLIN-1574</a></li>
- <li>NPE in Job engine when execute MR job <a href="https://issues.apache.org/jira/browse/KYLIN-1581">KYLIN-1581</a></li>
- <li>Agg group info will be blank when trying to edit cube <a href="https://issues.apache.org/jira/browse/KYLIN-1593">KYLIN-1593</a></li>
- <li>columns in metric could also be in filter/groupby <a href="https://issues.apache.org/jira/browse/KYLIN-1595">KYLIN-1595</a></li>
- <li>UT fail, due to String encoding CharsetEncoder mismatch <a href="https://issues.apache.org/jira/browse/KYLIN-1596">KYLIN-1596</a></li>
- <li>cannot run complete UT at windows dev machine <a href="https://issues.apache.org/jira/browse/KYLIN-1598">KYLIN-1598</a></li>
- <li>Concurrent write issue on hdfs when deploy coprocessor <a href="https://issues.apache.org/jira/browse/KYLIN-1604">KYLIN-1604</a></li>
- <li>Cube is ready but insight tables not result <a href="https://issues.apache.org/jira/browse/KYLIN-1612">KYLIN-1612</a></li>
- <li>UT ‘HiveCmdBuilderTest’ fail on ‘testBeeline’ <a href="https://issues.apache.org/jira/browse/KYLIN-1615">KYLIN-1615</a></li>
- <li>Can’t find any realization coursed by Top-N measure <a href="https://issues.apache.org/jira/browse/KYLIN-1619">KYLIN-1619</a></li>
- <li>sql not executed and report topN error <a href="https://issues.apache.org/jira/browse/KYLIN-1622">KYLIN-1622</a></li>
- <li>Web UI of TopN, “group by” column couldn’t be a dimension column <a href="https://issues.apache.org/jira/browse/KYLIN-1631">KYLIN-1631</a></li>
- <li>Unclosed OutputStream in SSHClient#scpFileToLocal() <a href="https://issues.apache.org/jira/browse/KYLIN-1634">KYLIN-1634</a></li>
- <li>Sample cube build error <a href="https://issues.apache.org/jira/browse/KYLIN-1637">KYLIN-1637</a></li>
- <li>Unclosed HBaseAdmin in ToolUtil#getHBaseMetaStoreId() <a href="https://issues.apache.org/jira/browse/KYLIN-1638">KYLIN-1638</a></li>
- <li>Wrong logging of JobID in MapReduceExecutable.java <a href="https://issues.apache.org/jira/browse/KYLIN-1639">KYLIN-1639</a></li>
- <li>Kylin’s hll counter count “NULL” as a value <a href="https://issues.apache.org/jira/browse/KYLIN-1643">KYLIN-1643</a></li>
- <li>Purge a cube, and then build again, the start date is not updated <a href="https://issues.apache.org/jira/browse/KYLIN-1647">KYLIN-1647</a></li>
- <li>java.io.IOException: Filesystem closed - in Cube Build Step 2 (MapR) <a href="https://issues.apache.org/jira/browse/KYLIN-1650">KYLIN-1650</a></li>
- <li>function name ‘getKylinPropertiesAsInputSteam’ misspelt <a href="https://issues.apache.org/jira/browse/KYLIN-1655">KYLIN-1655</a></li>
- <li>Streaming/kafka config not match with table name <a href="https://issues.apache.org/jira/browse/KYLIN-1660">KYLIN-1660</a></li>
- <li>tableName got truncated during request mapping for /tables/tableName <a href="https://issues.apache.org/jira/browse/KYLIN-1662">KYLIN-1662</a></li>
- <li>Should check project selection before add a stream table <a href="https://issues.apache.org/jira/browse/KYLIN-1666">KYLIN-1666</a></li>
- <li>Streaming table name should allow enter “DB.TABLE” format <a href="https://issues.apache.org/jira/browse/KYLIN-1667">KYLIN-1667</a></li>
- <li>make sure metadata in 1.5.2 compatible with 1.5.1 <a href="https://issues.apache.org/jira/browse/KYLIN-1673">KYLIN-1673</a></li>
- <li>MetaData clean just clean FINISHED and DISCARD jobs,but job correct status is SUCCEED <a href="https://issues.apache.org/jira/browse/KYLIN-1678">KYLIN-1678</a></li>
- <li>error happens while execute a sql contains ‘?’ using Statement <a href="https://issues.apache.org/jira/browse/KYLIN-1685">KYLIN-1685</a></li>
- <li>Illegal char on result dataset table <a href="https://issues.apache.org/jira/browse/KYLIN-1688">KYLIN-1688</a></li>
- <li>KylinConfigExt lost base properties when store into file <a href="https://issues.apache.org/jira/browse/KYLIN-1721">KYLIN-1721</a></li>
- <li>IntegerDimEnc serialization exception inside coprocessor <a href="https://issues.apache.org/jira/browse/KYLIN-1722">KYLIN-1722</a></li>
-</ul>
-
-<p><strong>Upgrade</strong></p>
-
-<p>Data and metadata of this version is back compatible with v1.5.1, but may need to <a href="/docs15/howto/howto_update_coprocessor.html">redeploy hbase coprocessor</a>.</p>
-
-<p><strong>Support</strong></p>
-
-<p>Any issue or question, please<br />
-open JIRA to Kylin project: <a href="https://issues.apache.org/jira/browse/KYLIN/">https://issues.apache.org/jira/browse/KYLIN/</a><br />
-or<br />
-send mail to Apache Kylin dev mailing list: <a href="&#109;&#097;&#105;&#108;&#116;&#111;:&#100;&#101;&#118;&#064;&#107;&#121;&#108;&#105;&#110;&#046;&#097;&#112;&#097;&#099;&#104;&#101;&#046;&#111;&#114;&#103;">&#100;&#101;&#118;&#064;&#107;&#121;&#108;&#105;&#110;&#046;&#097;&#112;&#097;&#099;&#104;&#101;&#046;&#111;&#114;&#103;</a></p>
-
-<p><em>Great thanks to everyone who contributed!</em></p>
-</description>
- <pubDate>Thu, 26 May 2016 08:00:00 -0700</pubDate>
- <link>http://kylin.apache.org/blog/2016/05/26/release-v1.5.2/</link>
- <guid isPermaLink="true">http://kylin.apache.org/blog/2016/05/26/release-v1.5.2/</guid>
-
-
- <category>blog</category>
-
- </item>
-
- <item>
<title>Apache Kylin v1.5.2 正式发布</title>
<description><p>Apache Kylin社区非常高兴宣布Apache Kylin v1.5.2正式发布。</p>
@@ -644,6 +626,131 @@ send mail to Apache Kylin dev mailing li
</item>
<item>
+ <title>Apache Kylin v1.5.2 Release Announcement</title>
+ <description><p>The Apache Kylin community is pleased to announce the release of Apache Kylin v1.5.2.</p>
+
+<p>Apache Kylin is an open source Distributed Analytics Engine designed to provide SQL interface and multi-dimensional analysis (OLAP) on Hadoop supporting extremely large datasets, original contributed from eBay Inc.</p>
+
+<p>To download Apache Kylin v1.5.2 source code or binary package:<br />
+please visit the <a href="http://kylin.apache.org/download">download</a> page.</p>
+
+<p>This is a major release which brings more stable, robust and well management version, Apache Kylin community resolved about 76 issues including bug fixes, improvements, and few new features.</p>
+
+<h2 id="change-highlights">Change Highlights</h2>
+
+<p><strong>New Feature</strong></p>
+
+<ul>
+ <li>Count distinct on any dimension should work even not a predefined measure <a href="https://issues.apache.org/jira/browse/KYLIN-1016">KYLIN-1016</a></li>
+ <li>Support Hive View as Lookup Table <a href="https://issues.apache.org/jira/browse/KYLIN-1077">KYLIN-1077</a></li>
+ <li>Display time column as partition column <a href="https://issues.apache.org/jira/browse/KYLIN-1441">KYLIN-1441</a></li>
+ <li>Make Kylin run on MapR <a href="https://issues.apache.org/jira/browse/KYLIN-1515">KYLIN-1515</a></li>
+ <li>Download diagnosis zip from GUI <a href="https://issues.apache.org/jira/browse/KYLIN-1600">KYLIN-1600</a></li>
+ <li>support kylin on cdh 5.7 <a href="https://issues.apache.org/jira/browse/KYLIN-1672">KYLIN-1672</a></li>
+</ul>
+
+<p><strong>Improvement</strong></p>
+
+<ul>
+ <li>Enhance mail notification <a href="https://issues.apache.org/jira/browse/KYLIN-869">KYLIN-869</a></li>
+ <li>HiveColumnCardinalityJob should use configurations in conf/kylin_job_conf.xml <a href="https://issues.apache.org/jira/browse/KYLIN-955">KYLIN-955</a></li>
+ <li>Enable deriving dimensions on non PK/FK <a href="https://issues.apache.org/jira/browse/KYLIN-1313">KYLIN-1313</a></li>
+ <li>Improve performance of converting data to hfile <a href="https://issues.apache.org/jira/browse/KYLIN-1323">KYLIN-1323</a></li>
+ <li>Tools to extract all cube/hybrid/project related metadata to facilitate diagnosing/debugging/* sharing <a href="https://issues.apache.org/jira/browse/KYLIN-1340">KYLIN-1340</a></li>
+ <li>change RealizationCapacity from three profiles to specific numbers <a href="https://issues.apache.org/jira/browse/KYLIN-1381">KYLIN-1381</a></li>
+ <li>quicker and better response to v2 storage engine’s rpc timeout exception <a href="https://issues.apache.org/jira/browse/KYLIN-1391">KYLIN-1391</a></li>
+ <li>Memory hungry cube should select LAYER and INMEM cubing smartly <a href="https://issues.apache.org/jira/browse/KYLIN-1418">KYLIN-1418</a></li>
+ <li>For GUI, to add one option “yyyy-MM-dd HH:MM:ss” for Partition Date Column <a href="https://issues.apache.org/jira/browse/KYLIN-1432">KYLIN-1432</a></li>
+ <li>cuboid sharding based on specific column <a href="https://issues.apache.org/jira/browse/KYLIN-1453">KYLIN-1453</a></li>
+ <li>attach a hyperlink to introduce new aggregation group <a href="https://issues.apache.org/jira/browse/KYLIN-1487">KYLIN-1487</a></li>
+ <li>Move query cache back to query controller level <a href="https://issues.apache.org/jira/browse/KYLIN-1526">KYLIN-1526</a></li>
+ <li>Hfile owner is not hbase <a href="https://issues.apache.org/jira/browse/KYLIN-1542">KYLIN-1542</a></li>
+ <li>Make hbase encoding and block size configurable just like hbase compression <a href="https://issues.apache.org/jira/browse/KYLIN-1544">KYLIN-1544</a></li>
+ <li>Refactor storage engine(v2) to be extension friendly <a href="https://issues.apache.org/jira/browse/KYLIN-1561">KYLIN-1561</a></li>
+ <li>Add and use a separate kylin_job_conf.xml for in-mem cubing <a href="https://issues.apache.org/jira/browse/KYLIN-1566">KYLIN-1566</a></li>
+ <li>Front-end work for KYLIN-1557 <a href="https://issues.apache.org/jira/browse/KYLIN-1567">KYLIN-1567</a></li>
+ <li>Coprocessor thread voluntarily stop itself when it reaches timeout <a href="https://issues.apache.org/jira/browse/KYLIN-1578">KYLIN-1578</a></li>
+ <li>IT preparation classes like BuildCubeWithEngine should exit with status code upon build * exception <a href="https://issues.apache.org/jira/browse/KYLIN-1579">KYLIN-1579</a></li>
+ <li>Use 1 byte instead of 8 bytes as column indicator in fact distinct MR job <a href="https://issues.apache.org/jira/browse/KYLIN-1580">KYLIN-1580</a></li>
+ <li>Specify region cut size in cubedesc and leave the RealizationCapacity in model as a hint <a href="https://issues.apache.org/jira/browse/KYLIN-1584">KYLIN-1584</a></li>
+ <li>make MAX_HBASE_FUZZY_KEYS in GTScanRangePlanner configurable <a href="https://issues.apache.org/jira/browse/KYLIN-1585">KYLIN-1585</a></li>
+ <li>show cube level configuration overwrites properties in CubeDesigner <a href="https://issues.apache.org/jira/browse/KYLIN-1587">KYLIN-1587</a></li>
+ <li>enabling different block size setting for small column families <a href="https://issues.apache.org/jira/browse/KYLIN-1591">KYLIN-1591</a></li>
+ <li>Add “isShardBy” flag in rowkey panel <a href="https://issues.apache.org/jira/browse/KYLIN-1599">KYLIN-1599</a></li>
+ <li>Need not to shrink scan cache when hbase rows can be large <a href="https://issues.apache.org/jira/browse/KYLIN-1601">KYLIN-1601</a></li>
+ <li>User could dump hbase usage for diagnosis <a href="https://issues.apache.org/jira/browse/KYLIN-1602">KYLIN-1602</a></li>
+ <li>Bring more information in diagnosis tool <a href="https://issues.apache.org/jira/browse/KYLIN-1614">KYLIN-1614</a></li>
+ <li>Use deflate level 1 to enable compression “on the fly” <a href="https://issues.apache.org/jira/browse/KYLIN-1621">KYLIN-1621</a></li>
+ <li>Make the hll precision for data samping configurable <a href="https://issues.apache.org/jira/browse/KYLIN-1623">KYLIN-1623</a></li>
+ <li>HyperLogLogPlusCounter will become inaccurate when there’re billions of entries <a href="https://issues.apache.org/jira/browse/KYLIN-1624">KYLIN-1624</a></li>
+ <li>GC log overwrites old one after restart Kylin service <a href="https://issues.apache.org/jira/browse/KYLIN-1625">KYLIN-1625</a></li>
+ <li>add backdoor toggle to dump binary cube storage response for further analysis <a href="https://issues.apache.org/jira/browse/KYLIN-1627">KYLIN-1627</a></li>
+</ul>
+
+<p><strong>Bug</strong></p>
+
+<ul>
+ <li>column width is too narrow for timestamp field <a href="https://issues.apache.org/jira/browse/KYLIN-989">KYLIN-989</a></li>
+ <li>cube data not updated after purge <a href="https://issues.apache.org/jira/browse/KYLIN-1197">KYLIN-1197</a></li>
+ <li>Can not get more than one system admin email in config <a href="https://issues.apache.org/jira/browse/KYLIN-1305">KYLIN-1305</a></li>
+ <li>Should check and ensure TopN measure has two parameters specified <a href="https://issues.apache.org/jira/browse/KYLIN-1551">KYLIN-1551</a></li>
+ <li>Unsafe check of initiated in HybridInstance#init() <a href="https://issues.apache.org/jira/browse/KYLIN-1563">KYLIN-1563</a></li>
+ <li>Select any column when adding a custom aggregation in GUI <a href="https://issues.apache.org/jira/browse/KYLIN-1569">KYLIN-1569</a></li>
+ <li>Unclosed ResultSet in QueryService#getMetadata() <a href="https://issues.apache.org/jira/browse/KYLIN-1574">KYLIN-1574</a></li>
+ <li>NPE in Job engine when execute MR job <a href="https://issues.apache.org/jira/browse/KYLIN-1581">KYLIN-1581</a></li>
+ <li>Agg group info will be blank when trying to edit cube <a href="https://issues.apache.org/jira/browse/KYLIN-1593">KYLIN-1593</a></li>
+ <li>columns in metric could also be in filter/groupby <a href="https://issues.apache.org/jira/browse/KYLIN-1595">KYLIN-1595</a></li>
+ <li>UT fail, due to String encoding CharsetEncoder mismatch <a href="https://issues.apache.org/jira/browse/KYLIN-1596">KYLIN-1596</a></li>
+ <li>cannot run complete UT at windows dev machine <a href="https://issues.apache.org/jira/browse/KYLIN-1598">KYLIN-1598</a></li>
+ <li>Concurrent write issue on hdfs when deploy coprocessor <a href="https://issues.apache.org/jira/browse/KYLIN-1604">KYLIN-1604</a></li>
+ <li>Cube is ready but insight tables not result <a href="https://issues.apache.org/jira/browse/KYLIN-1612">KYLIN-1612</a></li>
+ <li>UT ‘HiveCmdBuilderTest’ fail on ‘testBeeline’ <a href="https://issues.apache.org/jira/browse/KYLIN-1615">KYLIN-1615</a></li>
+ <li>Can’t find any realization coursed by Top-N measure <a href="https://issues.apache.org/jira/browse/KYLIN-1619">KYLIN-1619</a></li>
+ <li>sql not executed and report topN error <a href="https://issues.apache.org/jira/browse/KYLIN-1622">KYLIN-1622</a></li>
+ <li>Web UI of TopN, “group by” column couldn’t be a dimension column <a href="https://issues.apache.org/jira/browse/KYLIN-1631">KYLIN-1631</a></li>
+ <li>Unclosed OutputStream in SSHClient#scpFileToLocal() <a href="https://issues.apache.org/jira/browse/KYLIN-1634">KYLIN-1634</a></li>
+ <li>Sample cube build error <a href="https://issues.apache.org/jira/browse/KYLIN-1637">KYLIN-1637</a></li>
+ <li>Unclosed HBaseAdmin in ToolUtil#getHBaseMetaStoreId() <a href="https://issues.apache.org/jira/browse/KYLIN-1638">KYLIN-1638</a></li>
+ <li>Wrong logging of JobID in MapReduceExecutable.java <a href="https://issues.apache.org/jira/browse/KYLIN-1639">KYLIN-1639</a></li>
+ <li>Kylin’s hll counter count “NULL” as a value <a href="https://issues.apache.org/jira/browse/KYLIN-1643">KYLIN-1643</a></li>
+ <li>Purge a cube, and then build again, the start date is not updated <a href="https://issues.apache.org/jira/browse/KYLIN-1647">KYLIN-1647</a></li>
+ <li>java.io.IOException: Filesystem closed - in Cube Build Step 2 (MapR) <a href="https://issues.apache.org/jira/browse/KYLIN-1650">KYLIN-1650</a></li>
+ <li>function name ‘getKylinPropertiesAsInputSteam’ misspelt <a href="https://issues.apache.org/jira/browse/KYLIN-1655">KYLIN-1655</a></li>
+ <li>Streaming/kafka config not match with table name <a href="https://issues.apache.org/jira/browse/KYLIN-1660">KYLIN-1660</a></li>
+ <li>tableName got truncated during request mapping for /tables/tableName <a href="https://issues.apache.org/jira/browse/KYLIN-1662">KYLIN-1662</a></li>
+ <li>Should check project selection before add a stream table <a href="https://issues.apache.org/jira/browse/KYLIN-1666">KYLIN-1666</a></li>
+ <li>Streaming table name should allow enter “DB.TABLE” format <a href="https://issues.apache.org/jira/browse/KYLIN-1667">KYLIN-1667</a></li>
+ <li>make sure metadata in 1.5.2 compatible with 1.5.1 <a href="https://issues.apache.org/jira/browse/KYLIN-1673">KYLIN-1673</a></li>
+ <li>MetaData clean just clean FINISHED and DISCARD jobs,but job correct status is SUCCEED <a href="https://issues.apache.org/jira/browse/KYLIN-1678">KYLIN-1678</a></li>
+ <li>error happens while execute a sql contains ‘?’ using Statement <a href="https://issues.apache.org/jira/browse/KYLIN-1685">KYLIN-1685</a></li>
+ <li>Illegal char on result dataset table <a href="https://issues.apache.org/jira/browse/KYLIN-1688">KYLIN-1688</a></li>
+ <li>KylinConfigExt lost base properties when store into file <a href="https://issues.apache.org/jira/browse/KYLIN-1721">KYLIN-1721</a></li>
+ <li>IntegerDimEnc serialization exception inside coprocessor <a href="https://issues.apache.org/jira/browse/KYLIN-1722">KYLIN-1722</a></li>
+</ul>
+
+<p><strong>Upgrade</strong></p>
+
+<p>Data and metadata of this version is back compatible with v1.5.1, but may need to <a href="/docs15/howto/howto_update_coprocessor.html">redeploy hbase coprocessor</a>.</p>
+
+<p><strong>Support</strong></p>
+
+<p>Any issue or question, please<br />
+open JIRA to Kylin project: <a href="https://issues.apache.org/jira/browse/KYLIN/">https://issues.apache.org/jira/browse/KYLIN/</a><br />
+or<br />
+send mail to Apache Kylin dev mailing list: <a href="&#109;&#097;&#105;&#108;&#116;&#111;:&#100;&#101;&#118;&#064;&#107;&#121;&#108;&#105;&#110;&#046;&#097;&#112;&#097;&#099;&#104;&#101;&#046;&#111;&#114;&#103;">&#100;&#101;&#118;&#064;&#107;&#121;&#108;&#105;&#110;&#046;&#097;&#112;&#097;&#099;&#104;&#101;&#046;&#111;&#114;&#103;</a></p>
+
+<p><em>Great thanks to everyone who contributed!</em></p>
+</description>
+ <pubDate>Thu, 26 May 2016 08:00:00 -0700</pubDate>
+ <link>http://kylin.apache.org/blog/2016/05/26/release-v1.5.2/</link>
+ <guid isPermaLink="true">http://kylin.apache.org/blog/2016/05/26/release-v1.5.2/</guid>
+
+
+ <category>blog</category>
+
+ </item>
+
+ <item>
<title>Apache Kylin v1.5.1 正式发布</title>
<description><p>Apache Kylin社区非常高兴宣布Apache Kylin v1.5.1正式发布。</p>
@@ -816,397 +923,6 @@ send mail to Apache Kylin dev mailing li
<category>blog</category>
-
- </item>
-
- <item>
- <title>Approximate Top-N support in Kylin</title>
- <description><h2 id="background">Background</h2>
-
-<p>Find the Top-N (or Top-K) entities from a dataset is a common scenario and requirement in data minding; We often see the reports or news like “Top 100 companies in the world”, “Most popular 20 electronics” sold on a big e-commerce platform, etc. Exploring and analysising the top entities can always find some high value information.</p>
-
-<p>Within the era of big data, this need is much stronger than ever before, as both the raw dataset and the number of entities can be vast; Without certain pre-calculation, get the Top-K entities among a distributed big dataset may take a long time, makes the ad-hoc query inefficient.</p>
-
-<p>In v1.5.0, Apache Kylin introduces the “Top-N” measure, aiming to pre-calculate the top entities during the cube build phase; in the query phase, Kylin can quickly fetch and return the top records. The performance would be much better than a cube without “Top-N”, giving the analyst more power to inspect data.</p>
-
-<p>Please note, this “Top-N” measure is an approximate realization, to use it well you need have a good understanding with the algorithm as well as the data distribution.</p>
-
-<h2 id="top-n-query">Top-N query</h2>
-
-<p>Let’s start with the sample table that shipped in Kylin binary package. If you haven’t run that, follow this tutorial to create it: <a href="https://kylin.apache.org/docs15/tutorial/kylin_sample.html">Quick Start with Sample Cube</a>.</p>
-
-<p>The sample fact table “default.kylin_sales” mock the transactions on an online marketplace. It has a couple of dimension and measure columns. To be simple, here we only use four: “PART_DT”, “LSTG_SITE_ID”, “SELLER_ID” and “PRICE”. Bellow table is the concept of these columns, with a rough cardinality, the “SELLER_ID” is a high cardinality column.</p>
-
-<table>
- <thead>
- <tr>
- <th style="text-align: left">Column</th>
- <th style="text-align: center">Description</th>
- <th style="text-align: center">Cardinality</th>
- </tr>
- </thead>
- <tbody>
- <tr>
- <td style="text-align: left">PART_DT</td>
- <td style="text-align: center">Transaction Date</td>
- <td style="text-align: center">730: two years</td>
- </tr>
- <tr>
- <td style="text-align: left">LSTG_SITE_ID</td>
- <td style="text-align: center">Site ID, 0 represents ‘US’</td>
- <td style="text-align: center">50</td>
- </tr>
- <tr>
- <td style="text-align: left">SELLER_ID</td>
- <td style="text-align: center">Seller ID</td>
- <td style="text-align: center">About one million</td>
- </tr>
- <tr>
- <td style="text-align: left">PRICE</td>
- <td style="text-align: center">Sold amount</td>
- <td style="text-align: center">-</td>
- </tr>
- </tbody>
-</table>
-
-<p>Very often this online marketplace company need to identify the top sellers (say top 100) in a given time period in some countries. The query looks like:</p>
-
-<div class="highlighter-rouge"><pre class="highlight"><code>SELECT SELLER_ID, SUM(PRICE) FROM KYLIN_SALES
- WHERE
- PART_DT &gt;= date'2016-02-18' AND PART_DT &lt; date'2016-03-18'
- AND LSTG_SITE_ID in (0)
- group by SELLER_ID
- order by SUM(PRICE) DESC limit 100;
-</code></pre>
-</div>
-
-<h2 id="without-top-n-pre-calculation">Without Top-N pre-calculation</h2>
-
-<p>Before Kylin v1.5.0, all the “group by” columns need be as dimension, we come of a design that use PART_DT, LSTG_SITE_ID and SELLER_ID as dimensions, and define SUM(PRICE) as the measure. After build, the base cubiod of the cube will be like:</p>
-
-<table>
- <thead>
- <tr>
- <th style="text-align: left">Rowkey of base cuboid</th>
- <th style="text-align: center">SUM(PRICE)</th>
- </tr>
- </thead>
- <tbody>
- <tr>
- <td style="text-align: left">20140318_00_seller0000001</td>
- <td style="text-align: center">xx.xx</td>
- </tr>
- <tr>
- <td style="text-align: left">20140318_00_seller0000002</td>
- <td style="text-align: center">xx.xx</td>
- </tr>
- <tr>
- <td style="text-align: left">…</td>
- <td style="text-align: center">…</td>
- </tr>
- <tr>
- <td style="text-align: left">20140318_00_seller0999999</td>
- <td style="text-align: center">xx.xx</td>
- </tr>
- <tr>
- <td style="text-align: left">20140318_01_seller0999999</td>
- <td style="text-align: center">xx.xx</td>
- </tr>
- <tr>
- <td style="text-align: left">…</td>
- <td style="text-align: center">…</td>
- </tr>
- <tr>
- <td style="text-align: left">…</td>
- <td style="text-align: center">…</td>
- </tr>
- <tr>
- <td style="text-align: left">20160318_49_seller0999999</td>
- <td style="text-align: center">xx.xx</td>
- </tr>
- </tbody>
-</table>
-
-<p>Assume these dimensions are independent. The number of rows in base cuboid is 730*50*1million = 36.5 billion. Other cuboids which include “SELLER_ID” will also has millions of rows. At this moment you may notice that the cube expansion rate is high, the situation would be worse if there are more dimensions or the cardinality is higher. But the real challenge is not here.</p>
-
-<p>Soon you will find the Top-N query couldn’t work, or took an unacceptable long time. Assume you want the top sellers in past 30 days in US, it need read 30 million rows from storage, aggregate and sort, finally return the top 100 ones.</p>
-
-<p>Now we see, due to no pre-calculation, although the final result set is small, the memory footprint and I/Os in between is heavy.</p>
-
-<h2 id="with-top-n-pre-calculation">With Top-N pre-calculation</h2>
-
-<p>With the Top-N measure, Kylin will pre-calculate the top entities for each dimension combination duing the cube build, saving the result (both entity ID and measure value) as a column in storage. The entity ID (“SELLER_ID” in this case) now can be moved from dimension to the measure, which doesn’t participate in the rowkey. For the sample scenario described above, the newly designed cube will have 2 dimensions (PART_DT, LSTG_SITE_ID), and 1 Top-N measure.</p>
-
-<table>
- <thead>
- <tr>
- <th style="text-align: left">Rowkey of base cuboid</th>
- <th style="text-align: center">Top-N measure</th>
- </tr>
- </thead>
- <tbody>
- <tr>
- <td style="text-align: left">20140318_00</td>
- <td style="text-align: center">seller0010091:xx.xx, seller0005002:xx.xx, …, seller0001789:xx.xx</td>
- </tr>
- <tr>
- <td style="text-align: left">20140318_01</td>
- <td style="text-align: center">seller0032036:xx.xx, seller0010091:xx.xx, …, seller000699:xx.xx</td>
- </tr>
- <tr>
- <td style="text-align: left">…</td>
- <td style="text-align: center">…</td>
- </tr>
- <tr>
- <td style="text-align: left">20160318_49</td>
- <td style="text-align: center">seller0061016:xx.xx, seller0665091:xx.xx, …, seller000699:xx.xx</td>
- </tr>
- </tbody>
-</table>
-
-<p>The base cuboid will have 730 * 50 = 36.5 k rows now. In the measure cell, the Top certain records be stored in a container in descending order, those tail entities have been filtered out.</p>
-
-<p>For the same query, “Top sellers in past 30 days in US” now only need read 30 rows from storage. The measure object, also called as counter containers will be further aggregated/merged at the storage side, finally only one container is returned to Kylin. Kylin extract the “SELLER_ID” and “SUM(PRICE)” from it before returns to client. The cost is much lighter than before, the performance gets highly improved.</p>
-
-<h2 id="algorithm">Algorithm</h2>
-
-<p>Kylin’s Top-N implementation referred to <a href="https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/StreamSummary.java">stream-lib</a>, which is based on the Space-Saving algorithm and the Stream-Summary data structure as described in <i>[1]Efficient Computation of Frequent and Top-k Elements in Data Streams</i> by Metwally, Agrawal, and Abbadi.</p>
-
-<p>A couple of modifications are made to let it better fit with Kylin:</p>
-
-<ul>
- <li>Using double as the counter data type;</li>
- <li>Simplfied data strucutre, using one linked list for all entries;</li>
- <li>A more compact serializer;</li>
-</ul>
-
-<p>Besides, in order to run SpaceSaving in parallel on Hadoop, we make it mergable with the algorithm introduced in <i>[2] A parallel space saving algorithm for frequent items and the Hurwitz zeta distribution</i>.</p>
-
-<h2 id="accuracy">Accuracy</h2>
-
-<p>Although the experiments in paper [1] has proved SpaceSaving’s efficiency and accuracy for realistic Zipfian data, it doesn’t ensure 100% accuracy for all scenarios. SpaceSaving uses a fixed space to put the most frequent candidates; when the entities exceeds the space size, the tail entities will be truncated, causing data loss. The parallel algorithm merges multiple SpaceSavings into one, at that moment for the entities appeared in one but not in the other it had some assumptions, this will also cause some data distortion. Finally, the result from Top-N measure may have minor difference with the real result.</p>
-
-<p>A couple of factors can affect the accuracy:</p>
-
-<ul>
- <li>Zipfian distribution</li>
-</ul>
-
-<p>Many rankings in the world follows the <strong>[3] Zipfian distribution</strong>, such as the population ranks of cities in various countries, corporation sizes, income rankings, etc. But the exponent of the distribution varies in different scenarios, this will affect the correctness of the result to some extend. The higher the exponent is (the distribution is more sharp), the more accurate answer will get. If the distribution is very flat, entities’ values are very close, the rankings from SpaceSaving will be less accurate. When using SpaceSaving, you’d better have an calculation on your data distribution.</p>
-
-<ul>
- <li>Space in SpaceSaving</li>
-</ul>
-
-<p>As mentioned above, SpaceSaving use a limited space to put the most frequent elements. Giving more space it will provide more accurate answer. For example, to calculate Top N elements, using 100 * N space would provide more accurate answer than 50 * N space. If the space is more than the entity’s cardinality, the result will be accurate. More space will take more CPU, memory and storage, this need be balanced.</p>
-
-<ul>
- <li>Entity cardinality</li>
-</ul>
-
-<p>Element cardinality is also a factor to consider. Calculating Top 100 among 10 thousands is easiser than among 10 million.</p>
-
-<ul>
- <li>Dataset size</li>
-</ul>
-
-<p>Error ratio from a big dataset is less than from a small dataset. The same for Top-N calculation.</p>
-
-<h2 id="statistics">Statistics</h2>
-
-<p>We designed a test case to calculate the top 100 elements using the parallel SpaceSaving among a generated data set (with commons-math3’s ZipfDistribution); The entity’s occurancy follows the Zipfian distribution, adjusting the parameters of Zipfian exponent, space, entity cardinality and dataset size time to times, compare the result with the accurate result (using mergesort) to collect the statistics, we get a rough accuracy report in below.</p>
-
-<p>The first column is the entity cardinality, means among how many entities to identify the top 100 elements; The other three columns represent how much space using in the algorithm: 20X means using 2,000, 50X means use 5,000, and so on. Each cell of the table shows how many records are matched with the real result; if the error (or see difference) is less than 5/million of total data size we would think it is matched. E.g, for a 1 million data set, if the difference &lt; 5. The SpaceSaving is calculated in parallel with 10 threads.</p>
-
-<h3 id="test-1-calculate-top-100-in-1-million-records-zipf-distribution-exponent--05-error-tolerance--5">Test 1. Calculate top-100 in 1 million records, Zipf distribution exponent = 0.5, error tolerance &lt; 5</h3>
-
-<table>
- <thead>
- <tr>
- <th style="text-align: right">Element cardinality</th>
- <th style="text-align: center">20X space</th>
- <th style="text-align: center">50X space</th>
- <th style="text-align: center">100X space</th>
- </tr>
- </thead>
- <tbody>
- <tr>
- <td style="text-align: right">1,000</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- </tr>
- <tr>
- <td style="text-align: right">10,000</td>
- <td style="text-align: center">78%</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- </tr>
- <tr>
- <td style="text-align: right">100,000</td>
- <td style="text-align: center">12%</td>
- <td style="text-align: center">50%</td>
- <td style="text-align: center">95%</td>
- </tr>
- </tbody>
-</table>
-
-<p>Conclusion: More space can get better accuracy.</p>
-
-<h3 id="test-2-calculate-top-100-in-1-million-records-zipf-distribution-exponent--06-error-tolerance--5">Test 2. Calculate top-100 in 1 million records, Zipf distribution exponent = 0.6, error tolerance &lt; 5</h3>
-
-<table>
- <thead>
- <tr>
- <th style="text-align: right">Element cardinality</th>
- <th style="text-align: center">20X space</th>
- <th style="text-align: center">50X space</th>
- <th style="text-align: center">100X space</th>
- </tr>
- </thead>
- <tbody>
- <tr>
- <td style="text-align: right">1,000</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- </tr>
- <tr>
- <td style="text-align: right">10,000</td>
- <td style="text-align: center">93%</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- </tr>
- <tr>
- <td style="text-align: right">100,000</td>
- <td style="text-align: center">30%</td>
- <td style="text-align: center">89%</td>
- <td style="text-align: center">99%</td>
- </tr>
- </tbody>
-</table>
-
-<p>Conclusion: more sharp the entities distribute, the better answer SpaceSaving prvoides</p>
-
-<h3 id="test-3-calculate-top-100-in-20-million-records-zif-distribution-exponent--05-error-tolerance--100">Test 3. Calculate top-100 in 20 million records, Zif distribution exponent = 0.5, error tolerance &lt; 100</h3>
-
-<table>
- <thead>
- <tr>
- <th style="text-align: right">Element cardinality</th>
- <th style="text-align: center">20X space</th>
- <th style="text-align: center">50X space</th>
- <th style="text-align: center">100X space</th>
- </tr>
- </thead>
- <tbody>
- <tr>
- <td style="text-align: right">1,000</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- </tr>
- <tr>
- <td style="text-align: right">10,000</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- </tr>
- <tr>
- <td style="text-align: right">100,000</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- </tr>
- <tr>
- <td style="text-align: right">1,000,000</td>
- <td style="text-align: center">99%</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- </tr>
- </tbody>
-</table>
-
-<p>Conclusion: The result from SpaceSaving will be close to actual when the dataset is enough big.</p>
-
-<h3 id="test-4-calculate-top-100-in-20-million-records-zif-distribution-exponent--06-error-tolerance--100">Test 4. Calculate top-100 in 20 million records, Zif distribution exponent = 0.6, error tolerance &lt; 100</h3>
-
-<table>
- <thead>
- <tr>
- <th style="text-align: right">Element cardinality</th>
- <th style="text-align: center">20X space</th>
- <th style="text-align: center">50X space</th>
- <th style="text-align: center">100X space</th>
- </tr>
- </thead>
- <tbody>
- <tr>
- <td style="text-align: right">10,000</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- </tr>
- <tr>
- <td style="text-align: right">20,000</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- </tr>
- <tr>
- <td style="text-align: right">100,000</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- </tr>
- <tr>
- <td style="text-align: right">1,000,000</td>
- <td style="text-align: center">99%</td>
- <td style="text-align: center">100%</td>
- <td style="text-align: center">100%</td>
- </tr>
- </tbody>
-</table>
-
-<p>Conclusion: same conclusion as test 3.</p>
-
-<p>These statistics matches with what we expected above. It just gives us a rough estimation on the result correctness. To use this feature well in Kylin, you need know about all these variables, and do some pilots before publish it to the analysts.</p>
-
-<h2 id="query-performance">Query performance</h2>
-
-<p>Coming soon.</p>
-
-<p>##Futher works</p>
-
-<p>This feature in v1.5.0 is a basic version, which may solve 80% cases; While it has some limitations or hard-codings that deserve your attention:</p>
-
-<ul>
- <li>SUM() is the default aggregation function;</li>
- <li>Sort in descending order always;</li>
- <li>Use 50X space always;</li>
- <li>Use dictionary encoding for the literal column;</li>
- <li>UI only allow selecting topn(10), topn(100) and topn(1000) as the return type;</li>
-</ul>
-
-<p>Please note here, if you select “topn(10)” as the return type, it doesn’t mean you have to use “limit 10” in your query; You can use other limit numbers, Kylin can at most return the top 500 entities for one combination, but the precision after 10 are not tested.</p>
-
-<p>Whether or not to support more aggregations/sortings/encodings are totally based on user need. If you have any comment or suggestion, please subscribe and then drop email to our dev mailing list <a href="&#109;&#097;&#105;&#108;&#116;&#111;:&#100;&#101;&#118;&#064;&#107;&#121;&#108;&#105;&#110;&#046;&#097;&#112;&#097;&#099;&#104;&#101;&#046;&#111;&#114;&#103;">&#100;&#101;&#118;&#064;&#107;&#121;&#108;&#105;&#110;&#046;&#097;&#112;&#097;&#099;&#104;&#101;&#046;&#111;&#114;&#103;</a>, thanks for your feedbak.</p>
-
-<p>##References</p>
-
-<p>[1] <a href="https://dl.acm.org/citation.cfm?id=2131596">Efficient Computation of Frequent and Top-k Elements in Data Streams</a></p>
-
-<p>[2] <a href="http://arxiv.org/pdf/1401.0702.pdf">A parallel space saving algorithm for frequent items<br />
-and the Hurwitz zeta distribution</a></p>
-
-<p>[3] <a href="https://en.wikipedia.org/wiki/Zipf%27s_law">Zipfian law on wikipedia</a></p>
-</description>
- <pubDate>Sat, 19 Mar 2016 09:30:00 -0700</pubDate>
- <link>http://kylin.apache.org/blog/2016/03/19/approximate-topn-measure/</link>
- <guid isPermaLink="true">http://kylin.apache.org/blog/2016/03/19/approximate-topn-measure/</guid>
-
-
- <category>blog</category>
</item>