Horton

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

Peter Geoghegan <pg@bowt.ie>

View thread View on postgr.es
From: Peter Geoghegan <pg@bowt.ie>
To: Robert Haas <robertmhaas@gmail.com>
Cc: Anastasia Lubennikova <a.lubennikova@postgrespro.ru>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2019-11-16T00:04:44Z
Lists: pgsql-hackers 
On Fri, Nov 15, 2019 at 5:16 AM Robert Haas <robertmhaas@gmail.com> wrote:
> Hmm. Well, maybe I'm just behind the times. But that same wikipedia
> article also says that deduplication works on large chunks "such as
> entire files or large sections of files" thus differentiating it from
> compression algorithms which work on the byte level, so it seems to me
> that what you are doing still sounds more like ad-hoc compression.

I see your point.

One reason for my avoiding the word "compression" is that other DB
systems that have something similar don't use the word compression
either. Actually, they don't really call it *anything*. Posting lists
are simply the way that secondary indexes work. The "Modern B-Tree
techniques" book/survey paper mentions the idea of using a TID list in
its "3.7 Duplicate Key Values" section, not in the two related
sections that follow ("Bitmap Indexes", and "Data Compression").

That doesn't seem like a very good argument, now that I've typed it
out. The patch applies deduplication/compression/whatever at the point
where we'd otherwise have to split the page, unlike GIN. GIN eagerly
maintains posting lists (doing in-place updates for most insertions
seems pretty bad to me). My argument could reasonably be made about
GIN, which really does consider posting lists the natural way to store
duplicate tuples. I cannot really make that argument about nbtree with
this patch, though -- delaying a page split by re-encoding tuples
(changing their physical representation without changing their logical
contents) justifies using the word "compression" in the name.

> > Can you suggest an alternative?
>
> My instinct is to pick a name that somehow involves compression and
> just put enough other words in there to make it clear e.g. duplicate
> value compression, or something of that sort.

Does anyone else want to weigh in on this? Anastasia?

I will go along with whatever the consensus is. I'm very close to the
problem we're trying to solve, which probably isn't helping me here.

--
Peter Geoghegan

Commits

  1. Teach pageinspect about nbtree deduplication.

  2. Doc: Fix deduplicate_items index term.

  3. Revise BTP_HAS_GARBAGE nbtree VACUUM comments.

  4. Remove unneeded "pin scan" nbtree VACUUM code.

  5. Cleanup code in reloptions.h regarding reloption handling

  6. Catch invalid typlens in a couple of places

  7. Compute XID horizon for page level index vacuum on primary.

  8. Make heap TID a tiebreaker nbtree index column.

  9. Avoid pin scan for replay of XLOG_BTREE_VACUUM in all cases

  10. Revert buggy optimization of index scans

  11. Restructure index access method API to hide most of it at the C level.

  12. Reduce pinning and buffer content locking for btree scans.

  13. Avoid scanning nulls at the beginning of a btree index scan.