• Heikki Linnakangas's avatar
    Add support for building GiST index by sorting. · 16fa9b2b
    Heikki Linnakangas authored
    This adds a new optional support function to the GiST access method:
    sortsupport. If it is defined, the GiST index is built by sorting all data
    to the order defined by the sortsupport's comparator function, and packing
    the tuples in that order to GiST pages. This is similar to how B-tree
    index build works, and is much faster than inserting the tuples one by
    one. The resulting index is smaller too, because the pages are packed more
    tightly, upto 'fillfactor'. The normal build method works by splitting
    pages, which tends to lead to more wasted space.
    
    The quality of the resulting index depends on how good the opclass-defined
    sort order is. A good order preserves locality of the input data.
    
    As the first user of this facility, add 'sortsupport' function to the
    point_ops opclass. It sorts the points in Z-order (aka Morton Code), by
    interleaving the bits of the X and Y coordinates.
    
    Author: Andrey Borodin
    Reviewed-by: Pavel Borisov, Thomas Munro
    Discussion: https://www.postgresql.org/message-id/1A36620E-CAD8-4267-9067-FB31385E7C0D%40yandex-team.ru
    16fa9b2b
tuplesort.c 141 KB