Skip site navigation (1) Skip section navigation (2)

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

From: tgl(at)postgresql(dot)org (Tom Lane)
To: pgsql-committers(at)postgresql(dot)org
Subject: pgsql: Teach tuplesort.c about "top N" sorting, in which only the first
Date: 2007-05-04 01:13:45
Message-ID: 20070504011345.C50559FB9BB@postgresql.org (view raw or flat)
Thread:
Lists: pgsql-committerspgsql-hackers
Log Message:
-----------
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.

Modified Files:
--------------
    pgsql/src/backend/executor:
        nodeLimit.c (r1.29 -> r1.30)
        (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/executor/nodeLimit.c.diff?r1=1.29&r2=1.30)
        nodeSort.c (r1.60 -> r1.61)
        (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/executor/nodeSort.c.diff?r1=1.60&r2=1.61)
    pgsql/src/backend/optimizer/path:
        costsize.c (r1.181 -> r1.182)
        (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/path/costsize.c.diff?r1=1.181&r2=1.182)
    pgsql/src/backend/optimizer/plan:
        createplan.c (r1.229 -> r1.230)
        (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/plan/createplan.c.diff?r1=1.229&r2=1.230)
        planmain.c (r1.100 -> r1.101)
        (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/plan/planmain.c.diff?r1=1.100&r2=1.101)
        planner.c (r1.218 -> r1.219)
        (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/plan/planner.c.diff?r1=1.218&r2=1.219)
    pgsql/src/backend/optimizer/util:
        pathnode.c (r1.139 -> r1.140)
        (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/util/pathnode.c.diff?r1=1.139&r2=1.140)
    pgsql/src/backend/utils/misc:
        guc.c (r1.389 -> r1.390)
        (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/utils/misc/guc.c.diff?r1=1.389&r2=1.390)
    pgsql/src/backend/utils/sort:
        tuplesort.c (r1.74 -> r1.75)
        (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/utils/sort/tuplesort.c.diff?r1=1.74&r2=1.75)
    pgsql/src/include/nodes:
        execnodes.h (r1.172 -> r1.173)
        (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/nodes/execnodes.h.diff?r1=1.172&r2=1.173)
    pgsql/src/include/optimizer:
        cost.h (r1.85 -> r1.86)
        (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/optimizer/cost.h.diff?r1=1.85&r2=1.86)
        planmain.h (r1.100 -> r1.101)
        (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/optimizer/planmain.h.diff?r1=1.100&r2=1.101)
    pgsql/src/include/utils:
        tuplesort.h (r1.25 -> r1.26)
        (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/utils/tuplesort.h.diff?r1=1.25&r2=1.26)

Responses

pgsql-hackers by date

Next:From: Tom LaneDate: 2007-05-04 03:42:32
Subject: Re: Bitmap Heap Scan anomaly
Previous:From: Jeff DavisDate: 2007-05-03 23:50:42
Subject: Re: Bitmap Heap Scan anomaly

pgsql-committers by date

Next:From: Tom LaneDate: 2007-05-04 02:01:02
Subject: pgsql: A few fixups in error handling: mark pg_re_throw() as noreturn
Previous:From: Tom LaneDate: 2007-05-03 16:45:59
Subject: pgsql: Tweak hash index AM to use the new ReadOrZeroBuffer bufmgr API

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group