Add IntegerSet, to hold large sets of 64-bit ints efficiently.
authorHeikki Linnakangas <heikki.linnakangas@iki.fi>
Fri, 22 Mar 2019 11:21:19 +0000 (13:21 +0200)
committerHeikki Linnakangas <heikki.linnakangas@iki.fi>
Fri, 22 Mar 2019 11:21:45 +0000 (13:21 +0200)
commitdf816f6ad532ad685a3897869a2e64d3a53fe312
tree454bf3a2ffd9a19afb36073e91b090eae96e0de1
parent5e1963fb764e9cc092e0f7b58b28985c311431d9
Add IntegerSet, to hold large sets of 64-bit ints efficiently.

The set is implemented as a B-tree, with a compact representation at leaf
items, using Simple-8b algorithm, so that clusters of nearby values use
less memory.

The IntegerSet isn't used for anything yet, aside from the test code, but
we have two patches in the works that would benefit from this: A patch to
allow GiST vacuum to delete empty pages, and a patch to reduce heap
VACUUM's memory usage, by storing the list of dead TIDs more efficiently
and lifting the 1 GB limit on its size.

This includes a unit test module, in src/test/modules/test_integerset.
It can be used to verify correctness, as a regression test, but if you run
it manully, it can also print memory usage and execution time of some of
the tests.

Author: Heikki Linnakangas, Andrey Borodin
Reviewed-by: Julien Rouhaud
Discussion: https://www.postgresql.org/message-id/b5e82599-1966-5783-733c-1a947ddb729f@iki.fi
13 files changed:
src/backend/lib/Makefile
src/backend/lib/README
src/backend/lib/integerset.c [new file with mode: 0644]
src/include/lib/integerset.h [new file with mode: 0644]
src/test/modules/Makefile
src/test/modules/test_integerset/.gitignore [new file with mode: 0644]
src/test/modules/test_integerset/Makefile [new file with mode: 0644]
src/test/modules/test_integerset/README [new file with mode: 0644]
src/test/modules/test_integerset/expected/test_integerset.out [new file with mode: 0644]
src/test/modules/test_integerset/sql/test_integerset.sql [new file with mode: 0644]
src/test/modules/test_integerset/test_integerset--1.0.sql [new file with mode: 0644]
src/test/modules/test_integerset/test_integerset.c [new file with mode: 0644]
src/test/modules/test_integerset/test_integerset.control [new file with mode: 0644]