[YSQL] Bool hash column breaks lower order sorting

Jira Link: DB-17852

Description

Compare

create table ints (k1 int, k2 int, k3 text, primary key ((k1, k2) hash, k3));
explain select * from ints where k1 = 0 and k2 = 0 order by k3;

                                QUERY PLAN                                                                                              
--------------------------------------------------------------------------                                                              
 Index Scan using ints_pkey on ints  (cost=0.00..15.50 rows=100 width=40)                                                               
   Index Cond: ((k1 = 0) AND (k2 = 0))                              
(2 rows)                                                            

and

create table bools (k1 bool, k2 bool, k3 text, primary key ((k1, k2) hash, k3));
explain select * from bools where k1 = 0::bool and k2 = 0::bool order by k3;

                                    QUERY PLAN                                                                                          
----------------------------------------------------------------------------------                                                      
 Sort  (cost=18.32..18.57 rows=100 width=34)                        
   Sort Key: k3                                                     
   ->  Index Scan using bools_pkey on bools  (cost=0.00..15.00 rows=100 width=34)                                                       
         Index Cond: ((k1 = false) AND (k2 = false))                                                                                    
(4 rows)

or

explain select * from bools where not k1 and not k2 order by k3;

                                    QUERY PLAN                                                                                          
----------------------------------------------------------------------------------                                                      
 Sort  (cost=18.32..18.57 rows=100 width=34)                        
   Sort Key: k3                                                     
   ->  Index Scan using bools_pkey on bools  (cost=0.00..15.00 rows=100 width=34)                                                       
         Index Cond: ((k1 = false) AND (k2 = false))                                                                                    
(4 rows)

The bool case has an extra sort node on top because the index scan is not believed to return results in order.

I suspect commit 565f56692b42c01ce56025cb7f1c535de5022cdc to be causing this issue since it adds logic to ignore postgres's treatment of bool conditions as equivalence conditions (it appears some earlier processing step converts all sorts of boolean expressions such as boolcol = false or boolcol = (1 = 0) to something like not bool, thus causing an equivalence class for boolcol to not get created). However, applying this patch causes wrong results:

diff --git i/src/postgres/src/backend/optimizer/path/pathkeys.c w/src/postgres/src/backend/optimizer/path/pathkeys.c
index a59b2279c8..bd90245f21 100644
--- i/src/postgres/src/backend/optimizer/path/pathkeys.c
+++ w/src/postgres/src/backend/optimizer/path/pathkeys.c
@@ -650,7 +650,7 @@ build_index_pathkeys(PlannerInfo *root,
              * should stop considering index columns; any lower-order sort
              * keys won't be useful either.
              */
-            if (!indexcol_is_bool_constant_for_query(root, index, i) || i < index->nhashcolumns)
+            if (!indexcol_is_bool_constant_for_query(root, index, i))
                 break;
         }
 

yugabyte=# insert into bools select false, false, i from generate_series(1, 10) i;
INSERT 0 10
yugabyte=# select * from bools where k1 = 0::bool and k2 = 0::bool order by k3;
 k1 | k2 | k3 
----+----+----
 f  | f  | 1
 f  | f  | 10
 f  | f  | 2
 f  | f  | 3
 f  | f  | 4
 f  | f  | 5
 f  | f  | 6
 f  | f  | 7
 f  | f  | 8
 f  | f  | 9
(10 rows)

so more investigation is needed.

Note the examples above work the same way with a single hash column. This is not a bug because results are correct. It is a performance issue, but who would practically have a bool hash primary key? Maybe in conjunction with other columns for a multi-column hash?

Issue Type

kind/enhancement

Warning: Please confirm that this issue does not contain any sensitive information

• I confirm this issue does not contain any sensitive information.