[HIVE-11398] Parse wide OR and wide AND trees to flat OR/AND trees

• Type: New Feature
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 1.3.0, 2.0.0
• Component/s: Logical Optimizer, UDF
• Assignee: Jesús Camacho Rodríguez
• Reporter: Gopal Vijayaraghavan
• Created: 29/Jul/15 02:46
• Updated: 27/Feb/24 22:23
• Resolved: 11/Aug/15 02:59

Description

Deep trees of AND/OR are hard to traverse particularly when they are merely the same structure in nested form as a version of the operator that takes an arbitrary number of args.

One potential way to convert the DFS searches into a simpler BFS search is to introduce a new Operator pair named ALL and ANY.

ALL(A, B, C, D, E) represents AND(AND(AND(AND(E, D), C), B), A)

ANY(A, B, C, D, E) represents OR(OR(OR(OR(E, D), C),B),A)

The SemanticAnalyser would be responsible for generating these operators and this would mean that the depth and complexity of traversals for the simplest case of wide AND/OR trees would be trivial.

Issue Links

• is part of: HIVE-11315 Compilation performance issues for large queries
• is related to: HIVE-11557 CBO (Calcite Return Path): Convert to flat AND/OR
• is related to: HIVE-11461 Transform flat AND/OR into IN struct clause
• is related to: HIVE-11791 Add unit test for HIVE-10122
• is required by: HIVE-12968 genNotNullFilterForJoinSourcePlan: needs to merge predicates into the multi-AND
• relates to: HIVE-11448 Support vectorization of Multi-OR and Multi-AND
• supercedes: HIVE-11412 StackOverFlow in SemanticAnalyzer for huge filters (~5000)
• supercedes: HIVE-11415 Add early termination for recursion in vectorization for deep filter queries