Re: [HACKERS] [WIP] Effective storage of duplicates in B-tree index.

From: Anastasia Lubennikova <a(dot)lubennikova(at)postgrespro(dot)ru>
To: pgsql-hackers(at)lists(dot)postgresql(dot)org
Subject: Re: [HACKERS] [WIP] Effective storage of duplicates in B-tree index.
Date: 2019-08-16 15:56:12
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers

13.08.2019 18:45, Anastasia Lubennikova wrote:
>>   I also added a nearby FIXME comment to
>> _bt_insertonpg_in_posting() -- I don't think think that the code for
>> splitting a posting list in two is currently crash-safe.
> Good catch. It seems, that I need to rearrange the code.
> I'll send updated patch this week.

Attached is v7.

In this version of the patch, I heavily refactored the code of insertion
posting tuple. bt_split logic is quite complex, so I omitted a couple of
optimizations. They are mentioned in TODO comments.

Now the algorithm is the following:

- If bt_findinsertloc() found out that tuple belongs to existing posting
TID interval, it sets 'in_posting_offset' variable and passes it to

- If 'in_posting_offset' is valid and origtup is valid,
merge our itup into origtup.

It can result in one tuple neworigtup, that must replace origtup; or two
neworigtup and newrighttup, if the result exceeds BTMaxItemSize,

- If two new tuple(s) fit into the old page, we're lucky.
call _bt_delete_and_insert(..., neworigtup, newrighttup, newitemoff) to
atomically replace oldtup with new tuple(s) and generate xlog record.

- In case page split is needed, pass both tuples to _bt_split().
 _bt_findsplitloc() is now aware of upcoming replacement of origtup with
neworigtup, so it uses correct item size where needed.

It seems that now all replace operations are crash-safe. The new patch
all regression tests, so I think it's ready for review again.

In the meantime, I'll run more stress-tests.

Anastasia Lubennikova
Postgres Professional:
The Russian Postgres Company

Attachment Content-Type Size
v7-0001-Compression-deduplication-in-nbtree.patch text/x-patch 105.4 KB

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Hadi Moshayedi 2019-08-16 16:44:15 REL_12_STABLE crashing with assertion failure in ExtractReplicaIdentity
Previous Message Tom Lane 2019-08-16 15:30:50 Re: UNION ALL