Skip to content

2.27.0.0-b122

2.27.0.0-b122: [#26991] YSQL: Improve cost modelling for backward index scans
@gauravk-in gauravk-in tagged this 18 May 10:50 
Summary:
In this change, we improve the cost modeling of backward index scans. Before
this change, we used a heuristic cost factor to model the overhead of backward
index scans.

In this change, we try to estimate the seeks and nexts that will be performed
for backward scans. We also model this correctly depending on whether
`use_fast_backward_scan` gflag is enabled or disabled. This flag is currently
disabled by default in 2024.2 but enabled in later releases.

In the old implementation of backward index scans, we could only build
tuples from DocDB key-value pairs by reading from the top. This meant,
we needed to `seek` to the first key-value pair, then perform a series
of `next` operations to read all key-value pairs for this tuple. Then,
we must seek back to the first key-value pair and perform a `prev`
to move to the last key-value pair for the previous tuple. This means,
for each key-value pair we must do 2 seeks, as many nexts as the
number of key-value pairs for the tuple and 1 prev.

Currently, we cannot predict the number of key-value pairs per tuple.
We assume a single next operation will be needed for each tuple. This
may be improved in the future. There is additional nuance to this
algorithm that has not been modeled in the cost model, we may not
perform nexts if we find a "tombstone" for the tuple, marking the tuple
as deleted. This is also currently not modeled in the cost model for
the sake of simplicity.

In the new implementation of backward index scans, we build the
tuples by reading the key-value pairs in reverse order by performing
`prev` operations. In this way, we avoid expensive seeks.

Currently, we do not have a separate counter for `prev` and we count
them as `nexts`. Once again, there is nuance that has not been
modeled in the cost model.
Jira: DB-16466

Test Plan:
./yb_build.sh --java-test 'org.yb.pgsql.TestPgFastBackwardIndexScan'
./yb_build.sh --java-test 'org.yb.pgsql.TestPgBackwardIndexScan'

Reviewers: mihnea, arybochkin, mtakahara

Reviewed By: mtakahara

Subscribers: yql

Differential Revision: https://phorge.dev.yugabyte.com/D43513
Assets 2
Loading