You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@kylin.apache.org by "Huang Hua (JIRA)" <ji...@apache.org> on 2015/05/07 10:25:00 UTC

[jira] [Commented] (KYLIN-752) Improved IN clause performance

    [ https://issues.apache.org/jira/browse/KYLIN-752?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14532231#comment-14532231 ] 

Huang Hua commented on KYLIN-752:
---------------------------------

Would like to share my two cents worth on this topic:
1. for 'IN' values, the current strategy of Kylin storage engine just picks the min and max values from them to come up with the hbase scan range. This is usually bad, as you can imagine that in many cases you could have ‘IN' clause containing some random values, let's say a small value(e.g 1) and a large number(e.g. 1000000), and eventually the hbase scan range becomes [1, 1000000] meaning it would scan a pretty large range in the hbase table.

This could be solved by divide the 'IN' values into many small ranges, for example, the 'IN' clause is (a, b, c, d, e), initially Kylin would use [a, e] as scan range, but it's better to divide it into [a, c] and [d, e] because scan_count([a, c]) + scan_count([d, e]) < scan_count([a, e]) as we ignore the [c, d] scan.
And for cases that the number of 'IN' values is relatively small, we could even break the 'IN' clause into ranges where each range is just a single value scan, such as [a, a], [b, b], [c, c], [d, d] and [e, e] in the above example.

2. and also, for 'IN' values that are not in the corresponding dictionary, Kylin by default will use either '\x00' or '\xFF' to get thier scan values. If in some cases that the not-in-dictionary values happen to the min or the max value among the 'IN' values, Kylin would generate scan ranges like:
['\x00\x00\x00...', actual byte value of the max 'IN' value] - the not-in-dictionary value happen to be the min
[actual byte value of the min 'IN' value,  '\xFF\xFF\xFF..'] - the not-in-dictionary value happen to be the max
['\x00\x00\x00...', '\xFF\xFF\xFF..'] - the not-in-dictionary value happen to be the min as well as the max
The last case is the worst because it's essentially a full table scan!!

To avoid such issue, a quick fix can be made to drop the not-in-dictionary values before generating hbase scan range. And based on it, we can make a further optimization that as long as there is at least one andFilter is empty(after we drop the not-in-dictionary values), we can simply assert that the whole andFilters is empty to avoid an unnecessary hbase scan. However, this strategy only works for 'EQ', 'IN'.
For 'LT', 'LTE', 'GT', 'GTE', you can't simply drop the not-in-dictionary values, instead you have to replace them with the some sort of closest smaller or bigger values by calling "final public int getIdFromValue(T value, int roundingFlag)" of "Dictionary" class.
By the way, we've implemented this fix and it works very well.

> Improved IN clause performance
> ------------------------------
>
>                 Key: KYLIN-752
>                 URL: https://issues.apache.org/jira/browse/KYLIN-752
>             Project: Kylin
>          Issue Type: Improvement
>            Reporter: hongbin ma
>            Assignee: liyang
>




--
This message was sent by Atlassian JIRA
(v6.3.4#6332)