[YSQL] Support Bitmap Index Only Scans

[timothy-e]

Jira Link: DB-10084

Description

CREATE TABLE test_bitmap_index_only (a INT, b INT, c INT, d INT);
CREATE INDEX ON test_bitmap_index_only (a ASC) INCLUDE (c);
CREATE INDEX ON test_bitmap_index_only (b ASC) INCLUDE (d);
INSERT INTO test_bitmap_index_only SELECT i, i * 2, i * 3, i * 4 FROM generate_series(1, 10000) i;

The following query can be answered by an index only scan:

EXPLAIN SELECT b, d FROM test_bitmap_index_only WHERE b < 100;
                                                    QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
 Index Only Scan using test_bitmap_index_only_b_d_idx on test_bitmap_index_only  (cost=0.00..5.12 rows=10 width=8)
   Index Cond: (b < 100)
(2 rows)

But this query requires requests to the main table, even though all of it's fields are included in its indexes.

EXPLAIN SELECT b, d FROM test_bitmap_index_only WHERE b < 100 OR b > 19900;
                                             QUERY PLAN
----------------------------------------------------------------------------------------------------
 YB Bitmap Table Scan on test_bitmap_index_only  (cost=6.91..11.21 rows=10 width=8)
   ->  BitmapOr  (cost=6.91..6.91 rows=20 width=0)
         ->  Bitmap Index Scan on test_bitmap_index_only_b_d_idx  (cost=0.00..3.45 rows=10 width=0)
               Index Cond: (b < 100)
         ->  Bitmap Index Scan on test_bitmap_index_only_b_d_idx  (cost=0.00..3.45 rows=10 width=0)
               Index Cond: (b > 19900)
(6 rows)

Instead of storing the matching ybctids and using those to query the main table, we could detect that the fields we are requesting are covered by each of the indexes used to access them. We could then store (ybctid, <target_values>) in a hash table instead of a ybctid set and avoid a trip to the main table.

EXPLAIN (ANALYZE, DIST, COSTS OFF) SELECT b, d FROM test_bitmap_index_only WHERE b < 100 OR b > 19900;
                                        QUERY PLAN
------------------------------------------------------------------------------------------
 YB Bitmap Table Scan on test_bitmap_index_only (actual rows=99 loops=1)
   ->  BitmapOr (actual rows=99 loops=1)
         ->  Bitmap Index Scan on test_bitmap_index_only_b_d_idx (actual rows=49 loops=1)
               Index Cond: (b < 100)
               Targets: (b, d)
               Storage Index Read Requests: 1
               Storage Index Rows Scanned: 49
         ->  Bitmap Index Scan on test_bitmap_index_only_b_d_idx (actual rows=50 loops=1)
               Index Cond: (b > 19900)
               Targets: (b, d)
               Storage Index Read Requests: 1
               Storage Index Rows Scanned: 50
 Storage Read Requests: 2
 Storage Rows Scanned: 99
 Storage Write Requests: 0
 Storage Flush Requests: 0
(16 rows)

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.