[jira] [Commented] (HIVE-12972) Hive Expression parsing is significantly slow for pre-fix expression than post-fix expressions

["Rajat Khandelwal (JIRA)" <ji...@apache.org>]

    [ 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)