Re: Sparse bit set data structure

Andrey Borodin <x4mmm@yandex-team.ru>

From: Andrey Borodin <x4mmm@yandex-team.ru>

To: Heikki Linnakangas <hlinnaka@iki.fi>

Cc: pgsql-hackers <pgsql-hackers@postgresql.org>, Claudio Freire <klaussfreire@gmail.com>

Date: 2019-03-14T05:15:58Z

Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

Add IntegerSet, to hold large sets of 64-bit ints efficiently.
- df816f6ad532 12.0 landed

Hi!

> 14 марта 2019 г., в 0:18, Heikki Linnakangas <hlinnaka@iki.fi> написал(а):
> <0001-Add-SparseBitset-to-hold-a-large-set-of-64-bit-ints-.patch><0002-Andrey-Borodin-s-test_blockset-tool-adapted-for-Spar.patch>

That is very interesting idea. Basically, B-tree and radix tree is a tradeoff between space and time.

In general, lookup into radix tree will touch less CPU cache lines.
In this terms Bitmapset is on most performant and memory-wasteful side: lookup into Bitmapset is always 1 cache line.
Performance of radix tree can be good in case of skewed distribution, while B-tree will be OK on uniform. I think that distribution of GiST inner pages is uniform, distribution of empty leafs is... I have no idea, let's consider uniform too.

I'd review this data structure ASAP. I just need to understand: do we aim to v12 or v13? (I did not solve concurrency issues in GiST VACUUM yet, but will fix them at weekend)

Also, maybe we should consider using RoaringBitmaps? [0]
As a side not I would add that while balanced trees are widely used for operations on external memory, there are more performant versions for main memory. Like AVL-tree and RB-tree.


Brest regards, Andrey Borodin.

[0] https://github.com/RoaringBitmap/CRoaring