Index range search optimization

From: Konstantin Knizhnik <knizhnik(at)garret(dot)ru>
To: PostgreSQL Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Index range search optimization
Date: 2023-06-23 07:35:50
Message-ID: 079c3f8e-3371-abe2-e93c-fc8a0ae3f571@garret.ru
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Hi hackers.

_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.

Attachment Content-Type Size
range-search.patch text/x-patch 7.2 KB

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Jelte Fennema 2023-06-23 07:39:00 Re: Deleting prepared statements from libpq.
Previous Message Ashutosh Bapat 2023-06-23 07:27:33 Re: Infinite Interval