[YSQL] Seek Forward Optimization is not modeled in cost model

[gauravk-in]

Jira Link: DB-15215

Description

Seek forward optimization reduces the number of expensive seek operations needed in lookup of a key in DocDB.

Before seeking to the next key, we check if the key can be found in the subsequent few tuples by performing cheaper next operations. Only if the key is not found, we proceed to seek to the key. The number of nexts performed is controlled by the max_nexts_to_avoid_seek yb-master gflag.

In the cost model, we currently assume that seek-forward optimization yields no benefit, or in other words the key is never found in the subsequent next operations.

For example,

# CREATE TABLE test (k1 INT, k2 INT, PRIMARY KEY (k1 ASC, k2 ASC));
# INSERT INTO test (SELECT s1, s2 FROM generate_series(1, 20) s1, generate_series(1, 20) s2);
# ANALYZE test;
# SET yb_enable_base_scans_cost_model = ON;

In the following examples, the keys we are close by and the optimization will help reduce the number of seeks. The cost model over-estimates the seeks.

# /*+ IndexScan(test) */ EXPLAIN (ANALYZE, DEBUG, DIST) SELECT * FROM test WHERE k2 IN (4, 5, 6, 7);
                                                      QUERY PLAN                                                       
-----------------------------------------------------------------------------------------------------------------------
 Index Scan using test_pkey on test  (cost=180.00..1130.52 rows=80 width=8) (actual time=3.339..3.405 rows=80 loops=1)
   Index Cond: (k2 = ANY ('{4,5,6,7}'::integer[]))
...
   Metric rocksdb_number_db_seek: 41.000
   Metric rocksdb_number_db_next: 140.000
...
   Estimated Seeks: 100
   Estimated Nexts: 200
...

# EXPLAIN (ANALYZE, DEBUG, DIST) SELECT * FROM test WHERE k2 IN (4, 6, 8, 10);
colodb=# /*+ IndexScan(test) */ EXPLAIN (ANALYZE, DEBUG, DIST) SELECT * FROM test WHERE k2 IN (4, 6, 8, 10);
                                                      QUERY PLAN                                                       
-----------------------------------------------------------------------------------------------------------------------
 Index Scan using test_pkey on test  (cost=180.00..1130.52 rows=80 width=8) (actual time=6.214..6.278 rows=80 loops=1)
   Index Cond: (k2 = ANY ('{4,6,8,10}'::integer[]))
...
   Metric rocksdb_number_db_seek: 41.000
   Metric rocksdb_number_db_next: 200.000
...
   Estimated Seeks: 100
   Estimated Nexts: 200
...

In the following case however, when keys are further apart, DocDB must perform seeks. In this case, the estimates from the model are correct.

# /*+ IndexScan(test) */ EXPLAIN (ANALYZE, DEBUG, DIST) SELECT * FROM test WHERE k2 IN (4, 7, 10, 13);
                                                      QUERY PLAN                                                       
-----------------------------------------------------------------------------------------------------------------------
 Index Scan using test_pkey on test  (cost=180.00..1130.52 rows=80 width=8) (actual time=3.632..3.695 rows=80 loops=1)
   Index Cond: (k2 = ANY ('{4,7,10,13}'::integer[]))
...
   Metric rocksdb_number_db_seek: 101.000
   Metric rocksdb_number_db_next: 200.000
...
   Estimated Seeks: 100
   Estimated Nexts: 200
...

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.