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

Anastasia Lubennikova <a.lubennikova@postgrespro.ru>

From: Anastasia Lubennikova <a.lubennikova@postgrespro.ru>

To: pgsql-hackers@postgresql.org

Date: 2019-07-04T12:06:38Z

Lists: pgsql-hackers

Attachments

btree_compression_pg12_v1.patch (text/x-patch) patch v1
btree_compression_test_result.png (image/png)

The new version of the patch is attached.
This version is even simpler than the previous one,
thanks to the recent btree design changes and all the feedback I received.
I consider it ready for review and testing.

[feature overview]
This patch implements the deduplication of btree non-pivot tuples on 
leaf pages
in a manner similar to GIN index "posting lists".

Non-pivot posting tuple has following format:
t_tid | t_info | key values | posting_list[]

Where t_tid and t_info fields are used to store meta info
about tuple's posting list.
posting list is an array of ItemPointerData.

Currently, compression is applied to all indexes except system indexes, 
unique
indexes, and indexes with included columns.

On insertion, compression applied not to each tuple, but to the page before
split. If the target page is full, we try to compress it.

[benchmark results]
idx ON tbl(c1);
index contains 10000000 integer values

i - number of distinct values in the index.
So i=1 means that all rows have the same key,
and i=10000000 means that all keys are different.

i / old size (MB) / new size (MB)
1            215    88
1000        215    90
100000        215    71
10000000    214    214

For more, see the attached diagram with test results.

[future work]
Many things can be improved in this feature.
Personally, I'd prefer to keep this patch as small as possible
and work on other improvements after a basic part is committed.
Though, I understand that some of these can be considered essential
for this patch to be approved.

1. Implement a split of the posting tuples on a page split.
2. Implement microvacuum of posting tuples.
3. Add a flag into pg_index, which allows enabling/disabling compression
for a particular index.
4. Implement posting list compression.

-- 
Anastasia Lubennikova
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company

Commits

Teach pageinspect about nbtree deduplication.
- 93ee38eade1b 13.0 landed
Doc: Fix deduplicate_items index term.
- e537aed61db7 13.0 landed
Revise BTP_HAS_GARBAGE nbtree VACUUM comments.
- 4b25f5d0ba01 13.0 cited
Remove unneeded "pin scan" nbtree VACUUM code.
- 9f83468b3536 13.0 landed
Cleanup code in reloptions.h regarding reloption handling
- 50d22de9325f 13.0 cited
Catch invalid typlens in a couple of places
- 8557a6f10ca6 13.0 cited
Compute XID horizon for page level index vacuum on primary.
- 558a9165e081 12.0 cited
Make heap TID a tiebreaker nbtree index column.
- dd299df8189b 12.0 cited
Avoid pin scan for replay of XLOG_BTREE_VACUUM in all cases
- 3e4b7d87988f 9.6.0 cited
Revert buggy optimization of index scans
- c7111d11b188 9.6.0 cited
Restructure index access method API to hide most of it at the C level.
- 65c5fcd353a8 9.6.0 cited
Reduce pinning and buffer content locking for btree scans.
- 2ed5b87f96d4 9.5.0 cited
Avoid scanning nulls at the beginning of a btree index scan.
- 1a77f8b63d15 9.2.0 cited