pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Tom Lane <tgl@sss.pgh.pa.us>
To: Tomaz Borstnar <tomaz.borstnar@over.net>
Cc: pgsql-performance@postgresql.org
Subject: Re: any way to use indexscan to get last X values with "order by Y limit X" clause?
Date: Sun, 15 Jun 2003 12:53:10 -0400
Message-ID: <23329.1055695990@sss.pgh.pa.us> (raw)
In-Reply-To: <5.2.1.1.0.20030615161722.025c7630@127.0.0.1>
References: <5.2.1.1.0.20030615161722.025c7630@127.0.0.1>

Tomaz Borstnar <tomaz.borstnar@over.net> writes:
> SELECT thread, modifystamp, count(id) AS tcount, abstime(modifystamp) AS 
> latest, max(id) as maxid FROM tjavendan WHERE approved='Y'  GROUP BY 
> thread, modifystamp ORDER BY modifystamp desc, thread desc limit 40

> Having backwards reading of index would really help here.

The only way that a fast-start plan is useful is if there is a way to do
it with no explicit sort steps at all.  A sort step must read its entire
input before it can produce any output, so you completely blow the
chance of not reading the whole table as soon as there's any sorting.

There are a couple of reasons why this query can't be done using only an
initial indexscan to sort the data:

1. You don't have a suitable index.  Neither an index on modifystamp
alone nor an index on thread alone is of any use to produce a two-column
ordering; you need a two-column index on (modifystamp, thread).

2. The GROUP BY and ORDER BY steps require different sort orders, and so
even if an index satisfied one, there'd still be a sort needed for the
other.  This is partly your fault (writing the columns in different
orders) and partly the system's fault: it's implicitly taking the GROUP
BY entries to be equivalent to ORDER BY ASC, which is overspecification.

I've applied the attached patch to CVS tip to cure the latter problem.
With this, a two-column index, and compatible column ordering in ORDER
BY and GROUP BY, I get a reasonable-looking fast-start plan.  The patch
will not apply exactly against 7.3 because there's a renamed function
call in there, but you could make it work with a little effort.

			regards, tom lane


inline patch 1: src/backend/parser/analyze.c, src/backend/parser/parse_clause.c, src/include/parser/parse_clause.h (+40/-14 lines) download inline-1.patch*** src/backend/parser/analyze.c.orig Fri Jun 6 11:04:02 2003 --- src/backend/parser/analyze.c Sun Jun 15 12:05:34 2003 *************** *** 1787,1799 **** */ qry->havingQual = transformWhereClause(pstate, stmt->havingClause); ! qry->groupClause = transformGroupClause(pstate, ! stmt->groupClause, ! qry->targetList); ! qry->sortClause = transformSortClause(pstate, stmt->sortClause, qry->targetList); qry->distinctClause = transformDistinctClause(pstate, stmt->distinctClause, --- 1787,1804 ---- */ qry->havingQual = transformWhereClause(pstate, stmt->havingClause); ! /* ! * Transform sorting/grouping stuff. Do ORDER BY first because both ! * transformGroupClause and transformDistinctClause need the results. ! */ qry->sortClause = transformSortClause(pstate, stmt->sortClause, qry->targetList); + + qry->groupClause = transformGroupClause(pstate, + stmt->groupClause, + qry->targetList, + qry->sortClause); qry->distinctClause = transformDistinctClause(pstate, stmt->distinctClause, *** src/backend/parser/parse_clause.c.orig Fri Jun 6 11:04:02 2003 --- src/backend/parser/parse_clause.c Sun Jun 15 12:19:14 2003 *************** *** 1124,1130 **** * transform a GROUP BY clause */ List * ! transformGroupClause(ParseState *pstate, List *grouplist, List *targetlist) { List *glist = NIL, *gl; --- 1124,1131 ---- * transform a GROUP BY clause */ List * ! transformGroupClause(ParseState *pstate, List *grouplist, ! List *targetlist, List *sortClause) { List *glist = NIL, *gl; *************** *** 1132,1152 **** foreach(gl, grouplist) { TargetEntry *tle; tle = findTargetlistEntry(pstate, lfirst(gl), targetlist, GROUP_CLAUSE); /* avoid making duplicate grouplist entries */ ! if (!targetIsInSortList(tle, glist)) ! { ! GroupClause *grpcl = makeNode(GroupClause); ! ! grpcl->tleSortGroupRef = assignSortGroupRef(tle, targetlist); ! grpcl->sortop = ordering_oper_opid(tle->resdom->restype); ! ! glist = lappend(glist, grpcl); } } return glist; --- 1133,1173 ---- foreach(gl, grouplist) { TargetEntry *tle; + Oid ordering_op; + GroupClause *grpcl; tle = findTargetlistEntry(pstate, lfirst(gl), targetlist, GROUP_CLAUSE); /* avoid making duplicate grouplist entries */ ! if (targetIsInSortList(tle, glist)) ! continue; ! /* ! * If the GROUP BY clause matches the ORDER BY clause, we want to ! * adopt the ordering operators from the latter rather than using ! * the default ops. This allows "GROUP BY foo ORDER BY foo DESC" to ! * be done with only one sort step. Note we are assuming that any ! * user-supplied ordering operator will bring equal values together, ! * which is all that GROUP BY needs. ! */ ! if (sortClause && ! ((SortClause *) lfirst(sortClause))->tleSortGroupRef == ! tle->resdom->ressortgroupref) ! { ! ordering_op = ((SortClause *) lfirst(sortClause))->sortop; ! sortClause = lnext(sortClause); } + else + { + ordering_op = ordering_oper_opid(tle->resdom->restype); + sortClause = NIL; /* disregard ORDER BY once match fails */ + } + + grpcl = makeNode(GroupClause); + grpcl->tleSortGroupRef = assignSortGroupRef(tle, targetlist); + grpcl->sortop = ordering_op; + glist = lappend(glist, grpcl); } return glist; *** src/include/parser/parse_clause.h.orig Fri Mar 21 20:49:38 2003 --- src/include/parser/parse_clause.h Sun Jun 15 12:03:13 2003 *************** *** 22,28 **** extern bool interpretInhOption(InhOption inhOpt); extern Node *transformWhereClause(ParseState *pstate, Node *where); extern List *transformGroupClause(ParseState *pstate, List *grouplist, ! List *targetlist); extern List *transformSortClause(ParseState *pstate, List *orderlist, List *targetlist); extern List *transformDistinctClause(ParseState *pstate, List *distinctlist, --- 22,28 ---- extern bool interpretInhOption(InhOption inhOpt); extern Node *transformWhereClause(ParseState *pstate, Node *where); extern List *transformGroupClause(ParseState *pstate, List *grouplist, ! List *targetlist, List *sortClause); extern List *transformSortClause(ParseState *pstate, List *orderlist, List *targetlist); extern List *transformDistinctClause(ParseState *pstate, List *distinctlist,

view thread (10+ messages)  latest in thread

Message-ID: <23329.1055695990@sss.pgh.pa.us>
Permalink:  ../23329.1055695990@sss.pgh.pa.us/
Also on:    postgresql.org/message-id/23329.1055695990@sss.pgh.pa.us

 ·  · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-performance@postgresql.org
  Cc: tgl@sss.pgh.pa.us, tomaz.borstnar@over.net
  Subject: Re: any way to use indexscan to get last X values with "order by Y limit X" clause?
  In-Reply-To: <23329.1055695990@sss.pgh.pa.us>
  References: <5.2.1.1.0.20030615161722.025c7630@127.0.0.1> <23329.1055695990@sss.pgh.pa.us>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox