Teach tuplesort.c about "top N" sorting, in which only the first N tuples
authorTom Lane <tgl@sss.pgh.pa.us>
Fri, 4 May 2007 01:13:45 +0000 (01:13 +0000)
committerTom Lane <tgl@sss.pgh.pa.us>
Fri, 4 May 2007 01:13:45 +0000 (01:13 +0000)
commit211e8da7eac500cffcbbea482eab964ac9c3a094
tree3d85b4eb151cbaf8dd2778404c7b2ee8ed2ad220
parentf12e4adf8ac16373d328fe622320c6b8afb2ac58
Teach tuplesort.c about "top N" sorting, in which only the first N tuples
need be returned.  We keep a heap of the current best N tuples and sift-up
new tuples into it as we scan the input.  For M input tuples this means
only about M*log(N) comparisons instead of M*log(M), not to mention a lot
less workspace when N is small --- avoiding spill-to-disk for large M
is actually the most attractive thing about it.  Patch includes planner
and executor support for invoking this facility in ORDER BY ... LIMIT
queries.  Greg Stark, with some editorialization by moi.
13 files changed:
src/backend/executor/nodeLimit.c
src/backend/executor/nodeSort.c
src/backend/optimizer/path/costsize.c
src/backend/optimizer/plan/createplan.c
src/backend/optimizer/plan/planmain.c
src/backend/optimizer/plan/planner.c
src/backend/optimizer/util/pathnode.c
src/backend/utils/misc/guc.c
src/backend/utils/sort/tuplesort.c
src/include/nodes/execnodes.h
src/include/optimizer/cost.h
src/include/optimizer/planmain.h
src/include/utils/tuplesort.h