Re: [HACKERS] ORDER BY optimisations - Mailing list pgsql-hackers

>
> 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@debis.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;
  }

  /*