[HIVE-21857] Sort conditions in a filter predicate to accelerate query processing

• Type: New Feature
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 4.0.0-alpha-1
• Component/s: CBO
• Labels: pull-request-available
• Assignee: Jesús Camacho Rodríguez
• Reporter: Jesús Camacho Rodríguez
• Created: 10/Jun/19 23:20
• Updated: 27/Feb/24 22:23
• Resolved: 25/Jun/19 15:10

Description

Following approach similar to http://db.cs.berkeley.edu/jmh/miscpapers/sigmod93.pdf .

To reorder predicates in AND conditions, we could rank each of elements in the clauses in increasing order based on following formula:

rank = (selectivity - 1) / cost per tuple

Similarly, for OR conditions:

rank = (-selectivity) / cost per tuple

Selectivity can be computed with FilterSelectivityEstimator. For cost per tuple, we will need to come up with some heuristic based on how expensive is the evaluation of the functions contained in that predicate. Custom UDFs could be annotated.

Issue Links

• Is contained by: HIVE-26751 Bug Fixes and Improvements for 3.2.0 release
• is related to: HIVE-21867 Sort semijoin conditions to accelerate query processing
• is related to: HIVE-26238 Decouple sort filter predicates optimization from digest normalization in CBO
• links to: GitHub Pull Request #671