Use abbreviated keys for faster sorting of text datums.
authorRobert Haas <rhaas@postgresql.org>
Mon, 19 Jan 2015 20:20:31 +0000 (15:20 -0500)
committerRobert Haas <rhaas@postgresql.org>
Mon, 19 Jan 2015 20:28:27 +0000 (15:28 -0500)
commit4ea51cdfe85ceef8afabceb03c446574daa0ac23
tree703433dfca58c84f8b947b6f4f562ecdf98f1669
parent1605291b6c14be92915948d17f5509191632c97f
Use abbreviated keys for faster sorting of text datums.

This commit extends the SortSupport infrastructure to allow operator
classes the option to provide abbreviated representations of Datums;
in the case of text, we abbreviate by taking the first few characters
of the strxfrm() blob.  If the abbreviated comparison is insufficent
to resolve the comparison, we fall back on the normal comparator.
This can be much faster than the old way of doing sorting if the
first few bytes of the string are usually sufficient to resolve the
comparison.

There is the potential for a performance regression if all of the
strings to be sorted are identical for the first 8+ characters and
differ only in later positions; therefore, the SortSupport machinery
now provides an infrastructure to abort the use of abbreviation if
it appears that abbreviation is producing comparatively few distinct
keys.  HyperLogLog, a streaming cardinality estimator, is included in
this commit and used to make that determination for text.

Peter Geoghegan, reviewed by me.
13 files changed:
src/backend/access/nbtree/nbtsort.c
src/backend/commands/analyze.c
src/backend/executor/nodeAgg.c
src/backend/executor/nodeMergeAppend.c
src/backend/executor/nodeMergejoin.c
src/backend/lib/Makefile
src/backend/lib/hyperloglog.c [new file with mode: 0644]
src/backend/utils/adt/orderedsetaggs.c
src/backend/utils/adt/varlena.c
src/backend/utils/sort/tuplesort.c
src/include/lib/hyperloglog.h [new file with mode: 0644]
src/include/pg_config_manual.h
src/include/utils/sortsupport.h