Thread: pgsql: Add some randomness to the choice of which GiST page to insert t
pgsql: Add some randomness to the choice of which GiST page to insert t
From
Heikki Linnakangas
Date:
Add some randomness to the choice of which GiST page to insert to. When descending the tree for an insert, and there are multiple equally good pages we could insert to, make the choice in random. Previously, we would always choose the tuple with lowest offset number. That meant that when two non-leaf pages overlap - in the extreme case they might have exactly the same key - all but the first such page went unused. That wasn't optimal for space usage; if you deleted some tuples from the non-first pages, the space would never be reused. With this patch, the other pages are sometimes chosen too, although there's still a heavy bias towards low-offset tuples, so that we don't lose cache locality when doing a lot of inserts with similar keys. Original idea by Alexander Korotkov, although this patch version was written by me and copy-edited by Tom Lane. Branch ------ master Details ------- http://git.postgresql.org/pg/commitdiff/ba1cc6501e98aee7d43098b032d6656f243bca5b Modified Files -------------- src/backend/access/gist/gistutil.c | 66 +++++++++++++++++++++++++++++++++-- 1 files changed, 62 insertions(+), 4 deletions(-)