Re: Index range search optimization

Hi!

On Fri, Jun 23, 2023 at 10:36 AM Konstantin Knizhnik <knizhnik(at)garret(dot)ru>
wrote:

> _bt_readpage performs key check for each item on the page trying to locate
> upper boundary.
> While comparison of simple integer keys are very fast, comparison of long
> strings can be quite expensive.
> We can first make check for the largest key on the page and if it is not
> larger than upper boundary, then skip checks for all elements.
>
> At this quite artificial example such optimization gives 3x time speed-up:
>
> create table t(t text primary key);
> insert into t values ('primary key-'||generate_series(1,10000000)::text);
> select count(*) from t where t between 'primary key-1000000' and 'primary key-2000000';
>
> At my notebook with large enough shared buffers and disabled concurrency
> the difference is 83 vs. 247 msec
> For integer keys the difference is much smaller: 69 vs. 82 msec
>
> Certainly I realized that this example is quite exotic: most of DBAs
> prefer integer keys and such large ranges are quite rare.
> But still such large range queries are used.
> And I have checked that the proposed patch doesn't cause slowdown of exact
> search.
>

Neat optimization! But I wonder if we could do even better. The attached
patch allows Postgres to skip scan keys required for directional scans
(even when other keys are present in the scan). I'll soon post the testing
results and a more polished version of this patch.

------
Regards,
Alexander Korotkov