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