[IMPALA-9983] Push limit from a top level sort onto analytic sort when applicable

• Type: Improvement
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Affects Version/s: Impala 3.4.0
• Fix Version/s: Impala 4.0.0
• Component/s: Frontend
• Epic Color: ghx-label-2
• Assignee: Aman Sinha
• Reporter: Aman Sinha
• Created: 21/Jul/20 06:22
• Updated: 07/Aug/20 21:41
• Resolved: 03/Aug/20 05:10

Description

For queries of the following type:

select * from (select l_partkey, l_quantity, 
              rank() over (partition by l_partkey order by l_quantity desc) rk 
   from lineitem) dt 
   where rk <= 100
   order by l_partkey, l_quantity, rk
   limit 100

the limit 100 from the outer order by can be pushed down to the analytic sort that is done below the AnalyticEval operator. The reason is there are effectively 2 limits:
PARTITION BY l_partkey ORDER BY l_quantity LIMIT PER PARTITION 100
ORDER BY l_partkey .... LIMIT 100
and together they imply
ORDER BY l_partkey, l_quantity LIMIT 100

For the limit pushdown to work, the partition-by exprs must be a leading prefix of the order-by exprs. Also, other qualifying conditions must be met based on the above pattern.

Issue Links

• is related to: IMPALA-9951 Skew in analytic sorts when partition key has low cardinality
• is related to: IMPALA-9853 Push rank() predicates into sort