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
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-committers pgsql-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

Browse pgsql-committers by date

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

Browse pgsql-hackers by date

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