opt: Unnecessary sort operator added by SELECT with WHERE clause

[andy-kimball]

Repro:

CREATE TABLE xyz (x INT PRIMARY KEY, y INT, z INT);
CREATE TABLE abcd (a INT, b INT, c INT, d INT, INDEX ab(a, b) STORING (c, d), INDEX cd(c, d) STORING (a, b));
EXPLAIN (OPT) SELECT * FROM [INSERT INTO xyz SELECT b, c, d FROM abcd ORDER BY c, d LIMIT 100 RETURNING *] WHERE x=y ORDER BY y;

Expected: No explicit sort should be necessary
Actual: An explicit sort is added.

  sort
   ├── columns: x:5(int!null) y:6(int!null) z:7(int)
   ├── ordering: +(5|6) [provided: +5]
   └── select
        ├── columns: b:5(int!null) c:6(int!null) d:7(int)
        ├── insert xyz
        │    ├── columns: b:5(int!null) c:6(int) d:7(int)
        │    ├── insert-mapping:
        │    │    ├──  b:5(int!null) => x:1(int)
        │    │    ├──  c:6(int) => y:2(int)
        │    │    └──  d:7(int) => z:3(int)
        │    ├── internal-ordering: +6,+7
        │    └── scan abcd@cd
        │         ├── columns: b:5(int) c:6(int) d:7(int)
        │         ├── limit: 100
        │         ├── stats: [rows=100, distinct(5)=65.132156, null(5)=1, distinct(6)=65.132156, null(6)=1]
        │         └── ordering: +6,+7
        └── filters
             └── eq [type=bool, outer=(5,6), constraints=(/5: (/NULL - ]; /6: (/NULL - ]), fd=(5)==(6), (6)==(5)]
                  ├── variable: b [type=int]
                  └── variable: c [type=int]

Jira issue: CRDB-4704

[andy-kimball]

Note that removing the WHERE x=y clause no longer causes the sort to be added.

[RaduBerinde]

Fixed by #33023:

  select                                                                                                      
   ├── columns: x:5(int!null) y:6(int!null) z:7(int)                                                          
   ├── cardinality: [0 - 100]                                                                                 
   ├── side-effects, mutations                                                                                
   ├── stats: [rows=1.53533993, distinct(5)=1.53533993, null(5)=0, distinct(6)=1.53533993, null(6)=0]         
   ├── cost: 109.03                                                                                           
   ├── fd: (5)==(6), (6)==(5)                                                                                 
   ├── ordering: +(5|6) [provided: +6]                                                                        
   ├── insert xyz                                                                                             
   │    ├── columns: b:5(int!null) c:6(int) d:7(int)                                                          
   │    ├── insert-mapping:                                                                                   
   │    │    ├──  b:5(int!null) => x:1(int)                                                                   
   │    │    ├──  c:6(int) => y:2(int)                                                                        
   │    │    └──  d:7(int) => z:3(int)                                                                        
   │    ├── internal-ordering: +6,+7                                                                          
   │    ├── cardinality: [0 - 100]                                                                            
   │    ├── side-effects, mutations                                                                           
   │    ├── stats: [rows=100]                                                                                 
   │    ├── cost: 108.02                                                                                      
   │    ├── ordering: +(5|6) [provided: +6]                                                                   
   │    └── scan abcd@cd                                                                                      
   │         ├── columns: b:5(int) c:6(int) d:7(int)                                                          
   │         ├── limit: 100                                                                                   
   │         ├── stats: [rows=100, distinct(5)=65.132156, null(5)=1, distinct(6)=65.132156, null(6)=1]        
   │         ├── cost: 108.01                                                                                 
   │         └── ordering: +6,+7                                                                              
   └── filters                                                                                                
        └── eq [type=bool, outer=(5,6), constraints=(/5: (/NULL - ]; /6: (/NULL - ]), fd=(5)==(6), (6)==(5)]  
             ├── variable: b [type=int]                                                                       
             └── variable: c [type=int]                                                                       

[RaduBerinde]

I am backing out the "fix". Columns in an OrderingChoice column group must be equivalent. There are subtle issues that show up if we relax that, and queries where we have equalities between columns (other than joins) shouldn't be very common. In the Select case, the columns are not equivalent under the select and we must make an (arbitrary) choice between them.

As an example of a subtle issue: say that we have something like

SELECT * FROM (SELECT a,b,c,k FROM t UNION ALL <something>) WHERE b=k ORDER BY a,b,c

We have a Select (b=k) with required ordering +a,+b,+c. If we require ordering +a,+(b|k),+c from its input, then that might choose to do a streaming UNION along columns +a,+b,+c. Say that k is a key in t (but it won't be a key anymore at the level of the UNION ALL). Under the UNION, the ordering would get incorrectly simplified to +a,+(b|k). Now that operator might emit rows where column c is incorrectly ordered (which would break the assumption used by streaming union execution). The key issue here is that Simplify assumes that columns in groups are equivalent. I don't know how it would work if it didn't make that assumption. In this case, we would want to express that we require ordering +a,+k OR +a,+b,+c, but OrderingChoice is not capable of expressing that.

[RaduBerinde]

An idea is to use interesting orderings when making a choice for which subset of columns to keep.

[github-actions]

We have marked this issue as stale because it has been inactive for
18 months. If this issue is still relevant, removing the stale label
or adding a comment will keep it active. Otherwise, we'll close it in
5 days to keep the issue queue tidy. Thank you for your contribution
to CockroachDB!

[github-actions]

We have marked this issue as stale because it has been inactive for
18 months. If this issue is still relevant, removing the stale label
or adding a comment will keep it active. Otherwise, we'll close it in
10 days to keep the issue queue tidy. Thank you for your contribution
to CockroachDB!