• Heikki Linnakangas's avatar
    Add IntegerSet, to hold large sets of 64-bit ints efficiently. · df816f6a
    Heikki Linnakangas authored
    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
    df816f6a
test_integerset.sql 400 Bytes