[CALCITE-873] Prevent sort when ORDER BY not necessary due to equality constraints

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 1.17.0
• Assignee: Atri Sharma
• Reporter: James R. Taylor
• Created: 03/Sep/15 22:47
• Updated: 08/Jul/24 17:55
• Resolved: 24/May/18 22:43

Description

We're working on an optimization in Phoenix to optimize away an ORDER BY when it is known based on equality expressions in the WHERE clause that it is not necessary (PHOENIX-2194). It'd be great if Calcite could do that as well.

Here's a example, given the following schema:

CREATE TABLE T (
  K1 VARCHAR,
  K2 VARCHAR,
  K3 VARCHAR,
  CONSTRAINT pk PRIMARY KEY (K1, K2, K3));

In the following queries, no sort is necessary:

SELECT * FROM T WHERE K1='A' ORDER BY K2,K3;
SELECT * FROM T WHERE K2='B' ORDER BY K1,K3;
SELECT * FROM T WHERE K1='A' AND K2='B' ORDER BY K3;

There are also some edge cases where a function may be known to select a prefix of the column value where it's still ok to not sort:

SELECT * FROM T WHERE K1='A' AND SUBSTR(K2,1,3)='ABC' ORDER BY K2;

But if another column is included in the ORDER BY after the prefixing, a sort would still be necessary:

SELECT * FROM T WHERE K1='A' AND SUBSTR(K2,1,3)='ABC' ORDER BY K2,K3;

Issue Links

• is duplicated by: CALCITE-6440 SortRemoveConstantKeysRule should remove NULL literal sort keys (e.g. ORDER BY NULL)
• is related to: PHOENIX-2194 order by should not require all PK fields with = constraint
• relates to: CALCITE-945 Sort algorithm that skips low-cardinality leading edge, such as a salting column
• relates to: CALCITE-5894 Add SortRemoveRedundantRule to remove redundant sort fields if they are functionally dependent on other sort fields
• links to: PR 485