Re: [patch] _bt_binsrch* improvements - equal-prefix-skip binary search

On Fri, Sep 11, 2020 at 7:57 AM Matthias van de Meent
<boekewurm+postgres(at)gmail(dot)com> wrote:
> I've not yet been involved in postgresql's development process, so here's a first. Please find attached a patch for improving the BT binary search speeds, with accompanying performance data.
>
> v1-0001 adapts _bt_compare and _bt_binsrch* to make use of static properties of L&Y-style nbtree indexes to speed up finding an initial position in the nbtee.

Are you familiar with this thread?

https://www.postgresql.org/message-id/CAH2-Wzn_NAyK4pR0HRWO0StwHmxjP5qyu+X8vppt030XpqrO6w@mail.gmail.com

I wrote a patch that implemented the same idea, which is sometimes
called dynamic prefix truncation. I found some very subtle problems
with it, though. Concurrent page deletions could occur, which could
cause a scan that skips a prefix to miss that the page it landed on
doesn't have the same common prefix anymore.

> there could be a large throughput increase for short strings if the collation lookup from lc_collate_is_c() in varstr_cmp could be reused in the subsequent call to pg_newlocale_from_collation()

I noticed that myself recently.

--
Peter Geoghegan