Re: [HACKERS] ORDER BY optimisations

>
> Hallo Jan,
>
> Do I remember right that your pathes to speed up ORDER BYs (by
> omitting them when not needed) did not make it into 6.4 .
>
> If that is the case, are they available anywhere ?
>
> I really need them (fast) for my new project.
>
> -------------
> Hannu Krosing
>
>

Yepp, it didn't made it.

There where two different ones out, my and one from - hmmm -
was it Tatsuo or Hinoue? My one only suppresses the final
sort if

1. the plan is a Sort->IndexScan,

2. there is an ORDER BY clause,

3. the index choosen by the planner matches ALL attributes
given in the ORDER BY clause (extra indexed attributes
not in ORDER BY ignored),

4. and finally all sort operators are ASCENDING.

There are many debugging printf()'s in the patch and I think
one of them is still active while the others are commented
out. You need to comment out the last one yourself after you
found out that your queries are what causes it to suppress
the sorts.

Anyway, you said you need it fast, so here it is.

Jan

--

#======================================================================#
# It's easier to get forgiveness for being wrong than for being right. #
# Let's break this rule - forgive me. #
#======================================== jwieck(at)debis(dot)com (Jan Wieck) #

diff -cr src.orig/backend/optimizer/plan/planner.c src/backend/optimizer/plan/planner.c
*** src.orig/backend/optimizer/plan/planner.c Wed Oct 14 19:12:36 1998
--- src/backend/optimizer/plan/planner.c Wed Oct 14 23:17:08 1998
***************
*** 48,53 ****
--- 48,59 ----

#include "executor/executor.h"

+ #include "utils/builtins.h"
+ #include "utils/syscache.h"
+ #include "access/genam.h"
+ #include "parser/parse_oper.h"
+
+ static bool need_sortplan(List *sortcls, Plan *plan);
static Plan *make_sortplan(List *tlist, List *sortcls, Plan *plannode);
extern Plan *make_groupPlan(List **tlist, bool tuplePerGroup,
List *groupClause, Plan *subplan);
***************
*** 281,292 ****
}
else
{
! if (parse->sortClause)
return make_sortplan(tlist, parse->sortClause, result_plan);
else
return (Plan *) result_plan;
}

}

/*
--- 287,450 ----
}
else
{
! if (parse->sortClause && need_sortplan(parse->sortClause, result_plan))
return make_sortplan(tlist, parse->sortClause, result_plan);
else
return (Plan *) result_plan;
}

+ }
+
+ static TargetEntry *
+ get_matching_tle(Plan *plan, Resdom *resdom)
+ {
+ List *i;
+ TargetEntry *tle;
+
+ foreach (i, plan->targetlist) {
+ tle = (TargetEntry *)lfirst(i);
+ if (tle->resdom->resno == resdom->resno)
+ return tle;
+ }
+ return NULL;
+ }
+
+ static bool
+ need_sortplan(List *sortcls, Plan *plan)
+ {
+ Relation indexRel;
+ IndexScan *indexScan;
+ Oid indexId;
+ List *i;
+ HeapTuple htup;
+ Form_pg_index index_tup;
+ int key_no = 0;
+
+ /*
+ printf("check if need_sortplan ... ");
+ */
+
+ if (nodeTag(plan) != T_IndexScan) {
+ /*
+ printf("not an index scan\n");
+ */
+ return TRUE;
+ }
+
+ indexScan = (IndexScan *)plan;
+
+ if (plan->lefttree != NULL) {
+ /*
+ printf("scan has lefttree\n");
+ */
+ return TRUE;
+ }
+ if (plan->righttree != NULL) {
+ /*
+ printf("scan has righttree\n");
+ */
+ return TRUE;
+ }
+
+ if (length(indexScan->indxid) != 1) {
+ /*
+ printf("scanning multiple indices\n");
+ */
+ return TRUE;
+ }
+
+ if (length(sortcls) > 8) {
+ /*
+ printf("sort clause too long (>8)\n");
+ */
+ return TRUE;
+ }
+
+ indexId = lfirsti(indexScan->indxid);
+
+ indexRel = index_open(indexId);
+ if (strcmp(nameout(&(indexRel->rd_am->amname)), "btree") != 0) {
+ /*
+ printf("not a btree index\n");
+ */
+ heap_close(indexRel);
+ return TRUE;
+ }
+ heap_close(indexRel);
+
+ htup = SearchSysCacheTuple(INDEXRELID,
+ ObjectIdGetDatum(indexId), 0, 0, 0);
+ if (!HeapTupleIsValid(htup)) {
+ elog(ERROR, "cache lookup for index %d failed", indexId);
+ }
+ index_tup = (Form_pg_index) GETSTRUCT(htup);
+
+ foreach (i, sortcls) {
+ SortClause *sortcl;
+ Resdom *resdom;
+ TargetEntry *tle;
+ Var *var;
+
+ sortcl = (SortClause *) lfirst(i);
+
+ /*
+ printf("\nchecking sortclause %s\n", nodeToString(sortcl));
+ */
+
+ resdom = sortcl->resdom;
+ tle = get_matching_tle(plan, resdom);
+ if (tle == NULL) {
+ /*
+ printf("matching target entry not found\n");
+ */
+ return TRUE;
+ }
+ if (nodeTag(tle->expr) != T_Var) {
+ /*
+ printf("target entry not a Var\n");
+ */
+ return TRUE;
+ }
+ var = (Var *)(tle->expr);
+
+ if (var->varno != indexScan->scan.scanrelid) {
+ /*
+ printf("Var not from scanrelid\n");
+ */
+ return TRUE;
+ }
+
+ if (var->varattno != index_tup->indkey[key_no]) {
+ /*
+ printf("attribute sorted does not match indexed att\n");
+ */
+ return TRUE;
+ }
+
+ if (oprid(oper("<", resdom->restype, resdom->restype, FALSE)) != sortcl->opoid) {
+ /*
+ printf("opoid should be %d - is %d\n",
+ oprid(oper("<", resdom->restype, resdom->restype, FALSE)), sortcl->opoid);
+ */
+ return TRUE;
+ }
+
+ key_no++;
+ }
+ if (key_no < 8 && index_tup->indkey[key_no] != 0) {
+ /*
+ printf("there are more indexed fields! ");
+ */
+ return TRUE;
+ }
+
+ printf("SUPPRESSING sort over index scan\n");
+
+ /*
+ printf("scan = %s\n\n", nodeToString(indexScan));
+ */
+
+ return FALSE;
}

/*