Use a pairing heap for the priority queue in kNN-GiST searches

Enterprise / PostgreSQL - Heikki Linnakangas [iki.fi] - 22 December 2014 04:05 UTC

This performs slightly better, uses less memory, and needs slightly less code in GiST, than the Red-Black tree previously used.

Reviewed by Peter Geoghegan

e703261 Use a pairing heap for the priority queue in kNN-GiST searches.
src/backend/access/gist/gistget.c | 71 +++-------
src/backend/access/gist/gistscan.c | 75 ++--------
src/backend/lib/Makefile | 2 +-
src/backend/lib/README | 24 ++++
src/backend/lib/pairingheap.c | 274 ++++++++++++++++++++++++++++++++++++
src/include/access/gist_private.h | 25 +---
src/include/lib/pairingheap.h | 72 ++++++++++
7 files changed, 409 insertions(+), 134 deletions(-)

Upstream: git.postgresql.org

  • Share