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

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

From: Magnus Hagander <magnus(at)hagander(dot)net>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: pgsql-committers(at)postgresql(dot)org
Subject: Re: pgsql: Teach tuplesort.c about "top N" sorting, in which only the first
Date: 2007-05-04 08:01:07
Message-ID: 20070504080107.GD29747@svr2.hagander.net (view raw or flat)
Thread:
Lists: pgsql-committerspgsql-hackers
Is there some way to see in the generated query plan if this optimisation
is used?

//Magnus


On Thu, May 03, 2007 at 10:13:45PM -0300, Tom Lane wrote:
> 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)
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 6: explain analyze is your friend

In response to

Responses

pgsql-hackers by date

Next:From: User PetereDate: 2007-05-04 10:39:02
Subject: psqlodbc - psqlodbc: Put Autotools-generated files into subdirectory
Previous:From: Marko KreenDate: 2007-05-04 07:53:43
Subject: Re: RETURN QUERY in PL/PgSQL?

pgsql-committers by date

Next:From: Magnus HaganderDate: 2007-05-04 08:01:41
Subject: Re: pgsql: A few fixups in error handling: mark pg_re_throw() as noreturn
Previous:From: Tom LaneDate: 2007-05-04 02:06:13
Subject: pgsql: Suppress a recently-introduced 'variable might be clobbered by

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