From: | Peter Geoghegan <pg(at)bowt(dot)ie> |
---|---|
To: | Matthias van de Meent <boekewurm+postgres(at)gmail(dot)com> |
Cc: | PostgreSQL Hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: [patch] _bt_binsrch* improvements - equal-prefix-skip binary search |
Date: | 2020-09-11 17:41:01 |
Message-ID: | CAH2-WznPxocJKaz=XMqKqPauawi-vtB62oXT9SkHhDNb7cpV9Q@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
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?
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
From | Date | Subject | |
---|---|---|---|
Next Message | Tomas Vondra | 2020-09-11 18:05:10 | Re: WIP: BRIN multi-range indexes |
Previous Message | Ranier Vilela | 2020-09-11 17:10:31 | Re: Simplified version of read_binary_file (src/backend/utils/adt/genfile.c) |