[CALCITE-831] Rules to push down limits

• Type: Bug
• Status: Open
• Priority: Major
• Resolution: Unresolved
• Assignee: Unassigned
• Reporter: Julian Hyde
• Created: 07/Aug/15 15:58
• Updated: 22/Feb/19 01:20

Description

Add rules to push down limits, based on a conversation with maryannxue.

Recall that the SQL LIMIT clause becomes a Sort relational expression; the Sort.fetch attribute specifies the limit, or is null for no limit; the Sort has zero or more collations, corresponding to the expressions in the ORDER BY; there may also be a Sort.offset attribute.

A "naked limit" is a Sort with 0 sort columns and a not-null fetch clause, e.g. "LIMIT 10" without "ORDER BY".

Cases:

• SortProjectTransposeRule matches a Sort on a Project, already exists, and already handles offset and fetch. (DONE)
• SortSortMergeRule (proposed) combines two Sort expressions. Among other cases, it handles a naked limit followed by a naked limit, and a sort followed by a naked limit.
• SortUnionTransposeRule pushes a Sort through a Union in some cases. It can push a naked limit through a union all, but needs to keep a limit after the union.
• SortJoinTransposeRule pushes a Sort through a Join in some cases. You could push 'select * from emp join dept using (deptno) order by sal limit 10' because the join to dept is just a 'lookup' and has no filtering effect.
• SortAggregateMergeRule could, if the limit applied to a measure such as sum or count, create a "topN" aggregate, for which there are known optimizations.

Non-cases:

• SortFilterTransposeRule would not be very useful. It is not safe to push a limit through a Filter. And you can perform a Sort (without limit) before a Filter but it is more effort, so why bother?

Issue Links

• is duplicated by: CALCITE-857 Add SortJoinTransposeRule
• is duplicated by: CALCITE-832 General optimization rules for Limit
• is related to: DRILL-1457 Limit operator optimization : push limit operator past exchange operator
• is related to: HIVE-11775 Implement limit push down through union all in CBO
• relates to: CALCITE-857 Add SortJoinTransposeRule

Sub-Tasks

• Implement SortUnionTransposeRule: Closed
• Implement SortJoinTransposeRule: Closed