git.postgresql.org Git - postgresql.git/commit

git projects / postgresql.git / commit

Teach tuplesort.c about "top N" sorting, in which only the first N tuples

author Tom Lane <tgl@sss.pgh.pa.us>

Fri, 4 May 2007 01:13:45 +0000 (01:13 +0000)

committer Tom Lane <tgl@sss.pgh.pa.us>

Fri, 4 May 2007 01:13:45 +0000 (01:13 +0000)

commit d26559dbf356736923b26704ce76ca820ff3a2b0

tree e899e3b4eb9f0d34f598816f69a9a60379987391 tree

parent 0fef38da215cdc9b01b1b623c2e37d7414b91843 commit | diff

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 diff | blob | blame | history

src/backend/executor/nodeSort.c diff | blob | blame | history

src/backend/optimizer/path/costsize.c diff | blob | blame | history

src/backend/optimizer/plan/createplan.c diff | blob | blame | history

src/backend/optimizer/plan/planmain.c diff | blob | blame | history

src/backend/optimizer/plan/planner.c diff | blob | blame | history

src/backend/optimizer/util/pathnode.c diff | blob | blame | history

src/backend/utils/misc/guc.c diff | blob | blame | history

src/backend/utils/sort/tuplesort.c diff | blob | blame | history

src/include/nodes/execnodes.h diff | blob | blame | history

src/include/optimizer/cost.h diff | blob | blame | history

src/include/optimizer/planmain.h diff | blob | blame | history

src/include/utils/tuplesort.h diff | blob | blame | history

This is the main PostgreSQL git repository.

RSS Atom