hive-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Rajat Khandelwal (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (HIVE-12972) Hive Expression parsing is significantly slow for pre-fix expression than post-fix expressions
Date Mon, 01 Feb 2016 09:49:39 GMT

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

Rajat Khandelwal commented on HIVE-12972:
-----------------------------------------

Adding the data in table format so that it's easy to understand the difference


||Expression size||pre-fix parse time||post-fix parse time||
|0|3|2|
|1|5|3|
|2|5|3|
|3|6|11|
|4|11|7|
|5|17|6|
|6|40|6|
|7|55|10|
|8|51|5|
|9|18|6|
|10|56|4|
|11|54|5|
|12|111|5|
|13|266|9|
|14|341|4|
|15|543|4|
|16|259|2|
|17|273|2|
|18|369|3|
|19|844|2|
|20|841|3|
|21|1545|1|
|22|1882|1|
|23|2533|2|
|24|4516|2|
|25|6837|1|
|26|12679|2|
|27|21823|2|
|28|33731|1|
|29|73989|3|
|30|118986|3|

If interested, it's plotted [here|http://fooplot.com/#W3sidHlwZSI6MywiZXEiOltbIjAiLCIyIl0sWyIxIiwiMyJdLFsiMiIsIjMiXSxbIjMiLCIxMSJdLFsiNCIsIjciXSxbIjUiLCI2Il0sWyI2IiwiNiJdLFsiNyIsIjEwIl0sWyI4IiwiNSJdLFsiOSIsIjYiXSxbIjEwIiwiNCJdLFsiMTEiLCI1Il0sWyIxMiIsIjUiXSxbIjEzIiwiOSJdLFsiMTQiLCI0Il0sWyIxNSIsIjQiXSxbIjE2IiwiMiJdLFsiMTciLCIyIl0sWyIxOCIsIjMiXSxbIjE5IiwiMiJdLFsiMjAiLCIzIl0sWyIyMSIsIjEiXSxbIjIyIiwiMSJdLFsiMjMiLCIyIl0sWyIyNCIsIjIiXSxbIjI1IiwiMSJdLFsiMjYiLCIyIl0sWyIyNyIsIjIiXSxbIjI4IiwiMSJdLFsiMjkiLCIzIl0sWyIzMCIsIjMiXV0sImNvbG9yIjoiIzFDRkMwOCJ9LHsidHlwZSI6MywiZXEiOltbIjAiLCIzIl0sWyIxIiwiNSJdLFsiMiIsIjUiXSxbIjMiLCI2Il0sWyI0IiwiMTEiXSxbIjUiLCIxNyJdLFsiNiIsIjQwIl0sWyI3IiwiNTUiXSxbIjgiLCI1MSJdLFsiOSIsIjE4Il0sWyIxMCIsIjU2Il0sWyIxMSIsIjU0Il0sWyIxMiIsIjExMSJdLFsiMTMiLCIyNjYiXSxbIjE0IiwiMzQxIl0sWyIxNSIsIjU0MyJdLFsiMTYiLCIyNTkiXSxbIjE3IiwiMjczIl0sWyIxOCIsIjM2OSJdLFsiMTkiLCI4NDQiXSxbIjIwIiwiODQxIl0sWyIyMSIsIjE1NDUiXSxbIjIyIiwiMTg4MiJdLFsiMjMiLCIyNTMzIl0sWyIyNCIsIjQ1MTYiXSxbIjI1IiwiNjgzNyJdLFsiMjYiLCIxMjY3OSJdLFsiMjciLCIyMTgyMyJdLFsiMjgiLCIzMzczMSJdLFsiMjkiLCI3Mzk4OSJdLFsiMzAiLCIxMTg5ODYiXV0sImNvbG9yIjoiI0YyNDMxOCJ9LHsidHlwZSI6MTAwMCwid2luZG93IjpbIi01MTI5NS44NjczNDg2NjQxMSIsIjU1MjAwLjEzMjY1MTMzNTQ2NSIsIi0zMTkxMi40ODY5NzY1NTI4NDYiLCIzMzYyMy41MTMwMjM0NDY5MiJdfV0-].
Will need to zoom-in to see the magnitude of difference. 

> Hive Expression parsing is significantly slow for pre-fix expression than post-fix expressions
> ----------------------------------------------------------------------------------------------
>
>                 Key: HIVE-12972
>                 URL: https://issues.apache.org/jira/browse/HIVE-12972
>             Project: Hive
>          Issue Type: Bug
>            Reporter: Rajat Khandelwal
>
> Expressions
> * Prefix expression ((((true) or true) or true) or true) takes 5 ms in parsing while

> * Postfix expression (true or (true or (true or (true)))) takes 3 ms in parsing
> Given a sequence of expressions, which are to be OR-ed, they can be OR-ed in two ways.

> Given a, b, c, d, I can make:
> * (a) -> ((a) or b) -> (((a) or b) or c) -> ((((a) or b) or c) or d)
> * (d) -> (c or (d)) -> (b or (c or (d))) -> (a or (b or (c or (d))))
> The first construction is slower than the second construction, regardless of the constituent
sub-expressions. 
> A more important point is, as the number of sub-expressions grows, the performance gap
increases. Just to emphasize, it takes 2 minutes to parse a pre-fix expression of 20, while
it takes 3ms to parse post-fix expression of 20. 
> Have tried to instrument that by writing a test case in TestParseDriver:
> I hope it's easy enough to understand:
> {noformat}
>   @Test
>   public void parseLongExpression() throws ParseException {
>     List<Long> preFixParseTime = new ArrayList<>();
>     List<Long> postFixParseTime = new ArrayList<>();
>     String preFixExpr = "(true)";
>     String postFixExpr = "(true)";
>     parseDriver.parseExpression(preFixExpr);
>     parseDriver.parseExpression(postFixExpr);
>     for (int j = 0; j < 50; j++) {
>       preFixExpr = "(" + preFixExpr + " or true)";
>       postFixExpr = "(true or " + postFixExpr + ")";
>       long startTime = System.currentTimeMillis();
>       parseDriver.parseExpression(preFixExpr);
>       preFixParseTime.add(System.currentTimeMillis() - startTime);
>       startTime = System.currentTimeMillis();
>       parseDriver.parseExpression(postFixExpr);
>       postFixParseTime.add(System.currentTimeMillis() - startTime);
>       System.out.println("i = " + j + " prefix expr: " + preFixExpr + " parseTime: "
+ preFixParseTime.get(j) + " postfix expr: " + postFixExpr + " parse time: " + postFixParseTime.get(j));
>     }
>     System.out.println("done");
>   }
> {noformat}
> This was the output:
> {noformat}
> i = 0 prefix expr: ((true) or true) parseTime: 3 postfix expr: (true or (true)) parse
time: 2
> i = 1 prefix expr: (((true) or true) or true) parseTime: 5 postfix expr: (true or (true
or (true))) parse time: 3
> i = 2 prefix expr: ((((true) or true) or true) or true) parseTime: 5 postfix expr: (true
or (true or (true or (true)))) parse time: 3
> i = 3 prefix expr: (((((true) or true) or true) or true) or true) parseTime: 6 postfix
expr: (true or (true or (true or (true or (true))))) parse time: 11
> i = 4 prefix expr: ((((((true) or true) or true) or true) or true) or true) parseTime:
11 postfix expr: (true or (true or (true or (true or (true or (true)))))) parse time: 7
> i = 5 prefix expr: (((((((true) or true) or true) or true) or true) or true) or true)
parseTime: 17 postfix expr: (true or (true or (true or (true or (true or (true or (true)))))))
parse time: 6
> i = 6 prefix expr: ((((((((true) or true) or true) or true) or true) or true) or true)
or true) parseTime: 40 postfix expr: (true or (true or (true or (true or (true or (true or
(true or (true)))))))) parse time: 6
> i = 7 prefix expr: (((((((((true) or true) or true) or true) or true) or true) or true)
or true) or true) parseTime: 55 postfix expr: (true or (true or (true or (true or (true or
(true or (true or (true or (true))))))))) parse time: 10
> i = 8 prefix expr: ((((((((((true) or true) or true) or true) or true) or true) or true)
or true) or true) or true) parseTime: 51 postfix expr: (true or (true or (true or (true or
(true or (true or (true or (true or (true or (true)))))))))) parse time: 5
> i = 9 prefix expr: (((((((((((true) or true) or true) or true) or true) or true) or true)
or true) or true) or true) or true) parseTime: 18 postfix expr: (true or (true or (true or
(true or (true or (true or (true or (true or (true or (true or (true))))))))))) parse time:
6
> i = 10 prefix expr: ((((((((((((true) or true) or true) or true) or true) or true) or
true) or true) or true) or true) or true) or true) parseTime: 56 postfix expr: (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true))))))))))))
parse time: 4
> i = 11 prefix expr: (((((((((((((true) or true) or true) or true) or true) or true) or
true) or true) or true) or true) or true) or true) or true) parseTime: 54 postfix expr: (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true))))))))))))) parse time: 5
> i = 12 prefix expr: ((((((((((((((true) or true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) parseTime: 111 postfix
expr: (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true or (true or (true)))))))))))))) parse time: 5
> i = 13 prefix expr: (((((((((((((((true) or true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) parseTime:
266 postfix expr: (true or (true or (true or (true or (true or (true or (true or (true or
(true or (true or (true or (true or (true or (true or (true))))))))))))))) parse time: 9
> i = 14 prefix expr: ((((((((((((((((true) or true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
parseTime: 341 postfix expr: (true or (true or (true or (true or (true or (true or (true or
(true or (true or (true or (true or (true or (true or (true or (true or (true))))))))))))))))
parse time: 4
> i = 15 prefix expr: (((((((((((((((((true) or true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
or true) parseTime: 543 postfix expr: (true or (true or (true or (true or (true or (true or
(true or (true or (true or (true or (true or (true or (true or (true or (true or (true or
(true))))))))))))))))) parse time: 4
> i = 16 prefix expr: ((((((((((((((((((true) or true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
or true) or true) parseTime: 259 postfix expr: (true or (true or (true or (true or (true or
(true or (true or (true or (true or (true or (true or (true or (true or (true or (true or
(true or (true or (true)))))))))))))))))) parse time: 2
> i = 17 prefix expr: (((((((((((((((((((true) or true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
or true) or true) or true) parseTime: 273 postfix expr: (true or (true or (true or (true or
(true or (true or (true or (true or (true or (true or (true or (true or (true or (true or
(true or (true or (true or (true or (true))))))))))))))))))) parse time: 2
> i = 18 prefix expr: ((((((((((((((((((((true) or true) or true) or true) or true) or
true) or true) or true) or true) or true) or true) or true) or true) or true) or true) or
true) or true) or true) or true) or true) parseTime: 369 postfix expr: (true or (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true or (true or (true or (true or (true or (true)))))))))))))))))))) parse time:
3
> i = 19 prefix expr: (((((((((((((((((((((true) or true) or true) or true) or true) or
true) or true) or true) or true) or true) or true) or true) or true) or true) or true) or
true) or true) or true) or true) or true) or true) parseTime: 844 postfix expr: (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true)))))))))))))))))))))
parse time: 2
> i = 20 prefix expr: ((((((((((((((((((((((true) or true) or true) or true) or true) or
true) or true) or true) or true) or true) or true) or true) or true) or true) or true) or
true) or true) or true) or true) or true) or true) or true) parseTime: 841 postfix expr: (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true)))))))))))))))))))))) parse time: 3
> i = 21 prefix expr: (((((((((((((((((((((((true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) parseTime: 1545 postfix
expr: (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true or (true))))))))))))))))))))))) parse time: 1
> i = 22 prefix expr: ((((((((((((((((((((((((true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) parseTime:
1882 postfix expr: (true or (true or (true or (true or (true or (true or (true or (true or
(true or (true or (true or (true or (true or (true or (true or (true or (true or (true or
(true or (true or (true or (true or (true or (true)))))))))))))))))))))))) parse time: 1
> i = 23 prefix expr: (((((((((((((((((((((((((true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
parseTime: 2533 postfix expr: (true or (true or (true or (true or (true or (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true)))))))))))))))))))))))))
parse time: 2
> i = 24 prefix expr: ((((((((((((((((((((((((((true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
or true) parseTime: 4516 postfix expr: (true or (true or (true or (true or (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true))))))))))))))))))))))))))
parse time: 2
> i = 25 prefix expr: (((((((((((((((((((((((((((true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
or true) or true) parseTime: 6837 postfix expr: (true or (true or (true or (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true))))))))))))))))))))))))))) parse time: 1
> i = 26 prefix expr: ((((((((((((((((((((((((((((true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
or true) or true) or true) parseTime: 12679 postfix expr: (true or (true or (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true or (true or (true)))))))))))))))))))))))))))) parse time: 2
> i = 27 prefix expr: (((((((((((((((((((((((((((((true) or true) or true) or true) or
true) or true) or true) or true) or true) or true) or true) or true) or true) or true) or
true) or true) or true) or true) or true) or true) or true) or true) or true) or true) or
true) or true) or true) or true) or true) parseTime: 21823 postfix expr: (true or (true or
(true or (true or (true or (true or (true or (true or (true or (true or (true or (true or
(true or (true or (true or (true or (true or (true or (true or (true or (true or (true or
(true or (true or (true or (true or (true or (true or (true))))))))))))))))))))))))))))) parse
time: 2
> i = 28 prefix expr: ((((((((((((((((((((((((((((((true) or true) or true) or true) or
true) or true) or true) or true) or true) or true) or true) or true) or true) or true) or
true) or true) or true) or true) or true) or true) or true) or true) or true) or true) or
true) or true) or true) or true) or true) or true) parseTime: 33731 postfix expr: (true or
(true or (true or (true or (true or (true or (true or (true or (true or (true or (true or
(true or (true or (true or (true or (true or (true or (true or (true or (true or (true or
(true or (true or (true or (true or (true or (true or (true or (true or (true))))))))))))))))))))))))))))))
parse time: 1
> i = 29 prefix expr: (((((((((((((((((((((((((((((((true) or true) or true) or true) or
true) or true) or true) or true) or true) or true) or true) or true) or true) or true) or
true) or true) or true) or true) or true) or true) or true) or true) or true) or true) or
true) or true) or true) or true) or true) or true) or true) parseTime: 73989 postfix expr:
(true or (true or (true or (true or (true or (true or (true or (true or (true or (true or
(true or (true or (true or (true or (true or (true or (true or (true or (true or (true or
(true or (true or (true or (true or (true or (true or (true or (true or (true or (true or
(true))))))))))))))))))))))))))))))) parse time: 3
> i = 30 prefix expr: ((((((((((((((((((((((((((((((((true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) or true) or true)
or true) or true) or true) or true) or true) or true) or true) or true) parseTime: 118986
postfix expr: (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true or (true or (true or (true or (true or (true or (true or (true or (true
or (true or (true or (true)))))))))))))))))))))))))))))))) parse time: 3
> {noformat}



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

Mime
View raw message