From 166b5c1def56a8c43536ac64bd0ba92517f67765 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Sun, 9 Jan 2000 00:26:47 +0000 Subject: [PATCH] Another round of planner/optimizer work. This is just restructuring and code cleanup; no major improvements yet. However, EXPLAIN does produce more intuitive outputs for nested loops with indexscans now... --- src/backend/commands/explain.c | 6 +- src/backend/executor/nodeHash.c | 14 +- src/backend/nodes/copyfuncs.c | 54 ++-- src/backend/nodes/equalfuncs.c | 19 +- src/backend/nodes/freefuncs.c | 32 ++- src/backend/nodes/outfuncs.c | 52 ++-- src/backend/nodes/print.c | 6 +- src/backend/nodes/readfuncs.c | 71 +++-- src/backend/optimizer/geqo/geqo_eval.c | 10 +- src/backend/optimizer/geqo/geqo_misc.c | 16 +- src/backend/optimizer/path/allpaths.c | 51 +--- src/backend/optimizer/path/clausesel.c | 214 +++++--------- src/backend/optimizer/path/costsize.c | 458 +++++++++++++++--------------- src/backend/optimizer/path/indxpath.c | 124 ++++----- src/backend/optimizer/path/joinpath.c | 39 +-- src/backend/optimizer/path/joinrels.c | 106 ++----- src/backend/optimizer/path/orindxpath.c | 79 ++---- src/backend/optimizer/path/pathkeys.c | 4 +- src/backend/optimizer/path/prune.c | 6 +- src/backend/optimizer/path/tidpath.c | 23 +- src/backend/optimizer/plan/createplan.c | 300 ++++++++++++-------- src/backend/optimizer/plan/initsplan.c | 74 ++--- src/backend/optimizer/plan/planmain.c | 14 +- src/backend/optimizer/util/pathnode.c | 123 ++------- src/backend/optimizer/util/plancat.c | 475 ++++++++++++++------------------ src/backend/optimizer/util/relnode.c | 16 +- src/backend/utils/adt/selfuncs.c | 21 +- src/include/nodes/nodes.h | 18 +- src/include/nodes/plannodes.h | 14 +- src/include/nodes/relation.h | 106 ++++--- src/include/optimizer/cost.h | 46 ++-- src/include/optimizer/pathnode.h | 31 ++- src/include/optimizer/paths.h | 8 +- src/include/optimizer/plancat.h | 20 +- src/include/optimizer/planmain.h | 5 +- 35 files changed, 1223 insertions(+), 1432 deletions(-) diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c index 95856194ff..e940655cc1 100644 --- a/src/backend/commands/explain.c +++ b/src/backend/commands/explain.c @@ -4,7 +4,7 @@ * * Copyright (c) 1994-5, Regents of the University of California * - * $Id: explain.c,v 1.50 1999/11/23 20:06:48 momjian Exp $ + * $Id: explain.c,v 1.51 2000/01/09 00:26:18 tgl Exp $ * */ @@ -256,8 +256,8 @@ explain_outNode(StringInfo str, Plan *plan, int indent, ExplainState *es) } if (es->printCost) { - appendStringInfo(str, " (cost=%.2f rows=%d width=%d)", - plan->cost, plan->plan_size, plan->plan_width); + appendStringInfo(str, " (cost=%.2f rows=%.0f width=%d)", + plan->cost, plan->plan_rows, plan->plan_width); } appendStringInfo(str, "\n"); diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c index 3d5083a7ba..1995048e2d 100644 --- a/src/backend/executor/nodeHash.c +++ b/src/backend/executor/nodeHash.c @@ -6,7 +6,7 @@ * Copyright (c) 1994, Regents of the University of California * * - * $Id: nodeHash.c,v 1.41 1999/12/16 22:19:44 wieck Exp $ + * $Id: nodeHash.c,v 1.42 2000/01/09 00:26:18 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -227,7 +227,7 @@ HashJoinTable ExecHashTableCreate(Hash *node) { Plan *outerNode; - int ntuples; + double ntuples; int tupsize; double inner_rel_bytes; double hash_table_bytes; @@ -250,9 +250,9 @@ ExecHashTableCreate(Hash *node) * ---------------- */ outerNode = outerPlan(node); - ntuples = outerNode->plan_size; - if (ntuples <= 0) /* force a plausible size if no info */ - ntuples = 1000; + ntuples = outerNode->plan_rows; + if (ntuples <= 0.0) /* force a plausible size if no info */ + ntuples = 1000.0; /* * estimate tupsize based on footprint of tuple in hashtable... but @@ -260,7 +260,7 @@ ExecHashTableCreate(Hash *node) */ tupsize = MAXALIGN(outerNode->plan_width) + MAXALIGN(sizeof(HashJoinTupleData)); - inner_rel_bytes = (double) ntuples *tupsize * FUDGE_FAC; + inner_rel_bytes = ntuples * tupsize * FUDGE_FAC; /* * Target hashtable size is SortMem kilobytes, but not less than @@ -276,7 +276,7 @@ ExecHashTableCreate(Hash *node) * for an average bucket load of NTUP_PER_BUCKET (per virtual * bucket!). */ - totalbuckets = (int) ceil((double) ntuples * FUDGE_FAC / NTUP_PER_BUCKET); + totalbuckets = (int) ceil(ntuples * FUDGE_FAC / NTUP_PER_BUCKET); /* * Count the number of buckets we think will actually fit in the diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c index 884926b9b6..53bb27e329 100644 --- a/src/backend/nodes/copyfuncs.c +++ b/src/backend/nodes/copyfuncs.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.98 1999/12/13 01:26:53 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.99 2000/01/09 00:26:22 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -75,9 +75,9 @@ static void CopyPlanFields(Plan *from, Plan *newnode) { newnode->cost = from->cost; - newnode->plan_size = from->plan_size; + newnode->plan_rows = from->plan_rows; newnode->plan_width = from->plan_width; - newnode->plan_tupperpage = from->plan_tupperpage; + /* state is NOT copied */ newnode->targetlist = copyObject(from->targetlist); newnode->qual = copyObject(from->qual); newnode->lefttree = copyObject(from->lefttree); @@ -962,25 +962,44 @@ static RelOptInfo * _copyRelOptInfo(RelOptInfo *from) { RelOptInfo *newnode = makeNode(RelOptInfo); - int i, - len; - /* ---------------- - * copy remainder of node - * ---------------- - */ newnode->relids = listCopy(from->relids); - newnode->indexed = from->indexed; - newnode->pages = from->pages; - newnode->tuples = from->tuples; - newnode->size = from->size; + newnode->rows = from->rows; newnode->width = from->width; + Node_Copy(from, newnode, targetlist); Node_Copy(from, newnode, pathlist); + /* XXX cheapestpath should point to a member of pathlist? */ Node_Copy(from, newnode, cheapestpath); newnode->pruneable = from->pruneable; + newnode->indexed = from->indexed; + newnode->pages = from->pages; + newnode->tuples = from->tuples; + + Node_Copy(from, newnode, restrictinfo); + Node_Copy(from, newnode, joininfo); + Node_Copy(from, newnode, innerjoin); + + return newnode; +} + +/* ---------------- + * _copyIndexOptInfo + * ---------------- + */ +static IndexOptInfo * +_copyIndexOptInfo(IndexOptInfo *from) +{ + IndexOptInfo *newnode = makeNode(IndexOptInfo); + int i, + len; + + newnode->indexoid = from->indexoid; + newnode->pages = from->pages; + newnode->tuples = from->tuples; + if (from->classlist) { for (len = 0; from->classlist[len] != 0; len++) @@ -1015,10 +1034,6 @@ _copyRelOptInfo(RelOptInfo *from) newnode->indproc = from->indproc; Node_Copy(from, newnode, indpred); - Node_Copy(from, newnode, restrictinfo); - Node_Copy(from, newnode, joininfo); - Node_Copy(from, newnode, innerjoin); - return newnode; } @@ -1120,7 +1135,6 @@ _copyTidPath(TidPath *from) static void CopyJoinPathFields(JoinPath *from, JoinPath *newnode) { - Node_Copy(from, newnode, pathinfo); Node_Copy(from, newnode, outerjoinpath); Node_Copy(from, newnode, innerjoinpath); } @@ -1229,7 +1243,6 @@ _copyRestrictInfo(RestrictInfo *from) * ---------------- */ Node_Copy(from, newnode, clause); - newnode->selectivity = from->selectivity; Node_Copy(from, newnode, subclauseindices); newnode->mergejoinoperator = from->mergejoinoperator; newnode->left_sortop = from->left_sortop; @@ -1617,6 +1630,9 @@ copyObject(void *from) case T_Stream: retval = _copyStream(from); break; + case T_IndexOptInfo: + retval = _copyIndexOptInfo(from); + break; /* * PARSE NODES diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c index cc23555c46..8d4193e1ed 100644 --- a/src/backend/nodes/equalfuncs.c +++ b/src/backend/nodes/equalfuncs.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v 1.54 1999/12/24 06:43:32 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v 1.55 2000/01/09 00:26:23 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -303,6 +303,17 @@ _equalRelOptInfo(RelOptInfo *a, RelOptInfo *b) } static bool +_equalIndexOptInfo(IndexOptInfo *a, IndexOptInfo *b) +{ + /* We treat IndexOptInfos as equal if they refer to the same index. + * Is this sufficient? + */ + if (a->indexoid != b->indexoid) + return false; + return true; +} + +static bool _equalPathKeyItem(PathKeyItem *a, PathKeyItem *b) { if (a->sortop != b->sortop) @@ -358,8 +369,6 @@ _equalJoinPath(JoinPath *a, JoinPath *b) { if (!_equalPath((Path *) a, (Path *) b)) return false; - if (!equal(a->pathinfo, b->pathinfo)) - return false; if (!equal(a->outerjoinpath, b->outerjoinpath)) return false; if (!equal(a->innerjoinpath, b->innerjoinpath)) @@ -469,7 +478,6 @@ _equalRestrictInfo(RestrictInfo *a, RestrictInfo *b) { if (!equal(a->clause, b->clause)) return false; - /* do not check selectivity because of roundoff error worries */ if (!equal(a->subclauseindices, b->subclauseindices)) return false; if (a->mergejoinoperator != b->mergejoinoperator) @@ -792,6 +800,9 @@ equal(void *a, void *b) case T_RelOptInfo: retval = _equalRelOptInfo(a, b); break; + case T_IndexOptInfo: + retval = _equalIndexOptInfo(a, b); + break; case T_PathKeyItem: retval = _equalPathKeyItem(a, b); break; diff --git a/src/backend/nodes/freefuncs.c b/src/backend/nodes/freefuncs.c index 7e9ae5d06f..c11677b5b7 100644 --- a/src/backend/nodes/freefuncs.c +++ b/src/backend/nodes/freefuncs.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/nodes/Attic/freefuncs.c,v 1.29 1999/12/16 22:19:47 wieck Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/Attic/freefuncs.c,v 1.30 2000/01/09 00:26:23 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -730,11 +730,29 @@ _freeRelOptInfo(RelOptInfo *node) freeObject(node->targetlist); freeObject(node->pathlist); - /* is this right? cheapestpath will typically be a pointer into + /* XXX is this right? cheapestpath will typically be a pointer into * pathlist, won't it? */ freeObject(node->cheapestpath); + freeObject(node->restrictinfo); + freeObject(node->joininfo); + freeObject(node->innerjoin); + + pfree(node); +} + +/* ---------------- + * _freeIndexOptInfo + * ---------------- + */ +static void +_freeIndexOptInfo(IndexOptInfo *node) +{ + /* ---------------- + * free remainder of node + * ---------------- + */ if (node->classlist) pfree(node->classlist); @@ -746,10 +764,6 @@ _freeRelOptInfo(RelOptInfo *node) freeObject(node->indpred); - freeObject(node->restrictinfo); - freeObject(node->joininfo); - freeObject(node->innerjoin); - pfree(node); } @@ -837,7 +851,6 @@ _freeTidPath(TidPath *node) static void FreeJoinPathFields(JoinPath *node) { - freeObject(node->pathinfo); freeObject(node->outerjoinpath); freeObject(node->innerjoinpath); } @@ -936,7 +949,7 @@ _freeRestrictInfo(RestrictInfo *node) * ---------------- */ freeObject(node->clause); - /* this is certainly wrong? index RelOptInfos don't belong to + /* this is certainly wrong? IndexOptInfos don't belong to * RestrictInfo... */ freeObject(node->subclauseindices); @@ -1253,6 +1266,9 @@ freeObject(void *node) case T_Stream: _freeStream(node); break; + case T_IndexOptInfo: + _freeIndexOptInfo(node); + break; /* * PARSE NODES diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index 7907f1b62e..1c8754fef5 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -5,7 +5,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: outfuncs.c,v 1.100 1999/12/13 01:26:53 tgl Exp $ + * $Id: outfuncs.c,v 1.101 2000/01/09 00:26:23 tgl Exp $ * * NOTES * Every (plan) node in POSTGRES has an associated "out" routine which @@ -265,9 +265,9 @@ static void _outPlanInfo(StringInfo str, Plan *node) { appendStringInfo(str, - ":cost %g :size %d :width %d :state %s :qptargetlist ", + ":cost %g :rows %.0f :width %d :state %s :qptargetlist ", node->cost, - node->plan_size, + node->plan_rows, node->plan_width, node->state ? "not-NULL" : "<>"); _outNode(str, node->targetlist); @@ -834,6 +834,7 @@ _outEState(StringInfo str, EState *node) /* * Stuff from relation.h */ + static void _outRelOptInfo(StringInfo str, RelOptInfo *node) { @@ -841,12 +842,12 @@ _outRelOptInfo(StringInfo str, RelOptInfo *node) _outIntList(str, node->relids); appendStringInfo(str, - " :indexed %s :pages %u :tuples %u :size %u :width %u :targetlist ", + " :rows %.0f :width %d :indexed %s :pages %ld :tuples %.0f :targetlist ", + node->rows, + node->width, node->indexed ? "true" : "false", node->pages, - node->tuples, - node->size, - node->width); + node->tuples); _outNode(str, node->targetlist); appendStringInfo(str, " :pathlist "); @@ -871,6 +872,15 @@ _outRelOptInfo(StringInfo str, RelOptInfo *node) _outNode(str, node->innerjoin); } +static void +_outIndexOptInfo(StringInfo str, IndexOptInfo *node) +{ + appendStringInfo(str, " INDEXOPTINFO :indexoid %u :pages %ld :tuples %g ", + node->indexoid, + node->pages, + node->tuples); +} + /* * TargetEntry is a subclass of Node. */ @@ -910,7 +920,7 @@ _outRowMark(StringInfo str, RowMark *node) static void _outPath(StringInfo str, Path *node) { - appendStringInfo(str, " PATH :pathtype %d :cost %f :pathkeys ", + appendStringInfo(str, " PATH :pathtype %d :cost %.2f :pathkeys ", node->pathtype, node->path_cost); _outNode(str, node->pathkeys); @@ -923,7 +933,7 @@ static void _outIndexPath(StringInfo str, IndexPath *node) { appendStringInfo(str, - " INDEXPATH :pathtype %d :cost %f :pathkeys ", + " INDEXPATH :pathtype %d :cost %.2f :pathkeys ", node->path.pathtype, node->path.path_cost); _outNode(str, node->path.pathkeys); @@ -945,7 +955,7 @@ static void _outTidPath(StringInfo str, TidPath *node) { appendStringInfo(str, - " TIDPATH :pathtype %d :cost %f :pathkeys ", + " TIDPATH :pathtype %d :cost %.2f :pathkeys ", node->path.pathtype, node->path.path_cost); _outNode(str, node->path.pathkeys); @@ -964,14 +974,11 @@ static void _outNestPath(StringInfo str, NestPath *node) { appendStringInfo(str, - " NESTPATH :pathtype %d :cost %f :pathkeys ", + " NESTPATH :pathtype %d :cost %.2f :pathkeys ", node->path.pathtype, node->path.path_cost); _outNode(str, node->path.pathkeys); - appendStringInfo(str, " :pathinfo "); - _outNode(str, node->pathinfo); - /* * Not sure if these are nodes; they're declared as "struct path *". * For now, i'll just print the addresses. @@ -990,14 +997,11 @@ static void _outMergePath(StringInfo str, MergePath *node) { appendStringInfo(str, - " MERGEPATH :pathtype %d :cost %f :pathkeys ", + " MERGEPATH :pathtype %d :cost %.2f :pathkeys ", node->jpath.path.pathtype, node->jpath.path.path_cost); _outNode(str, node->jpath.path.pathkeys); - appendStringInfo(str, " :pathinfo "); - _outNode(str, node->jpath.pathinfo); - /* * Not sure if these are nodes; they're declared as "struct path *". * For now, i'll just print the addresses. @@ -1025,14 +1029,11 @@ static void _outHashPath(StringInfo str, HashPath *node) { appendStringInfo(str, - " HASHPATH :pathtype %d :cost %f :pathkeys ", + " HASHPATH :pathtype %d :cost %.2f :pathkeys ", node->jpath.path.pathtype, node->jpath.path.path_cost); _outNode(str, node->jpath.path.pathkeys); - appendStringInfo(str, " :pathinfo "); - _outNode(str, node->jpath.pathinfo); - /* * Not sure if these are nodes; they're declared as "struct path *". * For now, i'll just print the addresses. @@ -1067,9 +1068,7 @@ _outRestrictInfo(StringInfo str, RestrictInfo *node) appendStringInfo(str, " RESTRICTINFO :clause "); _outNode(str, node->clause); - appendStringInfo(str, - " :selectivity %f :subclauseindices ", - node->selectivity); + appendStringInfo(str, " :subclauseindices "); _outNode(str, node->subclauseindices); appendStringInfo(str, " :mergejoinoperator %u ", node->mergejoinoperator); @@ -1466,6 +1465,9 @@ _outNode(StringInfo str, void *obj) case T_RelOptInfo: _outRelOptInfo(str, obj); break; + case T_IndexOptInfo: + _outIndexOptInfo(str, obj); + break; case T_TargetEntry: _outTargetEntry(str, obj); break; diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c index 3241816cd3..bfd30ff8a7 100644 --- a/src/backend/nodes/print.c +++ b/src/backend/nodes/print.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/nodes/print.c,v 1.33 1999/11/23 20:06:53 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/print.c,v 1.34 2000/01/09 00:26:24 tgl Exp $ * * HISTORY * AUTHOR DATE MAJOR EVENT @@ -364,8 +364,8 @@ print_plan_recursive(Plan *p, Query *parsetree, int indentLevel, char *label) return; for (i = 0; i < indentLevel; i++) printf(" "); - printf("%s%s :c=%.4f :s=%d :w=%d ", label, plannode_type(p), - p->cost, p->plan_size, p->plan_width); + printf("%s%s :c=%.4f :r=%.0f :w=%d ", label, plannode_type(p), + p->cost, p->plan_rows, p->plan_width); if (IsA(p, Scan) ||IsA(p, SeqScan)) { RangeTblEntry *rte; diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c index 83683ff3b1..8f7bb5271a 100644 --- a/src/backend/nodes/readfuncs.c +++ b/src/backend/nodes/readfuncs.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/nodes/readfuncs.c,v 1.76 1999/12/13 01:26:54 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/readfuncs.c,v 1.77 2000/01/09 00:26:24 tgl Exp $ * * NOTES * Most of the read functions for plan nodes are tested. (In fact, they @@ -233,9 +233,9 @@ _getPlan(Plan *node) token = lsptok(NULL, &length); /* next is the actual cost */ node->cost = (Cost) atof(token); - token = lsptok(NULL, &length); /* skip the :size */ - token = lsptok(NULL, &length); /* get the plan_size */ - node->plan_size = atoi(token); + token = lsptok(NULL, &length); /* skip the :rows */ + token = lsptok(NULL, &length); /* get the plan_rows */ + node->plan_rows = atof(token); token = lsptok(NULL, &length); /* skip the :width */ token = lsptok(NULL, &length); /* get the plan_width */ @@ -1293,6 +1293,14 @@ _readRelOptInfo() token = lsptok(NULL, &length); /* get :relids */ local_node->relids = toIntList(nodeRead(true)); /* now read it */ + token = lsptok(NULL, &length); /* get :rows */ + token = lsptok(NULL, &length); /* now read it */ + local_node->rows = atof(token); + + token = lsptok(NULL, &length); /* get :width */ + token = lsptok(NULL, &length); /* now read it */ + local_node->width = atoi(token); + token = lsptok(NULL, &length); /* get :indexed */ token = lsptok(NULL, &length); /* now read it */ @@ -1303,19 +1311,11 @@ _readRelOptInfo() token = lsptok(NULL, &length); /* get :pages */ token = lsptok(NULL, &length); /* now read it */ - local_node->pages = (unsigned int) atoi(token); + local_node->pages = atol(token); token = lsptok(NULL, &length); /* get :tuples */ token = lsptok(NULL, &length); /* now read it */ - local_node->tuples = (unsigned int) atoi(token); - - token = lsptok(NULL, &length); /* get :size */ - token = lsptok(NULL, &length); /* now read it */ - local_node->size = (unsigned int) atoi(token); - - token = lsptok(NULL, &length); /* get :width */ - token = lsptok(NULL, &length); /* now read it */ - local_node->width = (unsigned int) atoi(token); + local_node->tuples = atof(token); token = lsptok(NULL, &length); /* get :targetlist */ local_node->targetlist = nodeRead(true); /* now read it */ @@ -1349,6 +1349,34 @@ _readRelOptInfo() } /* ---------------- + * _readIndexOptInfo + * ---------------- + */ +static IndexOptInfo * +_readIndexOptInfo() +{ + IndexOptInfo *local_node; + char *token; + int length; + + local_node = makeNode(IndexOptInfo); + + token = lsptok(NULL, &length); /* get :indexoid */ + token = lsptok(NULL, &length); /* now read it */ + local_node->indexoid = (Oid) atoi(token); + + token = lsptok(NULL, &length); /* get :pages */ + token = lsptok(NULL, &length); /* now read it */ + local_node->pages = atol(token); + + token = lsptok(NULL, &length); /* get :tuples */ + token = lsptok(NULL, &length); /* now read it */ + local_node->tuples = atof(token); + + return local_node; +} + +/* ---------------- * _readTargetEntry * ---------------- */ @@ -1572,9 +1600,6 @@ _readNestPath() token = lsptok(NULL, &length); /* get :pathkeys */ local_node->path.pathkeys = nodeRead(true); /* now read it */ - token = lsptok(NULL, &length); /* get :pathinfo */ - local_node->pathinfo = nodeRead(true); /* now read it */ - /* * Not sure if these are nodes; they're declared as "struct path *". * For now, i'll just print the addresses. @@ -1626,9 +1651,6 @@ _readMergePath() token = lsptok(NULL, &length); /* get :pathkeys */ local_node->jpath.path.pathkeys = nodeRead(true); /* now read it */ - token = lsptok(NULL, &length); /* get :pathinfo */ - local_node->jpath.pathinfo = nodeRead(true); /* now read it */ - /* * Not sure if these are nodes; they're declared as "struct path *". * For now, i'll just print the addresses. @@ -1689,9 +1711,6 @@ _readHashPath() token = lsptok(NULL, &length); /* get :pathkeys */ local_node->jpath.path.pathkeys = nodeRead(true); /* now read it */ - token = lsptok(NULL, &length); /* get :pathinfo */ - local_node->jpath.pathinfo = nodeRead(true); /* now read it */ - /* * Not sure if these are nodes; they're declared as "struct path *". * For now, i'll just print the addresses. @@ -1762,10 +1781,6 @@ _readRestrictInfo() token = lsptok(NULL, &length); /* get :clause */ local_node->clause = nodeRead(true); /* now read it */ - token = lsptok(NULL, &length); /* get :selectivity */ - token = lsptok(NULL, &length); /* now read it */ - local_node->selectivity = atof(token); - token = lsptok(NULL, &length); /* get :subclauseindices */ local_node->subclauseindices = nodeRead(true); /* now read it */ @@ -1909,6 +1924,8 @@ parsePlanString(void) return_value = _readEState(); else if (!strncmp(token, "RELOPTINFO", length)) return_value = _readRelOptInfo(); + else if (!strncmp(token, "INDEXOPTINFO", length)) + return_value = _readIndexOptInfo(); else if (!strncmp(token, "TARGETENTRY", length)) return_value = _readTargetEntry(); else if (!strncmp(token, "RTE", length)) diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c index 1c3fb05bc6..35238bbed4 100644 --- a/src/backend/optimizer/geqo/geqo_eval.c +++ b/src/backend/optimizer/geqo/geqo_eval.c @@ -5,7 +5,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: geqo_eval.c,v 1.44 1999/09/21 20:58:08 momjian Exp $ + * $Id: geqo_eval.c,v 1.45 2000/01/09 00:26:27 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -95,7 +95,7 @@ geqo_eval(Query *root, Gene *tour, int num_gene) joinrel = gimme_tree(root, tour, 0, num_gene, NULL); /* compute fitness */ - fitness = (Cost) joinrel->cheapestpath->path_cost; + fitness = joinrel->cheapestpath->path_cost; /* restore join_rel_list */ root->join_rel_list = savelist; @@ -177,16 +177,14 @@ gimme_tree(Query *root, Gene *tour, int rel_count, int num_gene, RelOptInfo *old elog(DEBUG, "gimme_tree: still %d relations left", length(new_rels)); } - rels_set_cheapest(new_rels); + rels_set_cheapest(root, new_rels); /* get essential new relation */ new_rel = (RelOptInfo *) lfirst(new_rels); rel_count++; /* processing of other new_rel attributes */ - if (new_rel->size <= 0) - new_rel->size = compute_rel_size(new_rel); - new_rel->width = compute_rel_width(new_rel); + set_rel_rows_width(root, new_rel); root->join_rel_list = lcons(new_rel, NIL); diff --git a/src/backend/optimizer/geqo/geqo_misc.c b/src/backend/optimizer/geqo/geqo_misc.c index db55aadcfc..19cdda31a5 100644 --- a/src/backend/optimizer/geqo/geqo_misc.c +++ b/src/backend/optimizer/geqo/geqo_misc.c @@ -5,7 +5,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: geqo_misc.c,v 1.24 1999/08/16 02:17:48 tgl Exp $ + * $Id: geqo_misc.c,v 1.25 2000/01/09 00:26:27 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -177,10 +177,9 @@ geqo_print_path(Query *root, Path *path, int indent) } if (join) { - int size = path->parent->size; - jp = (JoinPath *) path; - printf("%s size=%d cost=%f\n", ptype, size, path->path_cost); + printf("%s rows=%.0f cost=%f\n", + ptype, path->parent->rows, path->path_cost); switch (nodeTag(path)) { case T_MergePath: @@ -188,7 +187,7 @@ geqo_print_path(Query *root, Path *path, int indent) for (i = 0; i < indent + 1; i++) printf("\t"); printf(" clauses=("); - geqo_print_joinclauses(root, ((JoinPath *) path)->pathinfo); + geqo_print_joinclauses(root, path->parent->restrictinfo); printf(")\n"); if (nodeTag(path) == T_MergePath) @@ -213,11 +212,10 @@ geqo_print_path(Query *root, Path *path, int indent) } else { - int size = path->parent->size; int relid = lfirsti(path->parent->relids); - printf("%s(%d) size=%d cost=%f\n", - ptype, relid, size, path->path_cost); + printf("%s(%d) rows=%.0f cost=%f\n", + ptype, relid, path->parent->rows, path->path_cost); if (IsA(path, IndexPath)) { @@ -236,7 +234,7 @@ geqo_print_rel(Query *root, RelOptInfo *rel) printf("("); foreach(l, rel->relids) printf("%d ", lfirsti(l)); - printf("): size=%d width=%d\n", rel->size, rel->width); + printf("): rows=%.0f width=%d\n", rel->rows, rel->width); printf("\tpath list:\n"); foreach(l, rel->pathlist) diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 3cc8466f77..1e357d4b8f 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.54 1999/11/23 20:06:54 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.55 2000/01/09 00:26:29 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -66,23 +66,16 @@ make_one_rel(Query *root, List *rels) if (levels_needed <= 1) { - /* - * Unsorted single relation, no more processing is required. + * Single relation, no more processing is required. */ return lfirst(rels); } else { - /* - * This means that joins or sorts are required. Set selectivities - * of any clauses not yet set. (I think that this is redundant; - * set_base_rel_pathlist should have set them all already. But - * a scan to check that they are all set doesn't cost much...) + * Generate join tree. */ - set_rest_relselec(root, rels); - return make_one_rel_by_joins(root, rels, levels_needed); } } @@ -115,7 +108,7 @@ set_base_rel_pathlist(Query *root, List *rels) tidscan_pathlist = create_tidscan_paths(root, rel); if (tidscan_pathlist) sequential_scan_list = nconc(sequential_scan_list, - tidscan_pathlist); + tidscan_pathlist); rel_index_scan_list = create_index_paths(root, rel, indices, @@ -126,7 +119,6 @@ set_base_rel_pathlist(Query *root, List *rels) * to have marked OR restriction clauses with relevant indices; * this is why it doesn't need to be given the full list of indices. */ - or_index_scan_list = create_or_index_paths(root, rel, rel->restrictinfo); @@ -139,19 +131,10 @@ set_base_rel_pathlist(Query *root, List *rels) nconc(rel_index_scan_list, or_index_scan_list)); + /* Now find the cheapest of the paths */ set_cheapest(rel, rel->pathlist); - - /* Set the selectivity estimates for any restriction clauses that - * didn't get set as a byproduct of index-path selectivity estimation - * (see create_index_path()). - */ - set_rest_selec(root, rel->restrictinfo); - - /* Calculate the estimated size (post-restrictions) and tuple width - * for this base rel. This uses the restriction clause selectivities. - */ - rel->size = compute_rel_size(rel); - rel->width = compute_rel_width(rel); + /* Mark rel with estimated output rows and width */ + set_rel_rows_width(root, rel); } } @@ -217,16 +200,12 @@ make_one_rel_by_joins(Query *root, List *rels, int levels_needed) xfunc_trypullup((RelOptInfo *) lfirst(x)); #endif - rels_set_cheapest(joined_rels); + rels_set_cheapest(root, joined_rels); foreach(x, joined_rels) { rel = (RelOptInfo *) lfirst(x); - if (rel->size <= 0) - rel->size = compute_rel_size(rel); - rel->width = compute_rel_width(rel); - #ifdef OPTIMIZER_DEBUG printf("levels left: %d\n", levels_needed); debug_print_rel(root, rel); @@ -297,10 +276,9 @@ print_path(Query *root, Path *path, int indent) } if (join) { - int size = path->parent->size; - jp = (JoinPath *) path; - printf("%s size=%d cost=%f\n", ptype, size, path->path_cost); + printf("%s rows=%.0f cost=%f\n", + ptype, path->parent->rows, path->path_cost); switch (nodeTag(path)) { case T_MergePath: @@ -308,7 +286,7 @@ print_path(Query *root, Path *path, int indent) for (i = 0; i < indent + 1; i++) printf("\t"); printf(" clauses=("); - print_joinclauses(root, ((JoinPath *) path)->pathinfo); + print_joinclauses(root, jp->path.parent->restrictinfo); printf(")\n"); if (nodeTag(path) == T_MergePath) @@ -333,11 +311,10 @@ print_path(Query *root, Path *path, int indent) } else { - int size = path->parent->size; int relid = lfirsti(path->parent->relids); - printf("%s(%d) size=%d cost=%f\n", - ptype, relid, size, path->path_cost); + printf("%s(%d) rows=%.0f cost=%f\n", + ptype, relid, path->parent->rows, path->path_cost); if (IsA(path, IndexPath)) { @@ -355,7 +332,7 @@ debug_print_rel(Query *root, RelOptInfo *rel) printf("("); foreach(l, rel->relids) printf("%d ", lfirsti(l)); - printf("): size=%d width=%d\n", rel->size, rel->width); + printf("): rows=%.0f width=%d\n", rel->rows, rel->width); printf("\tpath list:\n"); foreach(l, rel->pathlist) diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c index 5264d50834..a25dd68da3 100644 --- a/src/backend/optimizer/path/clausesel.c +++ b/src/backend/optimizer/path/clausesel.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/clausesel.c,v 1.26 1999/09/09 02:35:47 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/clausesel.c,v 1.27 2000/01/09 00:26:31 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -24,102 +24,58 @@ /**************************************************************************** - * ROUTINES TO SET CLAUSE SELECTIVITIES + * ROUTINES TO COMPUTE SELECTIVITIES ****************************************************************************/ /* - * set_clause_selectivities - - * Sets the selectivity field for each clause in 'restrictinfo-list' - * to 'new-selectivity'. If the selectivity has already been set, - * change it only if the new one is better. - */ -void -set_clause_selectivities(List *restrictinfo_list, Cost new_selectivity) -{ - List *rlist; - - foreach(rlist, restrictinfo_list) - { - RestrictInfo *clausenode = (RestrictInfo *) lfirst(rlist); - Cost cost_clause = clausenode->selectivity; - - if (cost_clause <= 0 || new_selectivity < cost_clause) - clausenode->selectivity = new_selectivity; - } -} - -/* - * product_selec - - * Multiplies the selectivities of each clause in 'restrictinfo-list'. + * restrictlist_selec - + * Compute the selectivity of an implicitly-ANDed list of RestrictInfo + * clauses. * - * Returns a flonum corresponding to the selectivity of 'restrictinfo-list'. + * This is the same as clauselist_selec except for the form of the input. */ -Cost -product_selec(List *restrictinfo_list) +Selectivity +restrictlist_selec(Query *root, List *restrictinfo_list) { - Cost result = (Cost) 1.0; - List *rlist; + List *clauselist = get_actual_clauses(restrictinfo_list); + Selectivity result; - foreach(rlist, restrictinfo_list) - { - result *= ((RestrictInfo *) lfirst(rlist))->selectivity; - } + result = clauselist_selec(root, clauselist); + freeList(clauselist); return result; } /* - * set_rest_relselec - - * Scans through clauses on each relation and assigns a selectivity to - * those clauses that haven't been assigned a selectivity by an index. - * - * MODIFIES: selectivities of the various rel's restrictinfo slots. + * clauselist_selec - + * Compute the selectivity of an implicitly-ANDed list of boolean + * expression clauses. */ -void -set_rest_relselec(Query *root, List *rel_list) +Selectivity +clauselist_selec(Query *root, List *clauses) { - List *x; - - foreach(x, rel_list) + Selectivity s1 = 1.0; + List *clause; + + /* Use the product of the selectivities of the subclauses. + * XXX this is probably too optimistic, since the subclauses + * are very likely not independent... + */ + foreach(clause, clauses) { - RelOptInfo *rel = (RelOptInfo *) lfirst(x); - set_rest_selec(root, rel->restrictinfo); - } -} - -/* - * set_rest_selec - - * Sets the selectivity fields for those clauses within a single - * relation's 'restrictinfo-list' that haven't already been set. - */ -void -set_rest_selec(Query *root, List *restrictinfo_list) -{ - List *rlist; - - foreach(rlist, restrictinfo_list) - { - RestrictInfo *clause = (RestrictInfo *) lfirst(rlist); - - if (clause->selectivity <= 0) - { - clause->selectivity = - compute_clause_selec(root, (Node *) clause->clause); - } + Selectivity s2 = compute_clause_selec(root, (Node *) lfirst(clause)); + s1 = s1 * s2; } + return s1; } -/**************************************************************************** - * ROUTINES TO COMPUTE SELECTIVITIES - ****************************************************************************/ - /* * compute_clause_selec - - * Computes the selectivity of a clause. + * Compute the selectivity of a general boolean expression clause. */ -Cost +Selectivity compute_clause_selec(Query *root, Node *clause) { - Cost s1 = 1.0; /* default for any unhandled clause type */ + Selectivity s1 = 1.0; /* default for any unhandled clause type */ if (clause == NULL) return s1; @@ -131,17 +87,12 @@ compute_clause_selec(Query *root, Node *clause) * is what we have. The magic #define constants are a hack. I * didn't want to have to do system cache look ups to find out all * of that info. - * - * XXX why are we using varno and varoattno? Seems like it should - * be varno/varattno or varnoold/varoattno, not mix & match... */ - Oid relid = getrelid(((Var *) clause)->varno, - root->rtable); - s1 = restriction_selectivity(F_EQSEL, BooleanEqualOperator, - relid, - ((Var *) clause)->varoattno, + getrelid(((Var *) clause)->varno, + root->rtable), + ((Var *) clause)->varattno, Int8GetDatum(true), SEL_CONSTANT | SEL_RIGHT); } @@ -163,21 +114,12 @@ compute_clause_selec(Query *root, Node *clause) } else if (and_clause(clause)) { - /* Use the product of the selectivities of the subclauses. - * XXX this is probably too optimistic, since the subclauses - * are very likely not independent... - */ - List *arg; - s1 = 1.0; - foreach(arg, ((Expr *) clause)->args) - { - Cost s2 = compute_clause_selec(root, (Node *) lfirst(arg)); - s1 = s1 * s2; - } + s1 = clauselist_selec(root, ((Expr *) clause)->args); } else if (or_clause(clause)) { - /* Selectivities for an 'or' clause are computed as s1+s2 - s1*s2 + /* + * Selectivities for an 'or' clause are computed as s1+s2 - s1*s2 * to account for the probable overlap of selected tuple sets. * XXX is this too conservative? */ @@ -185,31 +127,15 @@ compute_clause_selec(Query *root, Node *clause) s1 = 0.0; foreach(arg, ((Expr *) clause)->args) { - Cost s2 = compute_clause_selec(root, (Node *) lfirst(arg)); + Selectivity s2 = compute_clause_selec(root, (Node *) lfirst(arg)); s1 = s1 + s2 - s1 * s2; } } - else if (is_funcclause(clause)) - { - /* - * This is not an operator, so we guess at the selectivity. THIS - * IS A HACK TO GET V4 OUT THE DOOR. FUNCS SHOULD BE ABLE TO HAVE - * SELECTIVITIES THEMSELVES. -- JMH 7/9/92 - */ - s1 = (Cost) 0.3333333; - } - else if (is_subplan(clause)) - { - /* - * Just for the moment! FIX ME! - vadim 02/04/98 - */ - s1 = 1.0; - } else if (is_opclause(clause)) { if (NumRelids(clause) == 1) { - /* The clause is not a join clause, since there is only one + /* The opclause is not a join clause, since there is only one * relid in the clause. The clause selectivity will be based on * the operator selectivity and operand values. */ @@ -221,33 +147,20 @@ compute_clause_selec(Query *root, Node *clause) * selectivity of 0.5 */ if (!oprrest) - s1 = (Cost) 0.5; + s1 = (Selectivity) 0.5; else { int relidx; AttrNumber attno; Datum constval; int flag; + Oid reloid; get_relattval(clause, 0, &relidx, &attno, &constval, &flag); - if (relidx && attno) - s1 = (Cost) restriction_selectivity(oprrest, - opno, - getrelid(relidx, - root->rtable), - attno, - constval, - flag); - else - { - /* - * attno can be 0 if the clause had a function in it, - * i.e. WHERE myFunc(f) = 10 - * - * XXX should be FIXED to use function selectivity - */ - s1 = (Cost) (0.5); - } + reloid = relidx ? getrelid(relidx, root->rtable) : InvalidOid; + s1 = restriction_selectivity(oprrest, opno, + reloid, attno, + constval, flag); } } else @@ -265,30 +178,41 @@ compute_clause_selec(Query *root, Node *clause) * selectivity of 0.5 */ if (!oprjoin) - s1 = (Cost) (0.5); + s1 = (Selectivity) 0.5; else { int relid1, relid2; AttrNumber attno1, attno2; + Oid reloid1, + reloid2; get_rels_atts(clause, &relid1, &attno1, &relid2, &attno2); - if (relid1 && relid2 && attno1 && attno2) - - s1 = (Cost) join_selectivity(oprjoin, - opno, - getrelid(relid1, - root->rtable), - attno1, - getrelid(relid2, - root->rtable), - attno2); - else /* XXX more code for function selectivity? */ - s1 = (Cost) (0.5); + reloid1 = relid1 ? getrelid(relid1, root->rtable) : InvalidOid; + reloid2 = relid2 ? getrelid(relid2, root->rtable) : InvalidOid; + s1 = join_selectivity(oprjoin, opno, + reloid1, attno1, + reloid2, attno2); } } } + else if (is_funcclause(clause)) + { + /* + * This is not an operator, so we guess at the selectivity. THIS + * IS A HACK TO GET V4 OUT THE DOOR. FUNCS SHOULD BE ABLE TO HAVE + * SELECTIVITIES THEMSELVES. -- JMH 7/9/92 + */ + s1 = (Selectivity) 0.3333333; + } + else if (is_subplan(clause)) + { + /* + * Just for the moment! FIX ME! - vadim 02/04/98 + */ + s1 = 1.0; + } return s1; } diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 99ee42cf8c..8261e17c02 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -18,15 +18,14 @@ * Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.46 1999/11/23 20:06:54 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.47 2000/01/09 00:26:31 tgl Exp $ * *------------------------------------------------------------------------- */ -#include - #include "postgres.h" +#include #ifdef HAVE_LIMITS_H #include #ifndef MAXINT @@ -45,13 +44,17 @@ #include "utils/lsyscache.h" -static int compute_targetlist_width(List *targetlist); +static void set_rel_width(Query *root, RelOptInfo *rel); static int compute_attribute_width(TargetEntry *tlistentry); -static double relation_byte_size(int tuples, int width); +static double relation_byte_size(double tuples, int width); +static double page_size(double tuples, int width); static double base_log(double x, double b); -int _disable_cost_ = 30000000; +Cost _cpu_page_weight_ = _CPU_PAGE_WEIGHT_; +Cost _cpu_index_page_weight_ = _CPU_INDEX_PAGE_WEIGHT_; + +Cost _disable_cost_ = 100000000.0; bool _enable_seqscan_ = true; bool _enable_indexscan_ = true; @@ -61,9 +64,6 @@ bool _enable_mergejoin_ = true; bool _enable_hashjoin_ = true; bool _enable_tidscan_ = true; -Cost _cpu_page_weight_ = _CPU_PAGE_WEIGHT_; -Cost _cpu_index_page_weight_ = _CPU_INDEX_PAGE_WEIGHT_; - /* * cost_seqscan * Determines and returns the cost of scanning a relation sequentially. @@ -74,27 +74,21 @@ Cost _cpu_index_page_weight_ = _CPU_INDEX_PAGE_WEIGHT_; * be). * * disk = p - * cpu = *CPU-PAGE-WEIGHT* * t - * - * 'relid' is the relid of the relation to be scanned - * 'relpages' is the number of pages in the relation to be scanned - * (as determined from the system catalogs) - * 'reltuples' is the number of tuples in the relation to be scanned - * - * Returns a flonum. - * + * cpu = CPU-PAGE-WEIGHT * t */ Cost -cost_seqscan(int relid, int relpages, int reltuples) +cost_seqscan(RelOptInfo *baserel) { Cost temp = 0; + /* Should only be applied to base relations */ + Assert(length(baserel->relids) == 1); + if (!_enable_seqscan_) temp += _disable_cost_; - if (relid < 0) + if (lfirsti(baserel->relids) < 0) { - /* * cost of sequentially scanning a materialized temporary relation */ @@ -102,9 +96,10 @@ cost_seqscan(int relid, int relpages, int reltuples) } else { - temp += relpages; - temp += _cpu_page_weight_ * reltuples; + temp += baserel->pages; + temp += _cpu_page_weight_ * baserel->tuples; } + Assert(temp >= 0); return temp; } @@ -115,31 +110,38 @@ cost_seqscan(int relid, int relpages, int reltuples) * Determines and returns the cost of scanning a relation using an index. * * disk = expected-index-pages + expected-data-pages - * cpu = *CPU-PAGE-WEIGHT* * - * (expected-index-tuples + expected-data-tuples) - * - * 'indexid' is the index OID - * 'expected-indexpages' is the number of index pages examined in the scan - * 'selec' is the selectivity of the index - * 'relpages' is the number of pages in the main relation - * 'reltuples' is the number of tuples in the main relation - * 'indexpages' is the number of pages in the index relation - * 'indextuples' is the number of tuples in the index relation - * - * Returns a flonum. - * + * cpu = CPU-INDEX-PAGE-WEIGHT * expected-index-tuples + + * CPU-PAGE-WEIGHT * expected-data-tuples + * + * 'baserel' is the base relation the index is for + * 'index' is the index to be used + * 'expected_indexpages' is the estimated number of index pages that will + * be touched in the scan (this is computed by index-type-specific code) + * 'selec' is the selectivity of the index, ie, the fraction of base-relation + * tuples that we will have to fetch and examine + * 'is_injoin' is T if we are considering using the index scan as the inside + * of a nestloop join. + * + * NOTE: 'selec' should be calculated on the basis of indexqual conditions + * only. Any additional quals evaluated as qpquals may reduce the number + * of returned tuples, but they won't reduce the number of tuples we have + * to fetch from the table, so they don't reduce the scan cost. */ Cost -cost_index(Oid indexid, - int expected_indexpages, - Cost selec, - int relpages, - int reltuples, - int indexpages, - int indextuples, +cost_index(RelOptInfo *baserel, + IndexOptInfo *index, + long expected_indexpages, + Selectivity selec, bool is_injoin) { Cost temp = 0; + double reltuples = selec * baserel->tuples; + double indextuples = selec * index->tuples; + double relpages; + + /* Should only be applied to base relations */ + Assert(IsA(baserel, RelOptInfo) && IsA(index, IndexOptInfo)); + Assert(length(baserel->relids) == 1); if (!_enable_indexscan_ && !is_injoin) temp += _disable_cost_; @@ -151,25 +153,49 @@ cost_index(Oid indexid, */ if (expected_indexpages <= 0) expected_indexpages = 1; - if (indextuples <= 0) - indextuples = 1; + if (indextuples <= 0.0) + indextuples = 1.0; /* expected index relation pages */ temp += expected_indexpages; - /* - * expected base relation pages XXX this isn't really right, since we - * will access the table nonsequentially and might have to fetch the - * same page more than once. This calculation assumes the buffer - * cache will prevent that from happening... + /*-------------------- + * expected base relation pages + * + * Worst case is that each tuple the index tells us to fetch comes + * from a different base-rel page, in which case the I/O cost would be + * 'reltuples' pages. In practice we can expect the number of page + * fetches to be reduced by the buffer cache, because more than one + * tuple can be retrieved per page fetched. Currently, we estimate + * the number of pages to be retrieved as + * MIN(reltuples, relpages) + * This amounts to assuming that the buffer cache is perfectly efficient + * and never ends up reading the same page twice within one scan, which + * of course is too optimistic. On the other hand, we are assuming that + * the target tuples are perfectly uniformly distributed across the + * relation's pages, which is too pessimistic --- any nonuniformity of + * distribution will reduce the number of pages we have to fetch. + * So, we guess-and-hope that these sources of error will more or less + * balance out. + * + * XXX if the relation has recently been "clustered" using this index, + * then in fact the target tuples will be highly nonuniformly distributed, + * and we will be seriously overestimating the scan cost! Currently we + * have no way to know whether the relation has been clustered, nor how + * much it's been modified since the last clustering, so we ignore this + * effect. Would be nice to do better someday. + *-------------------- */ - temp += ceil(((double) selec) * ((double) relpages)); + relpages = reltuples; + if (baserel->pages > 0 && baserel->pages < relpages) + relpages = baserel->pages; + temp += relpages; /* per index tuples */ - temp += _cpu_index_page_weight_ * selec * indextuples; + temp += _cpu_index_page_weight_ * indextuples; /* per heap tuples */ - temp += _cpu_page_weight_ * selec * reltuples; + temp += _cpu_page_weight_ * reltuples; Assert(temp >= 0); return temp; @@ -180,13 +206,10 @@ cost_index(Oid indexid, * Determines and returns the cost of scanning a relation using tid-s. * * disk = number of tids - * cpu = *CPU-PAGE-WEIGHT* * number_of_tids - * - * Returns a flonum. - * + * cpu = CPU-PAGE-WEIGHT * number_of_tids */ Cost -cost_tidscan(List *tideval) +cost_tidscan(RelOptInfo *baserel, List *tideval) { Cost temp = 0; @@ -200,28 +223,39 @@ cost_tidscan(List *tideval) /* * cost_sort - * Determines and returns the cost of sorting a relation by considering - * the cost of doing an external sort: XXX this is probably too low - * disk = (p lg p) - * cpu = *CPU-PAGE-WEIGHT* * (t lg t) + * Determines and returns the cost of sorting a relation. + * + * If the total volume of data to sort is less than SortMem, we will do + * an in-memory sort, which requires no I/O and about t*log2(t) tuple + * comparisons for t tuples. We use _cpu_index_page_weight as the cost + * of a tuple comparison (is this reasonable, or do we need another + * basic parameter?). + * + * If the total volume exceeds SortMem, we switch to a tape-style merge + * algorithm. There will still be about t*log2(t) tuple comparisons in + * total, but we will also need to write and read each tuple once per + * merge pass. We expect about ceil(log6(r)) merge passes where r is the + * number of initial runs formed (log6 because tuplesort.c uses six-tape + * merging). Since the average initial run should be about twice SortMem, + * we have + * disk = 2 * p * ceil(log6(p / (2*SortMem))) + * cpu = CPU-INDEX-PAGE-WEIGHT * t * log2(t) * * 'pathkeys' is a list of sort keys * 'tuples' is the number of tuples in the relation * 'width' is the average tuple width in bytes * - * NOTE: some callers currently pass NULL for pathkeys because they + * NOTE: some callers currently pass NIL for pathkeys because they * can't conveniently supply the sort keys. Since this routine doesn't * currently do anything with pathkeys anyway, that doesn't matter... * but if it ever does, it should react gracefully to lack of key data. - * - * Returns a flonum. */ Cost -cost_sort(List *pathkeys, int tuples, int width) +cost_sort(List *pathkeys, double tuples, int width) { Cost temp = 0; - int npages = page_size(tuples, width); - double log_npages; + double nbytes = relation_byte_size(tuples, width); + long sortmembytes = SortMem * 1024L; if (!_enable_sort_) temp += _disable_cost_; @@ -231,25 +265,23 @@ cost_sort(List *pathkeys, int tuples, int width) * even if passed-in tuple count is zero. Besides, mustn't do * log(0)... */ - if (tuples <= 0) - tuples = 1; - if (npages <= 0) - npages = 1; + if (tuples < 2.0) + tuples = 2.0; - log_npages = ceil(base_log((double) npages, 2.0)); - if (log_npages <= 0.0) - log_npages = 1.0; + temp += _cpu_index_page_weight_ * tuples * base_log(tuples, 2.0); - temp += npages * log_npages; + if (nbytes > sortmembytes) + { + double npages = ceil(nbytes / BLCKSZ); + double nruns = nbytes / (sortmembytes * 2); + double log_runs = ceil(base_log(nruns, 6.0)); - /* - * could be base_log(tuples, NBuffers), but we are only doing 2-way - * merges - */ - temp += _cpu_page_weight_ * tuples * base_log((double) tuples, 2.0); + if (log_runs < 1.0) + log_runs = 1.0; + temp += 2 * npages * log_runs; + } Assert(temp > 0); - return temp; } @@ -258,18 +290,15 @@ cost_sort(List *pathkeys, int tuples, int width) * cost_result * Determines and returns the cost of writing a relation of 'tuples' * tuples of 'width' bytes out to a result relation. - * - * Returns a flonum. - * */ #ifdef NOT_USED Cost -cost_result(int tuples, int width) +cost_result(double tuples, int width) { Cost temp = 0; - temp = temp + page_size(tuples, width); - temp = temp + _cpu_page_weight_ * tuples; + temp += page_size(tuples, width); + temp += _cpu_page_weight_ * tuples; Assert(temp >= 0); return temp; } @@ -281,111 +310,106 @@ cost_result(int tuples, int width) * Determines and returns the cost of joining two relations using the * nested loop algorithm. * - * 'outercost' is the (disk+cpu) cost of scanning the outer relation - * 'innercost' is the (disk+cpu) cost of scanning the inner relation - * 'outertuples' is the number of tuples in the outer relation - * - * Returns a flonum. - * + * 'outer_path' is the path for the outer relation + * 'inner_path' is the path for the inner relation + * 'is_indexjoin' is true if we are using an indexscan for the inner relation */ Cost -cost_nestloop(Cost outercost, - Cost innercost, - int outertuples, - int innertuples, - int outerpages, +cost_nestloop(Path *outer_path, + Path *inner_path, bool is_indexjoin) { Cost temp = 0; if (!_enable_nestloop_) temp += _disable_cost_; - temp += outercost; - temp += outertuples * innercost; - Assert(temp >= 0); + temp += outer_path->path_cost; + temp += outer_path->parent->rows * inner_path->path_cost; + + Assert(temp >= 0); return temp; } /* * cost_mergejoin - * 'outercost' and 'innercost' are the (disk+cpu) costs of scanning the - * outer and inner relations - * 'outersortkeys' and 'innersortkeys' are lists of the keys to be used - * to sort the outer and inner relations (or NIL if no explicit - * sort is needed because the source path is already ordered) - * 'outertuples' and 'innertuples' are the number of tuples in the outer - * and inner relations - * 'outerwidth' and 'innerwidth' are the (typical) widths (in bytes) - * of the tuples of the outer and inner relations - * - * Returns a flonum. + * Determines and returns the cost of joining two relations using the + * merge join algorithm. * + * 'outer_path' is the path for the outer relation + * 'inner_path' is the path for the inner relation + * 'outersortkeys' and 'innersortkeys' are lists of the keys to be used + * to sort the outer and inner relations, or NIL if no explicit + * sort is needed because the source path is already ordered */ Cost -cost_mergejoin(Cost outercost, - Cost innercost, +cost_mergejoin(Path *outer_path, + Path *inner_path, List *outersortkeys, - List *innersortkeys, - int outersize, - int innersize, - int outerwidth, - int innerwidth) + List *innersortkeys) { Cost temp = 0; if (!_enable_mergejoin_) temp += _disable_cost_; - temp += outercost; - temp += innercost; + /* cost of source data */ + temp += outer_path->path_cost + inner_path->path_cost; + if (outersortkeys) /* do we need to sort? */ - temp += cost_sort(outersortkeys, outersize, outerwidth); + temp += cost_sort(outersortkeys, + outer_path->parent->rows, + outer_path->parent->width); + if (innersortkeys) /* do we need to sort? */ - temp += cost_sort(innersortkeys, innersize, innerwidth); - temp += _cpu_page_weight_ * (outersize + innersize); + temp += cost_sort(innersortkeys, + inner_path->parent->rows, + inner_path->parent->width); - Assert(temp >= 0); + /* + * Estimate the number of tuples to be processed in the mergejoin itself + * as one per tuple in the two source relations. This could be a drastic + * underestimate if there are many equal-keyed tuples in either relation, + * but we have no good way of estimating that... + */ + temp += _cpu_page_weight_ * (outer_path->parent->rows + + inner_path->parent->rows); + Assert(temp >= 0); return temp; } /* * cost_hashjoin + * Determines and returns the cost of joining two relations using the + * hash join algorithm. * - * 'outercost' and 'innercost' are the (disk+cpu) costs of scanning the - * outer and inner relations - * 'outersize' and 'innersize' are the number of tuples in the outer - * and inner relations - * 'outerwidth' and 'innerwidth' are the (typical) widths (in bytes) - * of the tuples of the outer and inner relations - * 'innerdisbursion' is an estimate of the disbursion statistic + * 'outer_path' is the path for the outer relation + * 'inner_path' is the path for the inner relation + * 'innerdisbursion' is an estimate of the disbursion statistic * for the inner hash key. - * - * Returns a flonum. */ Cost -cost_hashjoin(Cost outercost, - Cost innercost, - int outersize, - int innersize, - int outerwidth, - int innerwidth, - Cost innerdisbursion) +cost_hashjoin(Path *outer_path, + Path *inner_path, + Selectivity innerdisbursion) { Cost temp = 0; - double outerbytes = relation_byte_size(outersize, outerwidth); - double innerbytes = relation_byte_size(innersize, innerwidth); + double outerbytes = relation_byte_size(outer_path->parent->rows, + outer_path->parent->width); + double innerbytes = relation_byte_size(inner_path->parent->rows, + inner_path->parent->width); long hashtablebytes = SortMem * 1024L; if (!_enable_hashjoin_) temp += _disable_cost_; /* cost of source data */ - temp += outercost + innercost; + temp += outer_path->path_cost + inner_path->path_cost; /* cost of computing hash function: must do it once per tuple */ - temp += _cpu_page_weight_ * (outersize + innersize); + temp += _cpu_page_weight_ * (outer_path->parent->rows + + inner_path->parent->rows); /* the number of tuple comparisons needed is the number of outer * tuples times the typical hash bucket size, which we estimate @@ -393,8 +417,8 @@ cost_hashjoin(Cost outercost, * count. The cost per comparison is set at _cpu_index_page_weight_; * is that reasonable, or do we need another basic parameter? */ - temp += _cpu_index_page_weight_ * outersize * - (innersize * innerdisbursion); + temp += _cpu_index_page_weight_ * outer_path->parent->rows * + (inner_path->parent->rows * innerdisbursion); /* * if inner relation is too big then we will need to "batch" the join, @@ -402,8 +426,10 @@ cost_hashjoin(Cost outercost, * extra time. Charge one cost unit per page of I/O. */ if (innerbytes > hashtablebytes) - temp += 2 * (page_size(outersize, outerwidth) + - page_size(innersize, innerwidth)); + temp += 2 * (page_size(outer_path->parent->rows, + outer_path->parent->width) + + page_size(inner_path->parent->rows, + inner_path->parent->width)); /* * Bias against putting larger relation on inside. We don't want @@ -415,76 +441,74 @@ cost_hashjoin(Cost outercost, temp *= 1.1; /* is this an OK fudge factor? */ Assert(temp >= 0); - return temp; } /* - * compute_rel_size - * Computes the size of each relation in 'rel_list' (after applying - * restrictions), by multiplying the selectivity of each restriction - * by the original size of the relation. + * set_rel_rows_width + * Set the 'rows' and 'width' estimates for the given base relation. * - * Sets the 'size' field for each relation entry with this computed size. - * - * Returns the size. + * 'rows' is the estimated number of output tuples (after applying + * restriction clauses). + * 'width' is the estimated average output tuple width in bytes. */ -int -compute_rel_size(RelOptInfo *rel) +void +set_rel_rows_width(Query *root, RelOptInfo *rel) { - Cost temp; - int temp1; + /* Should only be applied to base relations */ + Assert(length(rel->relids) == 1); - temp = rel->tuples * product_selec(rel->restrictinfo); - Assert(temp >= 0); - if (temp >= (MAXINT - 1)) - temp1 = MAXINT; - else - temp1 = ceil((double) temp); - Assert(temp1 >= 0); - Assert(temp1 <= MAXINT); - return temp1; + rel->rows = rel->tuples * restrictlist_selec(root, rel->restrictinfo); + Assert(rel->rows >= 0); + + set_rel_width(root, rel); } /* - * compute_rel_width - * Computes the width in bytes of a tuple from 'rel'. - * - * Returns the width of the tuple as a fixnum. + * set_joinrel_rows_width + * Set the 'rows' and 'width' estimates for the given join relation. */ -int -compute_rel_width(RelOptInfo *rel) +void +set_joinrel_rows_width(Query *root, RelOptInfo *rel, + JoinPath *joinpath) { - return compute_targetlist_width(rel->targetlist); + double temp; + + /* cartesian product */ + temp = joinpath->outerjoinpath->parent->rows * + joinpath->innerjoinpath->parent->rows; + + /* apply restrictivity */ + temp *= restrictlist_selec(root, joinpath->path.parent->restrictinfo); + + Assert(temp >= 0); + rel->rows = temp; + + set_rel_width(root, rel); } /* - * compute_targetlist_width - * Computes the width in bytes of a tuple made from 'targetlist'. - * - * Returns the width of the tuple as a fixnum. + * set_rel_width + * Set the estimated output width of the relation. */ -static int -compute_targetlist_width(List *targetlist) +static void +set_rel_width(Query *root, RelOptInfo *rel) { - List *temp_tl; int tuple_width = 0; + List *tle; - foreach(temp_tl, targetlist) - { - tuple_width += compute_attribute_width(lfirst(temp_tl)); - } - return tuple_width; + foreach(tle, rel->targetlist) + tuple_width += compute_attribute_width((TargetEntry *) lfirst(tle)); + Assert(tuple_width >= 0); + rel->width = tuple_width; } /* * compute_attribute_width * Given a target list entry, find the size in bytes of the attribute. * - * If a field is variable-length, it is assumed to be at least the size - * of a TID field. - * - * Returns the width of the attribute as a fixnum. + * If a field is variable-length, we make a default assumption. Would be + * better if VACUUM recorded some stats about the average field width... */ static int compute_attribute_width(TargetEntry *tlistentry) @@ -498,46 +522,14 @@ compute_attribute_width(TargetEntry *tlistentry) } /* - * compute_joinrel_size - * Computes the size of the join relation 'joinrel'. - * - * Returns a fixnum. - */ -int -compute_joinrel_size(JoinPath *joinpath) -{ - Cost temp = 1.0; - int temp1 = 0; - - /* cartesian product */ - temp *= ((Path *) joinpath->outerjoinpath)->parent->size; - temp *= ((Path *) joinpath->innerjoinpath)->parent->size; - - temp = temp * product_selec(joinpath->pathinfo); - if (temp >= (MAXINT - 1) / 2) - { - /* if we exceed (MAXINT-1)/2, we switch to log scale */ - /* +1 prevents log(0) */ - temp1 = ceil(log(temp + 1 - (MAXINT - 1) / 2) + (MAXINT - 1) / 2); - } - else - temp1 = ceil((double) temp); - Assert(temp1 >= 0); - - return temp1; -} - -/* * relation_byte_size * Estimate the storage space in bytes for a given number of tuples * of a given width (size in bytes). - * To avoid overflow with big relations, result is a double. */ - static double -relation_byte_size(int tuples, int width) +relation_byte_size(double tuples, int width) { - return ((double) tuples) * ((double) (width + sizeof(HeapTupleData))); + return tuples * ((double) (width + sizeof(HeapTupleData))); } /* @@ -545,14 +537,10 @@ relation_byte_size(int tuples, int width) * Returns an estimate of the number of pages covered by a given * number of tuples of a given width (size in bytes). */ -int -page_size(int tuples, int width) +static double +page_size(double tuples, int width) { - int temp; - - temp = (int) ceil(relation_byte_size(tuples, width) / BLCKSZ); - Assert(temp >= 0); - return temp; + return ceil(relation_byte_size(tuples, width) / BLCKSZ); } static double diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index b8aea22d10..3c93ee67ac 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.75 1999/12/31 05:38:25 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.76 2000/01/09 00:26:31 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -41,51 +41,55 @@ #include "utils/lsyscache.h" #include "utils/syscache.h" + +#define is_indexable_operator(clause,opclass,relam,indexkey_on_left) \ + (indexable_operator(clause,opclass,relam,indexkey_on_left) != InvalidOid) + typedef enum { Prefix_None, Prefix_Partial, Prefix_Exact } Prefix_Status; -static void match_index_orclauses(RelOptInfo *rel, RelOptInfo *index, +static void match_index_orclauses(RelOptInfo *rel, IndexOptInfo *index, int indexkey, Oid opclass, List *restrictinfo_list); -static List *match_index_orclause(RelOptInfo *rel, RelOptInfo *index, +static List *match_index_orclause(RelOptInfo *rel, IndexOptInfo *index, int indexkey, Oid opclass, List *or_clauses, List *other_matching_indices); -static bool match_or_subclause_to_indexkey(RelOptInfo *rel, RelOptInfo *index, +static bool match_or_subclause_to_indexkey(RelOptInfo *rel, + IndexOptInfo *index, int indexkey, Oid opclass, Expr *clause); -static List *group_clauses_by_indexkey(RelOptInfo *rel, RelOptInfo *index, +static List *group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index, int *indexkeys, Oid *classes, List *restrictinfo_list); -static List *group_clauses_by_ikey_for_joins(RelOptInfo *rel, RelOptInfo *index, +static List *group_clauses_by_ikey_for_joins(RelOptInfo *rel, + IndexOptInfo *index, int *indexkeys, Oid *classes, List *join_cinfo_list, List *restr_cinfo_list); -static bool match_clause_to_indexkey(RelOptInfo *rel, RelOptInfo *index, +static bool match_clause_to_indexkey(RelOptInfo *rel, IndexOptInfo *index, int indexkey, Oid opclass, Expr *clause, bool join); -static bool indexable_operator(Expr *clause, Oid opclass, Oid relam, - bool indexkey_on_left); static bool pred_test(List *predicate_list, List *restrictinfo_list, List *joininfo_list); static bool one_pred_test(Expr *predicate, List *restrictinfo_list); static bool one_pred_clause_expr_test(Expr *predicate, Node *clause); static bool one_pred_clause_test(Expr *predicate, Node *clause); static bool clause_pred_clause_test(Expr *predicate, Node *clause); -static void indexable_joinclauses(RelOptInfo *rel, RelOptInfo *index, +static void indexable_joinclauses(RelOptInfo *rel, IndexOptInfo *index, List *joininfo_list, List *restrictinfo_list, List **clausegroups, List **outerrelids); -static List *index_innerjoin(Query *root, RelOptInfo *rel, RelOptInfo *index, +static List *index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index, List *clausegroup_list, List *outerrelids_list); -static bool useful_for_mergejoin(RelOptInfo *rel, RelOptInfo *index, +static bool useful_for_mergejoin(RelOptInfo *rel, IndexOptInfo *index, List *joininfo_list); static bool useful_for_ordering(Query *root, RelOptInfo *rel, - RelOptInfo *index); + IndexOptInfo *index); static bool match_index_to_operand(int indexkey, Var *operand, - RelOptInfo *rel, RelOptInfo *index); + RelOptInfo *rel, IndexOptInfo *index); static bool function_index_operand(Expr *funcOpnd, RelOptInfo *rel, - RelOptInfo *index); + IndexOptInfo *index); static bool match_special_index_operator(Expr *clause, Oid opclass, Oid relam, bool indexkey_on_left); static Prefix_Status like_fixed_prefix(char *patt, char **prefix); @@ -145,7 +149,7 @@ create_index_paths(Query *root, foreach(ilist, indices) { - RelOptInfo *index = (RelOptInfo *) lfirst(ilist); + IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist); List *restrictclauses; List *joinclausegroups; List *joinouterrelids; @@ -268,7 +272,7 @@ create_index_paths(Query *root, */ static void match_index_orclauses(RelOptInfo *rel, - RelOptInfo *index, + IndexOptInfo *index, int indexkey, Oid opclass, List *restrictinfo_list) @@ -317,7 +321,7 @@ match_index_orclauses(RelOptInfo *rel, */ static List * match_index_orclause(RelOptInfo *rel, - RelOptInfo *index, + IndexOptInfo *index, int indexkey, Oid opclass, List *or_clauses, @@ -368,7 +372,7 @@ match_index_orclause(RelOptInfo *rel, */ static bool match_or_subclause_to_indexkey(RelOptInfo *rel, - RelOptInfo *index, + IndexOptInfo *index, int indexkey, Oid opclass, Expr *clause) @@ -435,7 +439,7 @@ match_or_subclause_to_indexkey(RelOptInfo *rel, */ static List * group_clauses_by_indexkey(RelOptInfo *rel, - RelOptInfo *index, + IndexOptInfo *index, int *indexkeys, Oid *classes, List *restrictinfo_list) @@ -497,7 +501,7 @@ group_clauses_by_indexkey(RelOptInfo *rel, */ static List * group_clauses_by_ikey_for_joins(RelOptInfo *rel, - RelOptInfo *index, + IndexOptInfo *index, int *indexkeys, Oid *classes, List *join_cinfo_list, @@ -614,7 +618,7 @@ group_clauses_by_ikey_for_joins(RelOptInfo *rel, */ static bool match_clause_to_indexkey(RelOptInfo *rel, - RelOptInfo *index, + IndexOptInfo *index, int indexkey, Oid opclass, Expr *clause, @@ -642,7 +646,7 @@ match_clause_to_indexkey(RelOptInfo *rel, if ((IsA(rightop, Const) || IsA(rightop, Param)) && match_index_to_operand(indexkey, leftop, rel, index)) { - if (indexable_operator(clause, opclass, index->relam, true)) + if (is_indexable_operator(clause, opclass, index->relam, true)) return true; /* * If we didn't find a member of the index's opclass, @@ -656,7 +660,7 @@ match_clause_to_indexkey(RelOptInfo *rel, if ((IsA(leftop, Const) || IsA(leftop, Param)) && match_index_to_operand(indexkey, rightop, rel, index)) { - if (indexable_operator(clause, opclass, index->relam, false)) + if (is_indexable_operator(clause, opclass, index->relam, false)) return true; /* * If we didn't find a member of the index's opclass, @@ -683,7 +687,7 @@ match_clause_to_indexkey(RelOptInfo *rel, isIndexable = ! intMember(lfirsti(rel->relids), othervarnos); freeList(othervarnos); if (isIndexable && - indexable_operator(clause, opclass, index->relam, true)) + is_indexable_operator(clause, opclass, index->relam, true)) return true; } else if (match_index_to_operand(indexkey, rightop, rel, index)) @@ -694,7 +698,7 @@ match_clause_to_indexkey(RelOptInfo *rel, isIndexable = ! intMember(lfirsti(rel->relids), othervarnos); freeList(othervarnos); if (isIndexable && - indexable_operator(clause, opclass, index->relam, false)) + is_indexable_operator(clause, opclass, index->relam, false)) return true; } } @@ -707,9 +711,9 @@ match_clause_to_indexkey(RelOptInfo *rel, * Does a binary opclause contain an operator matching the index's * access method? * - * If the indexkey is on the right, what we actually want to know - * is whether the operator has a commutator operator that matches - * the index's access method. + * If the indexkey is on the right, what we actually want to know + * is whether the operator has a commutator operator that matches + * the index's access method. * * We try both the straightforward match and matches that rely on * recognizing binary-compatible datatypes. For example, if we have @@ -717,12 +721,13 @@ match_clause_to_indexkey(RelOptInfo *rel, * which we need to replace with oideq in order to recognize it as * matching an oid_ops index on the oid field. * - * NOTE: if a binary-compatible match is made, we destructively modify - * the given clause to use the binary-compatible substitute operator! - * This should be safe even if we don't end up using the index, but it's - * a tad ugly... + * Returns the OID of the matching operator, or InvalidOid if no match. + * Note that the returned OID will be different from the one in the given + * expression if we used a binary-compatible substitution. Also note that + * if indexkey_on_left is FALSE (meaning we need to commute), the returned + * OID is *not* commuted; it can be plugged directly into the given clause. */ -static bool +Oid indexable_operator(Expr *clause, Oid opclass, Oid relam, bool indexkey_on_left) { @@ -737,11 +742,11 @@ indexable_operator(Expr *clause, Oid opclass, Oid relam, else commuted_op = get_commutator(expr_op); if (commuted_op == InvalidOid) - return false; + return InvalidOid; /* Done if the (commuted) operator is a member of the index's AM */ if (op_class(commuted_op, opclass, relam)) - return true; + return expr_op; /* * Maybe the index uses a binary-compatible operator set. @@ -758,7 +763,7 @@ indexable_operator(Expr *clause, Oid opclass, Oid relam, Operator newop; if (opname == NULL) - return false; /* probably shouldn't happen */ + return InvalidOid; /* probably shouldn't happen */ /* Use the datatype of the index key */ if (indexkey_on_left) @@ -781,22 +786,15 @@ indexable_operator(Expr *clause, Oid opclass, Oid relam, else commuted_op = get_commutator(new_expr_op); if (commuted_op == InvalidOid) - return false; + return InvalidOid; if (op_class(commuted_op, opclass, relam)) - { - /* - * Success! Change the opclause to use the - * binary-compatible operator. - */ - ((Oper *) clause->oper)->opno = new_expr_op; - return true; - } + return new_expr_op; } } } - return false; + return InvalidOid; } /* @@ -816,7 +814,7 @@ indexable_operator(Expr *clause, Oid opclass, Oid relam, */ static bool useful_for_mergejoin(RelOptInfo *rel, - RelOptInfo *index, + IndexOptInfo *index, List *joininfo_list) { int *indexkeys = index->indexkeys; @@ -867,7 +865,7 @@ useful_for_mergejoin(RelOptInfo *rel, static bool useful_for_ordering(Query *root, RelOptInfo *rel, - RelOptInfo *index) + IndexOptInfo *index) { List *index_pathkeys; @@ -1335,7 +1333,7 @@ clause_pred_clause_test(Expr *predicate, Node *clause) * '*outerrelids' receives a list of relid lists */ static void -indexable_joinclauses(RelOptInfo *rel, RelOptInfo *index, +indexable_joinclauses(RelOptInfo *rel, IndexOptInfo *index, List *joininfo_list, List *restrictinfo_list, List **clausegroups, List **outerrelids) { @@ -1384,7 +1382,7 @@ indexable_joinclauses(RelOptInfo *rel, RelOptInfo *index, * Returns a list of index pathnodes. */ static List * -index_innerjoin(Query *root, RelOptInfo *rel, RelOptInfo *index, +index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index, List *clausegroup_list, List *outerrelids_list) { List *path_list = NIL; @@ -1395,16 +1393,16 @@ index_innerjoin(Query *root, RelOptInfo *rel, RelOptInfo *index, List *clausegroup = lfirst(i); IndexPath *pathnode = makeNode(IndexPath); List *indexquals; - float npages; - float selec; + long npages; + Selectivity selec; indexquals = get_actual_clauses(clausegroup); /* expand special operators to indexquals the executor can handle */ indexquals = expand_indexqual_conditions(indexquals); index_selectivity(root, - lfirsti(rel->relids), - lfirsti(index->relids), + rel, + index, indexquals, &npages, &selec); @@ -1419,20 +1417,14 @@ index_innerjoin(Query *root, RelOptInfo *rel, RelOptInfo *index, * therefore, both indexid and indexqual should be single-element * lists. */ - Assert(length(index->relids) == 1); - pathnode->indexid = index->relids; + pathnode->indexid = lconsi(index->indexoid, NIL); pathnode->indexqual = lcons(indexquals, NIL); /* joinrelids saves the rels needed on the outer side of the join */ pathnode->joinrelids = lfirst(outerrelids_list); - pathnode->path.path_cost = cost_index((Oid) lfirsti(index->relids), - (int) npages, - selec, - rel->pages, - rel->tuples, - index->pages, - index->tuples, + pathnode->path.path_cost = cost_index(rel, index, + npages, selec, true); path_list = lappend(path_list, pathnode); @@ -1455,7 +1447,7 @@ static bool match_index_to_operand(int indexkey, Var *operand, RelOptInfo *rel, - RelOptInfo *index) + IndexOptInfo *index) { if (index->indproc == InvalidOid) { @@ -1477,7 +1469,7 @@ match_index_to_operand(int indexkey, } static bool -function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index) +function_index_operand(Expr *funcOpnd, RelOptInfo *rel, IndexOptInfo *index) { int relvarno = lfirsti(rel->relids); Func *function; diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c index c1ac6a2c4d..5c7df62fa2 100644 --- a/src/backend/optimizer/path/joinpath.c +++ b/src/backend/optimizer/path/joinpath.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.46 1999/08/21 03:49:00 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.47 2000/01/09 00:26:33 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -40,7 +40,7 @@ static List *match_unsorted_inner(RelOptInfo *joinrel, RelOptInfo *outerrel, List *mergeclause_list); static List *hash_inner_and_outer(Query *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel); -static Cost estimate_disbursion(Query *root, Var *var); +static Selectivity estimate_disbursion(Query *root, Var *var); static List *select_mergejoin_clauses(List *restrictinfo_list); /* @@ -258,12 +258,8 @@ sort_inner_and_outer(RelOptInfo *joinrel, curclause_list); /* And now we can make the path. */ path_node = create_mergejoin_path(joinrel, - outerrel->size, - innerrel->size, - outerrel->width, - innerrel->width, - (Path *) outerrel->cheapestpath, - (Path *) innerrel->cheapestpath, + outerrel->cheapestpath, + innerrel->cheapestpath, merge_pathkeys, get_actual_clauses(curclause_list), outerkeys, @@ -359,7 +355,6 @@ match_unsorted_outer(RelOptInfo *joinrel, /* Always consider a nestloop join with this outer and best inner. */ path_list = lappend(path_list, create_nestloop_path(joinrel, - outerrel, outerpath, nestinnerpath, merge_pathkeys)); @@ -393,7 +388,7 @@ match_unsorted_outer(RelOptInfo *joinrel, int clausecount; cheapest_cost = cheapest_inner->path_cost + - cost_sort(innersortkeys, innerrel->size, innerrel->width); + cost_sort(innersortkeys, innerrel->rows, innerrel->width); for (clausecount = mergeclausecount; clausecount > 0; @@ -427,10 +422,6 @@ match_unsorted_outer(RelOptInfo *joinrel, get_actual_clauses(mergeclauses)); path_list = lappend(path_list, create_mergejoin_path(joinrel, - outerrel->size, - innerrel->size, - outerrel->width, - innerrel->width, outerpath, mergeinnerpath, merge_pathkeys, @@ -496,7 +487,7 @@ match_unsorted_inner(RelOptInfo *joinrel, if (mergeouterpath != NULL && mergeouterpath->path_cost <= (outerrel->cheapestpath->path_cost + - cost_sort(outersortkeys, outerrel->size, outerrel->width))) + cost_sort(outersortkeys, outerrel->rows, outerrel->width))) { /* Use mergeouterpath */ outersortkeys = NIL; /* no explicit sort step */ @@ -516,10 +507,6 @@ match_unsorted_inner(RelOptInfo *joinrel, mergeclauses = get_actual_clauses(mergeclauses); path_list = lappend(path_list, create_mergejoin_path(joinrel, - outerrel->size, - innerrel->size, - outerrel->width, - innerrel->width, mergeouterpath, innerpath, merge_pathkeys, @@ -563,7 +550,7 @@ hash_inner_and_outer(Query *root, Var *leftop = get_leftop(clause); Var *rightop = get_rightop(clause); Var *innerop; - Cost innerdisbursion; + Selectivity innerdisbursion; HashPath *hash_path; /* find the inner var and estimate its disbursion */ @@ -574,12 +561,8 @@ hash_inner_and_outer(Query *root, innerdisbursion = estimate_disbursion(root, innerop); hash_path = create_hashjoin_path(joinrel, - outerrel->size, - innerrel->size, - outerrel->width, - innerrel->width, - (Path *) outerrel->cheapestpath, - (Path *) innerrel->cheapestpath, + outerrel->cheapestpath, + innerrel->cheapestpath, lcons(clause, NIL), innerdisbursion); hpath_list = lappend(hpath_list, hash_path); @@ -598,7 +581,7 @@ hash_inner_and_outer(Query *root, * we know that the inner rel is well-dispersed (or the alternatives * seem much worse). */ -static Cost +static Selectivity estimate_disbursion(Query *root, Var *var) { Oid relid; @@ -608,7 +591,7 @@ estimate_disbursion(Query *root, Var *var) relid = getrelid(var->varno, root->rtable); - return (Cost) get_attdisbursion(relid, var->varattno, 0.1); + return (Selectivity) get_attdisbursion(relid, var->varattno, 0.1); } /* diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c index 9085e0a393..9441999afb 100644 --- a/src/backend/optimizer/path/joinrels.c +++ b/src/backend/optimizer/path/joinrels.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.39 1999/08/16 02:17:51 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.40 2000/01/09 00:26:33 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -35,8 +35,6 @@ static List *new_join_tlist(List *tlist, int first_resdomno); static void build_joinrel_restrict_and_join(RelOptInfo *joinrel, List *joininfo_list, Relids join_relids); -static void set_joinrel_size(RelOptInfo *joinrel, RelOptInfo *outer_rel, - RelOptInfo *inner_rel); /* * make_rels_by_joins @@ -207,19 +205,15 @@ make_join_rel(RelOptInfo *outer_rel, RelOptInfo *inner_rel) * The list will be flattened out in update_rels_pathlist_for_joins(). */ joinrel->relids = lcons(outer_rel->relids, lcons(inner_rel->relids, NIL)); - joinrel->indexed = false; - joinrel->pages = 0; - joinrel->tuples = 0; - joinrel->size = 0; + joinrel->rows = 0; joinrel->width = 0; -/* joinrel->targetlist = NIL;*/ + joinrel->targetlist = NIL; joinrel->pathlist = NIL; joinrel->cheapestpath = (Path *) NULL; joinrel->pruneable = true; - joinrel->classlist = NULL; - joinrel->indexkeys = NULL; - joinrel->ordering = NULL; - joinrel->relam = InvalidOid; + joinrel->indexed = false; + joinrel->pages = 0; + joinrel->tuples = 0; joinrel->restrictinfo = NIL; joinrel->joininfo = NIL; joinrel->innerjoin = NIL; @@ -236,21 +230,22 @@ make_join_rel(RelOptInfo *outer_rel, RelOptInfo *inner_rel) /* * Construct restrict and join clause lists for the new joinrel. + * + * nconc(listCopy(x), y) is an idiom for making a new list without + * changing either input list. */ build_joinrel_restrict_and_join(joinrel, - nconc(copyObject(outer_rel->joininfo), - copyObject(inner_rel->joininfo)), + nconc(listCopy(outer_rel->joininfo), + inner_rel->joininfo), nconc(listCopy(outer_rel->relids), - listCopy(inner_rel->relids))); - - set_joinrel_size(joinrel, outer_rel, inner_rel); + inner_rel->relids)); return joinrel; } /* * new_join_tlist - * Builds a join relations's target list by keeping those elements that + * Builds a join relation's target list by keeping those elements that * will be in the final target list and any other elements that are still * needed for future joins. For a target list entry to still be needed * for future joins, its 'joinlist' field must not be empty after removal @@ -311,18 +306,16 @@ new_join_tlist(List *tlist, * 'joininfo_list' is a list of joininfo nodes from the relations being joined * 'join_relids' is a list of all base relids in the new join relation * - * NB: the elements of joininfo_list have all been COPIED and so can safely - * be destructively modified and/or inserted in the new joinrel's lists. - * The amount of copying going on here is probably vastly excessive, - * since we copied the underlying clauses as well... + * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass + * up to the join relation. I believe this is no longer necessary, because + * RestrictInfo nodes are no longer context-dependent. Instead, just add + * the original nodes to the lists belonging to the join relation. */ static void build_joinrel_restrict_and_join(RelOptInfo *joinrel, List *joininfo_list, Relids join_relids) { - List *output_restrictinfo_list = NIL; - List *output_joininfo_list = NIL; List *xjoininfo; foreach(xjoininfo, joininfo_list) @@ -341,38 +334,25 @@ build_joinrel_restrict_and_join(RelOptInfo *joinrel, * Be careful to eliminate duplicates, since we will see the * same clauses arriving from both input relations... */ - output_restrictinfo_list = - LispUnion(output_restrictinfo_list, + joinrel->restrictinfo = + LispUnion(joinrel->restrictinfo, joininfo->jinfo_restrictinfo); } else { - JoinInfo *old_joininfo; - /* - * There might already be a JoinInfo with the same set of - * unjoined relids in output_joininfo_list; don't make a - * redundant entry. + * These clauses are still join clauses at this level, + * so find or make the appropriate JoinInfo item for the joinrel, + * and add the clauses to it (eliminating duplicates). */ - old_joininfo = joininfo_member(new_unjoined_relids, - output_joininfo_list); - if (old_joininfo) - { - old_joininfo->jinfo_restrictinfo = - LispUnion(old_joininfo->jinfo_restrictinfo, - joininfo->jinfo_restrictinfo); - } - else - { - joininfo->unjoined_relids = new_unjoined_relids; - output_joininfo_list = lcons(joininfo, - output_joininfo_list); - } + JoinInfo *new_joininfo; + + new_joininfo = find_joininfo_node(joinrel, new_unjoined_relids); + new_joininfo->jinfo_restrictinfo = + LispUnion(new_joininfo->jinfo_restrictinfo, + joininfo->jinfo_restrictinfo); } } - - joinrel->restrictinfo = output_restrictinfo_list; - joinrel->joininfo = output_joininfo_list; } /* @@ -424,36 +404,6 @@ get_cheapest_complete_rel(List *join_rel_list) return final_rel; } -static void -set_joinrel_size(RelOptInfo *joinrel, RelOptInfo *outer_rel, - RelOptInfo *inner_rel) -{ - double dtuples; - int ntuples; - - /* avoid overflow ... probably, tuple estimates in RelOptInfo - * just ought to be double ... - */ - dtuples = (double) outer_rel->tuples * (double) inner_rel->tuples; - - if (joinrel->restrictinfo != NULL) - dtuples *= product_selec(joinrel->restrictinfo); - - if (dtuples >= MAXINT) /* avoid overflow */ - ntuples = MAXINT; - else - ntuples = (int) dtuples; - - /* - * I bet sizes less than 1 will screw up optimization so make the best - * case 1 instead of 0 - jolly - */ - if (ntuples < 1) - ntuples = 1; - - joinrel->tuples = ntuples; -} - /* * Subset-inclusion tests on integer lists. * diff --git a/src/backend/optimizer/path/orindxpath.c b/src/backend/optimizer/path/orindxpath.c index 51699a73d2..f5813a27a8 100644 --- a/src/backend/optimizer/path/orindxpath.c +++ b/src/backend/optimizer/path/orindxpath.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.32 1999/08/16 02:17:52 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.33 2000/01/09 00:26:33 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -30,11 +30,11 @@ static void best_or_subclause_indices(Query *root, RelOptInfo *rel, List *subclauses, List *indices, List **indexquals, List **indexids, - Cost *cost, Cost *selec); + Cost *cost); static void best_or_subclause_index(Query *root, RelOptInfo *rel, List *indexqual, List *indices, - int *retIndexid, - Cost *retCost, Cost *retSelec); + Oid *retIndexid, + Cost *retCost); /* @@ -89,7 +89,6 @@ create_or_index_paths(Query *root, List *indexquals; List *indexids; Cost cost; - Cost selec; best_or_subclause_indices(root, rel, @@ -97,8 +96,7 @@ create_or_index_paths(Query *root, clausenode->subclauseindices, &indexquals, &indexids, - &cost, - &selec); + &cost); pathnode->path.pathtype = T_IndexScan; pathnode->path.parent = rel; @@ -114,7 +112,6 @@ create_or_index_paths(Query *root, pathnode->indexqual = indexquals; pathnode->joinrelids = NIL; /* no join clauses here */ pathnode->path.path_cost = cost; - clausenode->selectivity = (Cost) selec; path_list = lappend(path_list, pathnode); } @@ -141,13 +138,12 @@ create_or_index_paths(Query *root, * * 'rel' is the node of the relation on which the indexes are defined * 'subclauses' are the subclauses of the 'or' clause - * 'indices' is a list of sublists of the index nodes that matched each - * subclause of the 'or' clause + * 'indices' is a list of sublists of the IndexOptInfo nodes that matched + * each subclause of the 'or' clause * '*indexquals' gets the constructed indexquals for the path (a list * of sublists of clauses, one sublist per scan of the base rel) - * '*indexids' gets a list of the index IDs for each scan of the rel + * '*indexids' gets a list of the index OIDs for each scan of the rel * '*cost' gets the total cost of the path - * '*selec' gets the total selectivity of the path. */ static void best_or_subclause_indices(Query *root, @@ -156,23 +152,20 @@ best_or_subclause_indices(Query *root, List *indices, List **indexquals, /* return value */ List **indexids, /* return value */ - Cost *cost, /* return value */ - Cost *selec) /* return value */ + Cost *cost) /* return value */ { List *slist; *indexquals = NIL; *indexids = NIL; *cost = (Cost) 0.0; - *selec = (Cost) 0.0; foreach(slist, subclauses) { Expr *subclause = lfirst(slist); List *indexqual; - int best_indexid; + Oid best_indexid; Cost best_cost; - Cost best_selec; /* Convert this 'or' subclause to an indexqual list */ indexqual = make_ands_implicit(subclause); @@ -180,18 +173,13 @@ best_or_subclause_indices(Query *root, indexqual = expand_indexqual_conditions(indexqual); best_or_subclause_index(root, rel, indexqual, lfirst(indices), - &best_indexid, &best_cost, &best_selec); + &best_indexid, &best_cost); + + Assert(best_indexid != InvalidOid); *indexquals = lappend(*indexquals, indexqual); *indexids = lappendi(*indexids, best_indexid); *cost += best_cost; - /* We approximate the selectivity as the sum of the clause - * selectivities (but not more than 1). - * XXX This is too pessimistic, isn't it? - */ - *selec += best_selec; - if (*selec > (Cost) 1.0) - *selec = (Cost) 1.0; indices = lnext(indices); } @@ -205,59 +193,50 @@ best_or_subclause_indices(Query *root, * * 'rel' is the node of the relation on which the index is defined * 'indexqual' is the indexqual list derived from the subclause - * 'indices' is a list of index nodes that match the subclause - * '*retIndexid' gets the ID of the best index + * 'indices' is a list of IndexOptInfo nodes that match the subclause + * '*retIndexid' gets the OID of the best index * '*retCost' gets the cost of a scan with that index - * '*retSelec' gets the selectivity of that scan */ static void best_or_subclause_index(Query *root, RelOptInfo *rel, List *indexqual, List *indices, - int *retIndexid, /* return value */ - Cost *retCost, /* return value */ - Cost *retSelec) /* return value */ + Oid *retIndexid, /* return value */ + Cost *retCost) /* return value */ { bool first_run = true; List *ilist; /* if we don't match anything, return zeros */ - *retIndexid = 0; - *retCost = (Cost) 0.0; - *retSelec = (Cost) 0.0; + *retIndexid = InvalidOid; + *retCost = 0.0; foreach(ilist, indices) { - RelOptInfo *index = (RelOptInfo *) lfirst(ilist); - Oid indexid = (Oid) lfirsti(index->relids); + IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist); + long npages; + Selectivity selec; Cost subcost; - float npages; - float selec; + + Assert(IsA(index, IndexOptInfo)); index_selectivity(root, - lfirsti(rel->relids), - indexid, + rel, + index, indexqual, &npages, &selec); - subcost = cost_index(indexid, - (int) npages, - (Cost) selec, - rel->pages, - rel->tuples, - index->pages, - index->tuples, + subcost = cost_index(rel, index, + npages, selec, false); if (first_run || subcost < *retCost) { - *retIndexid = indexid; + *retIndexid = index->indexoid; *retCost = subcost; - *retSelec = selec; first_run = false; } } - } diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index b9a982e828..1e508f76f0 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.16 1999/08/22 20:14:42 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.17 2000/01/09 00:26:33 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -261,7 +261,7 @@ get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, * ordering of that key is not interesting. */ List * -build_index_pathkeys(Query *root, RelOptInfo *rel, RelOptInfo *index) +build_index_pathkeys(Query *root, RelOptInfo *rel, IndexOptInfo *index) { List *retval = NIL; int *indexkeys = index->indexkeys; diff --git a/src/backend/optimizer/path/prune.c b/src/backend/optimizer/path/prune.c index 33fb67bc57..96e8051a74 100644 --- a/src/backend/optimizer/path/prune.c +++ b/src/backend/optimizer/path/prune.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/prune.c,v 1.43 1999/08/16 02:17:52 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/prune.c,v 1.44 2000/01/09 00:26:33 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -90,7 +90,7 @@ merge_rel_with_same_relids(RelOptInfo *rel, List *unmerged_rels) * relations), set pointers to the cheapest path and compute rel size. */ void -rels_set_cheapest(List *rel_list) +rels_set_cheapest(Query *root, List *rel_list) { List *x; @@ -101,7 +101,7 @@ rels_set_cheapest(List *rel_list) cheapest = (JoinPath *) set_cheapest(rel, rel->pathlist); if (IsA_JoinPath(cheapest)) - rel->size = compute_joinrel_size(cheapest); + set_joinrel_rows_width(root, rel, cheapest); else elog(ERROR, "rels_set_cheapest: non JoinPath found"); } diff --git a/src/backend/optimizer/path/tidpath.c b/src/backend/optimizer/path/tidpath.c index 9e618f7a87..39504bb1e0 100644 --- a/src/backend/optimizer/path/tidpath.c +++ b/src/backend/optimizer/path/tidpath.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/tidpath.c,v 1.1 1999/11/23 20:06:55 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/tidpath.c,v 1.2 2000/01/09 00:26:33 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -241,30 +241,27 @@ List *TidqualFromRestrictinfo(List *relids, List * restrictinfo) List * create_tidscan_joinpaths(RelOptInfo *rel) { - List *rlst = NIL, *lst; - TidPath *pathnode = (TidPath *)0; - List *restinfo, *tideval; + List *rlst = NIL, + *lst; + TidPath *pathnode = (TidPath *) NULL; + List *restinfo, + *tideval; foreach (lst, rel->joininfo) { - JoinInfo *joininfo = (JoinInfo *)lfirst(lst); + JoinInfo *joininfo = (JoinInfo *)lfirst(lst); + restinfo = joininfo->jinfo_restrictinfo; tideval = TidqualFromRestrictinfo(rel->relids, restinfo); - if (tideval && length(tideval) == 1) + if (length(tideval) == 1) { pathnode = makeNode(TidPath); pathnode->path.pathtype = T_TidScan; pathnode->path.parent = rel; - pathnode->path.path_cost = 0.0; pathnode->path.pathkeys = NIL; - - pathnode->path.path_cost = cost_tidscan(tideval); + pathnode->path.path_cost = cost_tidscan(rel, tideval); pathnode->tideval = tideval; - /* - pathnode->tideval = copyObject(tideval); - freeList(tideval); - */ pathnode->unjoined_relids = joininfo->unjoined_relids; rlst = lappend(rlst, pathnode); } diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 6fda28aa74..fc476fe267 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.77 1999/11/23 20:06:57 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.78 2000/01/09 00:26:34 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -22,6 +22,7 @@ #include "optimizer/clauses.h" #include "optimizer/cost.h" #include "optimizer/internal.h" +#include "optimizer/paths.h" #include "optimizer/planmain.h" #include "optimizer/restrictinfo.h" #include "optimizer/tlist.h" @@ -31,12 +32,12 @@ static List *switch_outer(List *clauses); static int set_tlist_sort_info(List *tlist, List *pathkeys); -static Scan *create_scan_node(Path *best_path, List *tlist); -static Join *create_join_node(JoinPath *best_path, List *tlist); +static Scan *create_scan_node(Query *root, Path *best_path, List *tlist); +static Join *create_join_node(Query *root, JoinPath *best_path, List *tlist); static SeqScan *create_seqscan_node(Path *best_path, List *tlist, List *scan_clauses); -static IndexScan *create_indexscan_node(IndexPath *best_path, List *tlist, - List *scan_clauses); +static IndexScan *create_indexscan_node(Query *root, IndexPath *best_path, + List *tlist, List *scan_clauses); static TidScan *create_tidscan_node(TidPath *best_path, List *tlist, List *scan_clauses); static NestLoop *create_nestloop_node(NestPath *best_path, List *tlist, @@ -49,10 +50,11 @@ static HashJoin *create_hashjoin_node(HashPath *best_path, List *tlist, List *clauses, Plan *outer_node, List *outer_tlist, Plan *inner_node, List *inner_tlist); static List *fix_indxqual_references(List *indexquals, IndexPath *index_path); -static List *fix_indxqual_sublist(List *indexqual, IndexPath *index_path, - Form_pg_index index); -static Node *fix_indxqual_operand(Node *node, IndexPath *index_path, +static List *fix_indxqual_sublist(List *indexqual, int baserelid, Oid relam, Form_pg_index index); +static Node *fix_indxqual_operand(Node *node, int baserelid, + Form_pg_index index, + Oid *opclass); static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid, List *indxid, List *indxqual, List *indxqualorig); static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid, @@ -66,7 +68,8 @@ static MergeJoin *make_mergejoin(List *tlist, List *qpqual, List *mergeclauses, Plan *righttree, Plan *lefttree); static Material *make_material(List *tlist, Oid nonameid, Plan *lefttree, int keycount); -static void copy_costsize(Plan *dest, Plan *src); +static void copy_path_costsize(Plan *dest, Path *src); +static void copy_plan_costsize(Plan *dest, Plan *src); /* * create_plan @@ -84,46 +87,31 @@ static void copy_costsize(Plan *dest, Plan *src); * Returns the access plan. */ Plan * -create_plan(Path *best_path) +create_plan(Query *root, Path *best_path) { - List *tlist; + List *tlist = best_path->parent->targetlist; Plan *plan_node = (Plan *) NULL; - RelOptInfo *parent_rel; - int size; - int width; - int pages; - int tuples; - - parent_rel = best_path->parent; - tlist = parent_rel->targetlist; - size = parent_rel->size; - width = parent_rel->width; - pages = parent_rel->pages; - tuples = parent_rel->tuples; switch (best_path->pathtype) { case T_IndexScan: case T_SeqScan: case T_TidScan: - plan_node = (Plan *) create_scan_node(best_path, tlist); + plan_node = (Plan *) create_scan_node(root, best_path, tlist); break; case T_HashJoin: case T_MergeJoin: case T_NestLoop: - plan_node = (Plan *) create_join_node((JoinPath *) best_path, tlist); + plan_node = (Plan *) create_join_node(root, + (JoinPath *) best_path, + tlist); break; default: - /* do nothing */ + elog(ERROR, "create_plan: unknown pathtype %d", + best_path->pathtype); break; } - plan_node->plan_size = size; - plan_node->plan_width = width; - if (pages == 0) - pages = 1; - plan_node->plan_tupperpage = tuples / pages; - #ifdef NOT_USED /* fix xfunc */ /* sort clauses by cost/(1-selectivity) -- JMH 2/26/92 */ if (XfuncMode != XFUNC_OFF) @@ -149,9 +137,8 @@ create_plan(Path *best_path) * Returns the scan node. */ static Scan * -create_scan_node(Path *best_path, List *tlist) +create_scan_node(Query *root, Path *best_path, List *tlist) { - Scan *node = NULL; List *scan_clauses; @@ -168,7 +155,8 @@ create_scan_node(Path *best_path, List *tlist) break; case T_IndexScan: - node = (Scan *) create_indexscan_node((IndexPath *) best_path, + node = (Scan *) create_indexscan_node(root, + (IndexPath *) best_path, tlist, scan_clauses); break; @@ -199,7 +187,7 @@ create_scan_node(Path *best_path, List *tlist) * Returns the join node. */ static Join * -create_join_node(JoinPath *best_path, List *tlist) +create_join_node(Query *root, JoinPath *best_path, List *tlist) { Plan *outer_node; List *outer_tlist; @@ -208,13 +196,13 @@ create_join_node(JoinPath *best_path, List *tlist) List *clauses; Join *retval = NULL; - outer_node = create_plan((Path *) best_path->outerjoinpath); + outer_node = create_plan(root, best_path->outerjoinpath); outer_tlist = outer_node->targetlist; - inner_node = create_plan((Path *) best_path->innerjoinpath); + inner_node = create_plan(root, best_path->innerjoinpath); inner_tlist = inner_node->targetlist; - clauses = get_actual_clauses(best_path->pathinfo); + clauses = get_actual_clauses(best_path->path.parent->restrictinfo); switch (best_path->path.pathtype) { @@ -280,20 +268,19 @@ create_join_node(JoinPath *best_path, List *tlist) static SeqScan * create_seqscan_node(Path *best_path, List *tlist, List *scan_clauses) { - SeqScan *scan_node = (SeqScan *) NULL; - Index scan_relid = -1; - List *temp; + SeqScan *scan_node; + Index scan_relid; - temp = best_path->parent->relids; /* there should be exactly one base rel involved... */ - Assert(length(temp) == 1); - scan_relid = (Index) lfirsti(temp); + Assert(length(best_path->parent->relids) == 1); + + scan_relid = (Index) lfirsti(best_path->parent->relids); scan_node = make_seqscan(tlist, scan_clauses, scan_relid); - scan_node->plan.cost = best_path->path_cost; + copy_path_costsize(&scan_node->plan, best_path); return scan_node; } @@ -312,7 +299,8 @@ create_seqscan_node(Path *best_path, List *tlist, List *scan_clauses) * scan. */ static IndexScan * -create_indexscan_node(IndexPath *best_path, +create_indexscan_node(Query *root, + IndexPath *best_path, List *tlist, List *scan_clauses) { @@ -322,11 +310,12 @@ create_indexscan_node(IndexPath *best_path, List *ixid; IndexScan *scan_node; bool lossy = false; + double plan_rows; /* there should be exactly one base rel involved... */ Assert(length(best_path->path.parent->relids) == 1); - /* check and see if any of the indices are lossy */ + /* check to see if any of the indices are lossy */ foreach(ixid, best_path->indexid) { HeapTuple indexTuple; @@ -354,44 +343,72 @@ create_indexscan_node(IndexPath *best_path, * * Since the indexquals were generated from the restriction clauses * given by scan_clauses, there will normally be some duplications - * between the lists. Get rid of the duplicates, then add back if lossy. + * between the lists. We get rid of the duplicates, then add back + * if lossy. + * + * If this indexscan is a nestloop-join inner indexscan (as indicated + * by having nonempty joinrelids), then it uses indexqual conditions + * that are not part of the relation's restriction clauses. The rows + * estimate stored in the relation's RelOptInfo will be an overestimate + * because it did not take these extra conditions into account. So, + * in this case we recompute the selectivity of the whole scan --- + * considering both indexqual and qpqual --- rather than using the + * RelOptInfo's rows value. Since clausesel.c assumes it's working on + * minimized (no duplicates) expressions, we have to do that while we + * have the duplicate-free qpqual available. */ + plan_rows = best_path->path.parent->rows; /* OK unless nestloop inner */ + if (length(indxqual) > 1) { /* * Build an expression representation of the indexqual, expanding * the implicit OR and AND semantics of the first- and second-level - * lists. XXX Is it really necessary to do a deep copy here? + * lists. */ List *orclauses = NIL; List *orclause; Expr *indxqual_expr; foreach(orclause, indxqual) - { orclauses = lappend(orclauses, - make_ands_explicit((List *) copyObject(lfirst(orclause)))); - } + make_ands_explicit(lfirst(orclause))); indxqual_expr = make_orclause(orclauses); - /* this set_difference is almost certainly a waste of time... */ qpqual = set_difference(scan_clauses, lcons(indxqual_expr, NIL)); + if (best_path->joinrelids) + { + /* recompute output row estimate using all available quals */ + plan_rows = best_path->path.parent->tuples * + clauselist_selec(root, lcons(indxqual_expr, qpqual)); + } + if (lossy) - qpqual = lappend(qpqual, indxqual_expr); + qpqual = lappend(qpqual, copyObject(indxqual_expr)); } else if (indxqual != NIL) { /* Here, we can simply treat the first sublist as an independent * set of qual expressions, since there is no top-level OR behavior. */ - qpqual = set_difference(scan_clauses, lfirst(indxqual)); + List *indxqual_list = lfirst(indxqual); + + qpqual = set_difference(scan_clauses, indxqual_list); + + if (best_path->joinrelids) + { + /* recompute output row estimate using all available quals */ + plan_rows = best_path->path.parent->tuples * + clauselist_selec(root, nconc(listCopy(indxqual_list), qpqual)); + } + if (lossy) - qpqual = nconc(qpqual, (List *) copyObject(lfirst(indxqual))); + qpqual = nconc(qpqual, (List *) copyObject(indxqual_list)); } else - qpqual = NIL; + qpqual = scan_clauses; /* The executor needs a copy with the indexkey on the left of each clause * and with index attr numbers substituted for table ones. @@ -405,7 +422,8 @@ create_indexscan_node(IndexPath *best_path, fixed_indxqual, indxqual); - scan_node->scan.plan.cost = best_path->path.path_cost; + copy_path_costsize(&scan_node->scan.plan, &best_path->path); + scan_node->scan.plan.plan_rows = plan_rows; return scan_node; } @@ -416,11 +434,11 @@ make_tidscan(List *qptlist, Index scanrelid, List *tideval) { - TidScan *node = makeNode(TidScan); + TidScan *node = makeNode(TidScan); Plan *plan = &node->scan.plan; plan->cost = 0; - plan->plan_size = 0; + plan->plan_rows = 0; plan->plan_width = 0; plan->state = (EState *) NULL; plan->targetlist = qptlist; @@ -428,7 +446,7 @@ make_tidscan(List *qptlist, plan->lefttree = NULL; plan->righttree = NULL; node->scan.scanrelid = scanrelid; - node->tideval = copyObject(tideval); + node->tideval = copyObject(tideval); /* XXX do we really need a copy? */ node->needRescan = false; node->scan.scanstate = (CommonScanState *) NULL; @@ -443,25 +461,23 @@ make_tidscan(List *qptlist, static TidScan * create_tidscan_node(TidPath *best_path, List *tlist, List *scan_clauses) { - TidScan *scan_node = (TidScan *) NULL; - Index scan_relid = -1; - List *temp; - - temp = best_path->path.parent->relids; - if (temp == NULL) - elog(ERROR, "scanrelid is empty"); - else if (length(temp) != 1) - return scan_node; - else - scan_relid = (Index) lfirsti(temp); + TidScan *scan_node; + Index scan_relid; + + /* there should be exactly one base rel involved... */ + Assert(length(best_path->path.parent->relids) == 1); + + scan_relid = (Index) lfirsti(best_path->path.parent->relids); + scan_node = make_tidscan(tlist, - scan_clauses, - scan_relid, - best_path->tideval); + scan_clauses, + scan_relid, + best_path->tideval); if (best_path->unjoined_relids) scan_node->needRescan = true; - scan_node->scan.plan.cost = best_path->path.path_cost; + + copy_path_costsize(&scan_node->scan.plan, &best_path->path); return scan_node; } @@ -581,7 +597,7 @@ create_nestloop_node(NestPath *best_path, outer_node, inner_node); - join_node->join.cost = best_path->path.path_cost; + copy_path_costsize(&join_node->join, &best_path->path); return join_node; } @@ -639,7 +655,7 @@ create_mergejoin_node(MergePath *best_path, inner_node, outer_node); - join_node->join.cost = best_path->jpath.path.path_cost; + copy_path_costsize(&join_node->join, &best_path->jpath.path); return join_node; } @@ -699,7 +715,7 @@ create_hashjoin_node(HashPath *best_path, outer_node, (Plan *) hash_node); - join_node->join.cost = best_path->jpath.path.path_cost; + copy_path_costsize(&join_node->join, &best_path->jpath.path); return join_node; } @@ -713,10 +729,18 @@ create_hashjoin_node(HashPath *best_path, /* * fix_indxqual_references - * Adjust indexqual clauses to refer to index attributes instead of the - * attributes of the original relation. Also, commute clauses if needed - * to put the indexkey on the left. (Someday the executor might not need - * that, but for now it does.) + * Adjust indexqual clauses to the form the executor's indexqual + * machinery needs. + * + * We have three tasks here: + * * Var nodes representing index keys must have varattno equal to the + * index's attribute number, not the attribute number in the original rel. + * * indxpath.c may have selected an index that is binary-compatible with + * the actual expression operator, but not the same; we must replace the + * expression's operator with the binary-compatible equivalent operator + * that the index will recognize. + * * If the index key is on the right, commute the clause to put it on the + * left. (Someday the executor might not need this, but for now it does.) * * This code used to be entirely bogus for multi-index scans. Now it keeps * track of which index applies to each subgroup of index qual clauses... @@ -729,6 +753,7 @@ static List * fix_indxqual_references(List *indexquals, IndexPath *index_path) { List *fixed_quals = NIL; + int baserelid = lfirsti(index_path->path.parent->relids); List *indexids = index_path->indexid; List *i; @@ -737,19 +762,31 @@ fix_indxqual_references(List *indexquals, IndexPath *index_path) List *indexqual = lfirst(i); Oid indexid = lfirsti(indexids); HeapTuple indexTuple; + Oid relam; Form_pg_index index; + /* Get the relam from the index's pg_class entry */ + indexTuple = SearchSysCacheTuple(RELOID, + ObjectIdGetDatum(indexid), + 0, 0, 0); + if (!HeapTupleIsValid(indexTuple)) + elog(ERROR, "fix_indxqual_references: index %u not found in pg_class", + indexid); + relam = ((Form_pg_class) GETSTRUCT(indexTuple))->relam; + + /* Need the index's pg_index entry for other stuff */ indexTuple = SearchSysCacheTuple(INDEXRELID, ObjectIdGetDatum(indexid), 0, 0, 0); if (!HeapTupleIsValid(indexTuple)) - elog(ERROR, "fix_indxqual_references: index %u not found", + elog(ERROR, "fix_indxqual_references: index %u not found in pg_index", indexid); index = (Form_pg_index) GETSTRUCT(indexTuple); fixed_quals = lappend(fixed_quals, fix_indxqual_sublist(indexqual, - index_path, + baserelid, + relam, index)); indexids = lnext(indexids); @@ -761,11 +798,11 @@ fix_indxqual_references(List *indexquals, IndexPath *index_path) * Fix the sublist of indexquals to be used in a particular scan. * * For each qual clause, commute if needed to put the indexkey operand on the - * left, and then change its varno. We do not need to change the other side - * of the clause. + * left, and then change its varno. (We do not need to change the other side + * of the clause.) Also change the operator if necessary. */ static List * -fix_indxqual_sublist(List *indexqual, IndexPath *index_path, +fix_indxqual_sublist(List *indexqual, int baserelid, Oid relam, Form_pg_index index) { List *fixed_qual = NIL; @@ -779,6 +816,8 @@ fix_indxqual_sublist(List *indexqual, IndexPath *index_path, Datum constval; int flag; Expr *newclause; + Oid opclass, + newopno; if (!is_opclause((Node *) clause) || length(clause->args) != 2) @@ -788,8 +827,7 @@ fix_indxqual_sublist(List *indexqual, IndexPath *index_path, * * get_relattval sets flag&SEL_RIGHT if the indexkey is on the LEFT. */ - get_relattval((Node *) clause, - lfirsti(index_path->path.parent->relids), + get_relattval((Node *) clause, baserelid, &relid, &attno, &constval, &flag); /* Copy enough structure to allow commuting and replacing an operand @@ -802,10 +840,27 @@ fix_indxqual_sublist(List *indexqual, IndexPath *index_path, if ((flag & SEL_RIGHT) == 0) CommuteClause(newclause); - /* Now, change the indexkey operand as needed. */ + /* Now, determine which index attribute this is, + * change the indexkey operand as needed, + * and get the index opclass. + */ lfirst(newclause->args) = fix_indxqual_operand(lfirst(newclause->args), - index_path, - index); + baserelid, + index, + &opclass); + + /* Substitute the appropriate operator if the expression operator + * is merely binary-compatible with the index. This shouldn't fail, + * since indxpath.c found it before... + */ + newopno = indexable_operator(newclause, opclass, relam, true); + if (newopno == InvalidOid) + elog(ERROR, "fix_indxqual_sublist: failed to find substitute op"); + if (newopno != ((Oper *) newclause->oper)->opno) + { + newclause->oper = (Node *) copyObject(newclause->oper); + ((Oper *) newclause->oper)->opno = newopno; + } fixed_qual = lappend(fixed_qual, newclause); } @@ -813,12 +868,12 @@ fix_indxqual_sublist(List *indexqual, IndexPath *index_path, } static Node * -fix_indxqual_operand(Node *node, IndexPath *index_path, - Form_pg_index index) +fix_indxqual_operand(Node *node, int baserelid, Form_pg_index index, + Oid *opclass) { if (IsA(node, Var)) { - if (((Var *) node)->varno == lfirsti(index_path->path.parent->relids)) + if (((Var *) node)->varno == baserelid) { int varatt = ((Var *) node)->varattno; int pos; @@ -829,6 +884,7 @@ fix_indxqual_operand(Node *node, IndexPath *index_path, { Node *newnode = copyObject(node); ((Var *) newnode)->varattno = pos + 1; + *opclass = index->indclass[pos]; return newnode; } } @@ -851,6 +907,9 @@ fix_indxqual_operand(Node *node, IndexPath *index_path, * misbehaves...) */ + /* indclass[0] is the only class of a functional index */ + *opclass = index->indclass[0]; + /* return the unmodified node */ return node; } @@ -964,23 +1023,44 @@ set_tlist_sort_info(List *tlist, List *pathkeys) } /* + * Copy cost and size info from a Path node to the Plan node created from it. + * The executor won't use this info, but it's needed by EXPLAIN. + */ +static void +copy_path_costsize(Plan *dest, Path *src) +{ + if (src) + { + dest->cost = src->path_cost; + dest->plan_rows = src->parent->rows; + dest->plan_width = src->parent->width; + } + else + { + dest->cost = 0; + dest->plan_rows = 0; + dest->plan_width = 0; + } +} + +/* * Copy cost and size info from a lower plan node to an inserted node. * This is not critical, since the decisions have already been made, * but it helps produce more reasonable-looking EXPLAIN output. */ static void -copy_costsize(Plan *dest, Plan *src) +copy_plan_costsize(Plan *dest, Plan *src) { if (src) { dest->cost = src->cost; - dest->plan_size = src->plan_size; + dest->plan_rows = src->plan_rows; dest->plan_width = src->plan_width; } else { dest->cost = 0; - dest->plan_size = 0; + dest->plan_rows = 0; dest->plan_width = 0; } } @@ -1042,7 +1122,7 @@ make_seqscan(List *qptlist, SeqScan *node = makeNode(SeqScan); Plan *plan = &node->plan; - copy_costsize(plan, NULL); + copy_plan_costsize(plan, NULL); plan->state = (EState *) NULL; plan->targetlist = qptlist; plan->qual = qpqual; @@ -1065,7 +1145,7 @@ make_indexscan(List *qptlist, IndexScan *node = makeNode(IndexScan); Plan *plan = &node->scan.plan; - copy_costsize(plan, NULL); + copy_plan_costsize(plan, NULL); plan->state = (EState *) NULL; plan->targetlist = qptlist; plan->qual = qpqual; @@ -1140,7 +1220,7 @@ make_hash(List *tlist, Var *hashkey, Plan *lefttree) Hash *node = makeNode(Hash); Plan *plan = &node->plan; - copy_costsize(plan, lefttree); + copy_plan_costsize(plan, lefttree); plan->state = (EState *) NULL; plan->targetlist = tlist; plan->qual = NULL; @@ -1183,8 +1263,8 @@ make_sort(List *tlist, Oid nonameid, Plan *lefttree, int keycount) Sort *node = makeNode(Sort); Plan *plan = &node->plan; - copy_costsize(plan, lefttree); - plan->cost += cost_sort(NULL, plan->plan_size, plan->plan_width); + copy_plan_costsize(plan, lefttree); + plan->cost += cost_sort(NIL, plan->plan_rows, plan->plan_width); plan->state = (EState *) NULL; plan->targetlist = tlist; plan->qual = NIL; @@ -1205,7 +1285,7 @@ make_material(List *tlist, Material *node = makeNode(Material); Plan *plan = &node->plan; - copy_costsize(plan, lefttree); + copy_plan_costsize(plan, lefttree); plan->state = (EState *) NULL; plan->targetlist = tlist; plan->qual = NIL; @@ -1222,7 +1302,7 @@ make_agg(List *tlist, Plan *lefttree) { Agg *node = makeNode(Agg); - copy_costsize(&node->plan, lefttree); + copy_plan_costsize(&node->plan, lefttree); node->plan.state = (EState *) NULL; node->plan.qual = NULL; node->plan.targetlist = tlist; @@ -1241,7 +1321,7 @@ make_group(List *tlist, { Group *node = makeNode(Group); - copy_costsize(&node->plan, lefttree); + copy_plan_costsize(&node->plan, lefttree); node->plan.state = (EState *) NULL; node->plan.qual = NULL; node->plan.targetlist = tlist; @@ -1266,7 +1346,7 @@ make_unique(List *tlist, Plan *lefttree, char *uniqueAttr) Unique *node = makeNode(Unique); Plan *plan = &node->plan; - copy_costsize(plan, lefttree); + copy_plan_costsize(plan, lefttree); plan->state = (EState *) NULL; plan->targetlist = tlist; plan->qual = NIL; @@ -1292,7 +1372,7 @@ make_result(List *tlist, #ifdef NOT_USED tlist = generate_fjoin(tlist); #endif - copy_costsize(plan, subplan); + copy_plan_costsize(plan, subplan); plan->state = (EState *) NULL; plan->targetlist = tlist; plan->qual = NIL; diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c index ef219245aa..7316a79461 100644 --- a/src/backend/optimizer/plan/initsplan.c +++ b/src/backend/optimizer/plan/initsplan.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.40 1999/10/07 04:23:06 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.41 2000/01/09 00:26:36 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -30,6 +30,7 @@ static void add_restrict_and_join_to_rel(Query *root, Node *clause); static void add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo, Relids join_relids); static void add_vars_to_targetlist(Query *root, List *vars); +static void set_restrictinfo_joininfo(RestrictInfo *restrictinfo); static void check_mergejoinable(RestrictInfo *restrictinfo); static void check_hashjoinable(RestrictInfo *restrictinfo); @@ -165,12 +166,6 @@ add_restrict_and_join_to_rel(Query *root, Node *clause) restrictinfo->hashjoinoperator = InvalidOid; /* - * The selectivity of the clause must be computed regardless of - * whether it's a restriction or a join clause - */ - restrictinfo->selectivity = compute_clause_selec(root, clause); - - /* * Retrieve all relids and vars contained within the clause. */ clause_get_relids_vars(clause, &relids, &vars); @@ -189,12 +184,20 @@ add_restrict_and_join_to_rel(Query *root, Node *clause) { /* * 'clause' is a join clause, since there is more than one atom in - * the relid list. Add it to the join lists of all the relevant + * the relid list. Set additional RestrictInfo fields for joining. + */ + set_restrictinfo_joininfo(restrictinfo); + /* + * Add clause to the join lists of all the relevant * relations. (If, perchance, 'clause' contains NO vars, then * nothing will happen...) */ add_join_info_to_rels(root, restrictinfo, relids); - /* we are going to be doing a join, so add vars to targetlists */ + /* + * Add vars used in the join clause to targetlists of member relations, + * so that they will be emitted by the plan nodes that scan those + * relations (else they won't be available at the join node!). + */ add_vars_to_targetlist(root, vars); } } @@ -202,7 +205,7 @@ add_restrict_and_join_to_rel(Query *root, Node *clause) /* * add_join_info_to_rels * For every relation participating in a join clause, add 'restrictinfo' to - * the appropriate joininfo list (creating a new one and adding it to the + * the appropriate joininfo list (creating a new list and adding it to the * appropriate rel node if necessary). * * 'restrictinfo' describes the join clause @@ -218,8 +221,8 @@ add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo, foreach(join_relid, join_relids) { int cur_relid = lfirsti(join_relid); - JoinInfo *joininfo; Relids unjoined_relids = NIL; + JoinInfo *joininfo; List *otherrel; /* Get the relids not equal to the current relid */ @@ -230,18 +233,12 @@ add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo, } /* - * Find or make the joininfo node for this combination of rels + * Find or make the joininfo node for this combination of rels, + * and add the restrictinfo node to it. */ joininfo = find_joininfo_node(get_base_rel(root, cur_relid), unjoined_relids); - - /* - * And add the restrictinfo node to it. NOTE that each joininfo - * gets its own copy of the restrictinfo node! (Is this really - * necessary? Possibly ... later parts of the optimizer destructively - * modify restrict/join clauses...) - */ - joininfo->jinfo_restrictinfo = lcons(copyObject((void *) restrictinfo), + joininfo->jinfo_restrictinfo = lcons(restrictinfo, joininfo->jinfo_restrictinfo); } } @@ -253,36 +250,17 @@ add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo, *****************************************************************************/ /* - * set_joininfo_mergeable_hashable - * Examine each join clause used in a query and set the merge and hash - * info fields in those that are mergejoinable or hashjoinable. + * set_restrictinfo_joininfo + * Examine a RestrictInfo that has been determined to be a join clause, + * and set the merge and hash info fields if it can be merge/hash joined. */ -void -set_joininfo_mergeable_hashable(List *rel_list) +static void +set_restrictinfo_joininfo(RestrictInfo *restrictinfo) { - List *x; - - foreach(x, rel_list) - { - RelOptInfo *rel = (RelOptInfo *) lfirst(x); - List *y; - - foreach(y, rel->joininfo) - { - JoinInfo *joininfo = (JoinInfo *) lfirst(y); - List *z; - - foreach(z, joininfo->jinfo_restrictinfo) - { - RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(z); - - if (_enable_mergejoin_) - check_mergejoinable(restrictinfo); - if (_enable_hashjoin_) - check_hashjoinable(restrictinfo); - } - } - } + if (_enable_mergejoin_) + check_mergejoinable(restrictinfo); + if (_enable_hashjoin_) + check_hashjoinable(restrictinfo); } /* diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index 7dcafe35dc..fa1744ebb9 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.48 1999/12/09 05:58:52 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.49 2000/01/09 00:26:36 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -218,8 +218,6 @@ subplanner(Query *root, add_restrict_and_join_to_rels(root, qual); add_missing_rels_to_query(root); - set_joininfo_mergeable_hashable(root->base_rel_list); - final_rel = make_one_rel(root, root->base_rel_list); if (! final_rel) @@ -275,7 +273,7 @@ subplanner(Query *root, final_rel->cheapestpath->pathkeys)) { root->query_pathkeys = final_rel->cheapestpath->pathkeys; - return create_plan(final_rel->cheapestpath); + return create_plan(root, final_rel->cheapestpath); } /* @@ -283,7 +281,7 @@ subplanner(Query *root, * cheaper than doing an explicit sort on cheapestpath. */ cheapest_cost = final_rel->cheapestpath->path_cost + - cost_sort(root->query_pathkeys, final_rel->size, final_rel->width); + cost_sort(root->query_pathkeys, final_rel->rows, final_rel->width); sortedpath = get_cheapest_path_for_pathkeys(final_rel->pathlist, root->query_pathkeys, @@ -294,7 +292,7 @@ subplanner(Query *root, { /* Found a better presorted path, use it */ root->query_pathkeys = sortedpath->pathkeys; - return create_plan(sortedpath); + return create_plan(root, sortedpath); } /* otherwise, doing it the hard way is still cheaper */ } @@ -322,7 +320,7 @@ subplanner(Query *root, * backwards scan, we have to convert to Plan format and * then poke the result. */ - Plan *sortedplan = create_plan(sortedpath); + Plan *sortedplan = create_plan(root, sortedpath); List *sortedpathkeys; Assert(IsA(sortedplan, IndexScan)); @@ -350,5 +348,5 @@ subplanner(Query *root, * an aggregate function...) */ root->query_pathkeys = final_rel->cheapestpath->pathkeys; - return create_plan(final_rel->cheapestpath); + return create_plan(root, final_rel->cheapestpath); } diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 0f9bf1b8bb..a2551391e0 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.55 1999/11/23 20:07:00 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.56 2000/01/09 00:26:37 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -15,8 +15,6 @@ #include "postgres.h" - - #include "optimizer/cost.h" #include "optimizer/pathnode.h" #include "optimizer/paths.h" @@ -37,10 +35,7 @@ bool path_is_cheaper(Path *path1, Path *path2) { - Cost cost1 = path1->path_cost; - Cost cost2 = path2->path_cost; - - return (bool) (cost1 < cost2); + return (bool) (path1->path_cost < path2->path_cost); } /* @@ -60,8 +55,8 @@ set_cheapest(RelOptInfo *parent_rel, List *pathlist) List *p; Path *cheapest_so_far; - Assert(pathlist != NIL); Assert(IsA(parent_rel, RelOptInfo)); + Assert(pathlist != NIL); cheapest_so_far = (Path *) lfirst(pathlist); @@ -192,18 +187,11 @@ Path * create_seqscan_path(RelOptInfo *rel) { Path *pathnode = makeNode(Path); - int relid = 0; pathnode->pathtype = T_SeqScan; pathnode->parent = rel; - pathnode->path_cost = 0.0; pathnode->pathkeys = NIL; /* seqscan has unordered result */ - - if (rel->relids != NIL) /* can this happen? */ - relid = lfirsti(rel->relids); - - pathnode->path_cost = cost_seqscan(relid, - rel->pages, rel->tuples); + pathnode->path_cost = cost_seqscan(rel); return pathnode; } @@ -222,7 +210,7 @@ create_seqscan_path(RelOptInfo *rel) IndexPath * create_index_path(Query *root, RelOptInfo *rel, - RelOptInfo *index, + IndexOptInfo *index, List *restriction_clauses) { IndexPath *pathnode = makeNode(IndexPath); @@ -239,8 +227,7 @@ create_index_path(Query *root, * conditions. If we do have restriction conditions to use, they * will get inserted below. */ - Assert(length(index->relids) == 1); - pathnode->indexid = index->relids; + pathnode->indexid = lconsi(index->indexoid, NIL); pathnode->indexqual = lcons(NIL, NIL); pathnode->joinrelids = NIL; /* no join clauses here */ @@ -250,13 +237,9 @@ create_index_path(Query *root, * We have no restriction clauses, so compute scan cost using * selectivity of 1.0. */ - pathnode->path.path_cost = cost_index(lfirsti(index->relids), + pathnode->path.path_cost = cost_index(rel, index, index->pages, - 1.0, - rel->pages, - rel->tuples, - index->pages, - index->tuples, + (Selectivity) 1.0, false); } else @@ -266,9 +249,8 @@ create_index_path(Query *root, * restriction clause(s). Also, place indexqual in path node. */ List *indexquals; - float npages; - float selec; - Cost clausesel; + long npages; + Selectivity selec; indexquals = get_actual_clauses(restriction_clauses); /* expand special operators to indexquals the executor can handle */ @@ -280,39 +262,15 @@ create_index_path(Query *root, lfirst(pathnode->indexqual) = indexquals; index_selectivity(root, - lfirsti(rel->relids), - lfirsti(index->relids), + rel, + index, indexquals, &npages, &selec); - pathnode->path.path_cost = cost_index(lfirsti(index->relids), - (int) npages, - selec, - rel->pages, - rel->tuples, - index->pages, - index->tuples, + pathnode->path.path_cost = cost_index(rel, index, + npages, selec, false); - - /* - * Set selectivities of clauses used with index to the selectivity - * of this index, subdividing the selectivity equally over each of - * the clauses. To the extent that index_selectivity() can make a - * better estimate of the joint selectivity of these clauses than - * the product of individual estimates from compute_clause_selec() - * would be, this should give us a more accurate estimate of the - * total selectivity of all the clauses. - * - * XXX If there is more than one useful index for this rel, and the - * indexes can be used with different but overlapping groups of - * restriction clauses, we may end up with too optimistic an estimate, - * since set_clause_selectivities() will save the minimum of the - * per-clause selectivity estimated with each index. But that should - * be fairly unlikely for typical index usage. - */ - clausesel = pow(selec, 1.0 / (double) length(restriction_clauses)); - set_clause_selectivities(restriction_clauses, clausesel); } return pathnode; @@ -331,14 +289,12 @@ create_tidscan_path(RelOptInfo *rel, List *tideval) pathnode->path.pathtype = T_TidScan; pathnode->path.parent = rel; - pathnode->path.path_cost = 0.0; pathnode->path.pathkeys = NIL; - - pathnode->path.path_cost = cost_tidscan(tideval); + pathnode->path.path_cost = cost_tidscan(rel, tideval); /* divide selectivity for each clause to get an equal selectivity * as IndexScan does OK ? */ - pathnode->tideval = copyObject(tideval); + pathnode->tideval = copyObject(tideval); /* is copy really necessary? */ pathnode->unjoined_relids = NIL; return pathnode; @@ -350,7 +306,6 @@ create_tidscan_path(RelOptInfo *rel, List *tideval) * relations. * * 'joinrel' is the join relation. - * 'outer_rel' is the outer join relation * 'outer_path' is the outer path * 'inner_path' is the inner path * 'pathkeys' are the path keys of the new join path @@ -360,7 +315,6 @@ create_tidscan_path(RelOptInfo *rel, List *tideval) */ NestPath * create_nestloop_path(RelOptInfo *joinrel, - RelOptInfo *outer_rel, Path *outer_path, Path *inner_path, List *pathkeys) @@ -371,15 +325,10 @@ create_nestloop_path(RelOptInfo *joinrel, pathnode->path.parent = joinrel; pathnode->outerjoinpath = outer_path; pathnode->innerjoinpath = inner_path; - pathnode->pathinfo = joinrel->restrictinfo; pathnode->path.pathkeys = pathkeys; - pathnode->path.path_cost = cost_nestloop(outer_path->path_cost, - inner_path->path_cost, - outer_rel->size, - inner_path->parent->size, - page_size(outer_rel->size, - outer_rel->width), + pathnode->path.path_cost = cost_nestloop(outer_path, + inner_path, IsA(inner_path, IndexPath)); return pathnode; @@ -391,10 +340,6 @@ create_nestloop_path(RelOptInfo *joinrel, * two relations * * 'joinrel' is the join relation - * 'outersize' is the number of tuples in the outer relation - * 'innersize' is the number of tuples in the inner relation - * 'outerwidth' is the number of bytes per tuple in the outer relation - * 'innerwidth' is the number of bytes per tuple in the inner relation * 'outer_path' is the outer path * 'inner_path' is the inner path * 'pathkeys' are the path keys of the new join path @@ -405,10 +350,6 @@ create_nestloop_path(RelOptInfo *joinrel, */ MergePath * create_mergejoin_path(RelOptInfo *joinrel, - int outersize, - int innersize, - int outerwidth, - int innerwidth, Path *outer_path, Path *inner_path, List *pathkeys, @@ -433,19 +374,14 @@ create_mergejoin_path(RelOptInfo *joinrel, pathnode->jpath.path.parent = joinrel; pathnode->jpath.outerjoinpath = outer_path; pathnode->jpath.innerjoinpath = inner_path; - pathnode->jpath.pathinfo = joinrel->restrictinfo; pathnode->jpath.path.pathkeys = pathkeys; pathnode->path_mergeclauses = mergeclauses; pathnode->outersortkeys = outersortkeys; pathnode->innersortkeys = innersortkeys; - pathnode->jpath.path.path_cost = cost_mergejoin(outer_path->path_cost, - inner_path->path_cost, + pathnode->jpath.path.path_cost = cost_mergejoin(outer_path, + inner_path, outersortkeys, - innersortkeys, - outersize, - innersize, - outerwidth, - innerwidth); + innersortkeys); return pathnode; } @@ -455,10 +391,6 @@ create_mergejoin_path(RelOptInfo *joinrel, * Creates a pathnode corresponding to a hash join between two relations. * * 'joinrel' is the join relation - * 'outersize' is the number of tuples in the outer relation - * 'innersize' is the number of tuples in the inner relation - * 'outerwidth' is the number of bytes per tuple in the outer relation - * 'innerwidth' is the number of bytes per tuple in the inner relation * 'outer_path' is the cheapest outer path * 'inner_path' is the cheapest inner path * 'hashclauses' is a list of the hash join clause (always a 1-element list) @@ -467,14 +399,10 @@ create_mergejoin_path(RelOptInfo *joinrel, */ HashPath * create_hashjoin_path(RelOptInfo *joinrel, - int outersize, - int innersize, - int outerwidth, - int innerwidth, Path *outer_path, Path *inner_path, List *hashclauses, - Cost innerdisbursion) + Selectivity innerdisbursion) { HashPath *pathnode = makeNode(HashPath); @@ -482,14 +410,11 @@ create_hashjoin_path(RelOptInfo *joinrel, pathnode->jpath.path.parent = joinrel; pathnode->jpath.outerjoinpath = outer_path; pathnode->jpath.innerjoinpath = inner_path; - pathnode->jpath.pathinfo = joinrel->restrictinfo; /* A hashjoin never has pathkeys, since its ordering is unpredictable */ pathnode->jpath.path.pathkeys = NIL; pathnode->path_hashclauses = hashclauses; - pathnode->jpath.path.path_cost = cost_hashjoin(outer_path->path_cost, - inner_path->path_cost, - outersize, innersize, - outerwidth, innerwidth, + pathnode->jpath.path.path_cost = cost_hashjoin(outer_path, + inner_path, innerdisbursion); return pathnode; diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c index 03d29be4dc..ef0dbfbda9 100644 --- a/src/backend/optimizer/util/plancat.c +++ b/src/backend/optimizer/util/plancat.c @@ -8,14 +8,15 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/plancat.c,v 1.40 1999/11/22 17:56:17 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/plancat.c,v 1.41 2000/01/09 00:26:40 tgl Exp $ * *------------------------------------------------------------------------- */ -#include #include "postgres.h" +#include + #include "access/genam.h" #include "access/heapam.h" #include "catalog/catname.h" @@ -23,20 +24,12 @@ #include "catalog/pg_inherits.h" #include "optimizer/clauses.h" #include "optimizer/internal.h" +#include "optimizer/paths.h" #include "optimizer/plancat.h" #include "parser/parsetree.h" #include "utils/syscache.h" -static void IndexSelectivity(Oid indexrelid, Oid baserelid, int nIndexKeys, - Oid *operatorObjectIds, - AttrNumber *varAttributeNumbers, - Datum *constValues, - int *constFlags, - float *idxPages, - float *idxSelec); - - /* * relation_info - * Retrieves catalog information for a given relation. @@ -47,39 +40,33 @@ static void IndexSelectivity(Oid indexrelid, Oid baserelid, int nIndexKeys, */ void relation_info(Query *root, Index relid, - bool *hasindex, int *pages, int *tuples) + bool *hasindex, long *pages, double *tuples) { + Oid relationObjectId = getrelid(relid, root->rtable); HeapTuple relationTuple; Form_pg_class relation; - Oid relationObjectId; - relationObjectId = getrelid(relid, root->rtable); relationTuple = SearchSysCacheTuple(RELOID, ObjectIdGetDatum(relationObjectId), 0, 0, 0); - if (HeapTupleIsValid(relationTuple)) - { - relation = (Form_pg_class) GETSTRUCT(relationTuple); - - *hasindex = (relation->relhasindex) ? true : false; - *pages = relation->relpages; - *tuples = relation->reltuples; - } - else - { + if (!HeapTupleIsValid(relationTuple)) elog(ERROR, "relation_info: Relation %u not found", relationObjectId); - } + relation = (Form_pg_class) GETSTRUCT(relationTuple); + + *hasindex = (relation->relhasindex) ? true : false; + *pages = relation->relpages; + *tuples = relation->reltuples; } /* * find_secondary_indexes - * Creates a list of RelOptInfo nodes containing information for each + * Creates a list of IndexOptInfo nodes containing information for each * secondary index defined on the given relation. * * 'relid' is the RT index of the relation for which indices are being located * - * Returns a list of new index RelOptInfo nodes. + * Returns a list of new IndexOptInfo nodes. */ List * find_secondary_indexes(Query *root, Index relid) @@ -105,7 +92,7 @@ find_secondary_indexes(Query *root, Index relid) while (HeapTupleIsValid(indexTuple = heap_getnext(scan, 0))) { Form_pg_index index = (Form_pg_index) GETSTRUCT(indexTuple); - RelOptInfo *info = makeNode(RelOptInfo); + IndexOptInfo *info = makeNode(IndexOptInfo); int i; Relation indexRelation; uint16 amstrategy; @@ -120,7 +107,7 @@ find_secondary_indexes(Query *root, Index relid) info->ordering = (Oid *) palloc(sizeof(Oid) * (INDEX_MAX_KEYS+1)); /* Extract info from the pg_index tuple */ - info->relids = lconsi(index->indexrelid, NIL); + info->indexoid = index->indexrelid; info->indproc = index->indproc; /* functional index ?? */ if (VARSIZE(&index->indpred) != 0) /* partial index ?? */ { @@ -172,17 +159,6 @@ find_secondary_indexes(Query *root, Index relid) info->ordering[i] = ((Form_pg_amop) GETSTRUCT(amopTuple))->amopopr; } - info->indexed = false; /* not indexed itself */ - info->size = 0; - info->width = 0; - info->targetlist = NIL; - info->pathlist = NIL; - info->cheapestpath = NULL; - info->pruneable = true; - info->restrictinfo = NIL; - info->joininfo = NIL; - info->innerjoin = NIL; - indexes = lcons(info, indexes); } @@ -200,77 +176,211 @@ find_secondary_indexes(Query *root, Index relid) * but here we consider the cost of just one pass. * * 'root' is the query root - * 'relid' is the RT index of the relation being scanned - * 'indexid' is the OID of the index to be used + * 'rel' is the relation being scanned + * 'index' is the index to be used * 'indexquals' is the list of qual condition exprs (implicit AND semantics) * '*idxPages' receives an estimate of the number of index pages touched - * '*idxSelec' receives an estimate of selectivity of the scan + * '*idxSelec' receives an estimate of selectivity of the scan, ie fraction + * of the relation's tuples that will be retrieved */ void index_selectivity(Query *root, - int relid, - Oid indexid, + RelOptInfo *rel, + IndexOptInfo *index, List *indexquals, - float *idxPages, - float *idxSelec) + long *idxPages, + Selectivity *idxSelec) { - int nclauses = length(indexquals); - Oid *opno_array; - AttrNumber *attno_array; - Datum *value_array; - int *flag_array; + int relid; + Oid baserelid, + indexrelid; + HeapTuple indRel, + indexTuple; + Form_pg_class indexrelation; + Oid relam; + Form_pg_index pgindex; + int nIndexKeys; + float64data npages, + select, + fattr_select; + bool nphack = false; List *q; - int i; - if (nclauses <= 0) - { - *idxPages = 0.0; - *idxSelec = 1.0; - return; - } - opno_array = (Oid *) palloc(nclauses * sizeof(Oid)); - attno_array = (AttrNumber *) palloc(nclauses * sizeof(AttrNumber)); - value_array = (Datum *) palloc(nclauses * sizeof(Datum)); - flag_array = (int *) palloc(nclauses * sizeof(int)); + Assert(length(rel->relids) == 1); /* must be a base rel */ + relid = lfirsti(rel->relids); + + baserelid = getrelid(relid, root->rtable); + indexrelid = index->indexoid; + + indRel = SearchSysCacheTuple(RELOID, + ObjectIdGetDatum(indexrelid), + 0, 0, 0); + if (!HeapTupleIsValid(indRel)) + elog(ERROR, "index_selectivity: index %u not found in pg_class", + indexrelid); + indexrelation = (Form_pg_class) GETSTRUCT(indRel); + relam = indexrelation->relam; + + indexTuple = SearchSysCacheTuple(INDEXRELID, + ObjectIdGetDatum(indexrelid), + 0, 0, 0); + if (!HeapTupleIsValid(indexTuple)) + elog(ERROR, "index_selectivity: index %u not found in pg_index", + indexrelid); + pgindex = (Form_pg_index) GETSTRUCT(indexTuple); + + nIndexKeys = 1; + while (pgindex->indclass[nIndexKeys] != InvalidOid) + nIndexKeys++; + + /* + * Hack for non-functional btree npages estimation: npages = + * index_pages * selectivity_of_1st_attr_clause(s) - vadim 04/24/97 + */ + if (relam == BTREE_AM_OID && pgindex->indproc == InvalidOid) + nphack = true; + + npages = 0.0; + select = 1.0; + fattr_select = 1.0; - i = 0; foreach(q, indexquals) { Node *expr = (Node *) lfirst(q); + Oid opno; int dummyrelid; + AttrNumber attno; + Datum value; + int flag; + Oid indclass; + HeapTuple amopTuple; + Form_pg_amop amop; + float64 amopnpages, + amopselect; + /* + * Extract info from clause. + */ if (is_opclause(expr)) - opno_array[i] = ((Oper *) ((Expr *) expr)->oper)->opno; + opno = ((Oper *) ((Expr *) expr)->oper)->opno; else - opno_array[i] = InvalidOid; + opno = InvalidOid; + get_relattval(expr, relid, &dummyrelid, &attno, &value, &flag); - get_relattval(expr, relid, &dummyrelid, &attno_array[i], - &value_array[i], &flag_array[i]); - i++; + /* + * Find the AM class for this key. + */ + if (pgindex->indproc != InvalidOid) + { + /* + * Functional index: AM class is the first one defined since + * functional indices have exactly one key. + */ + indclass = pgindex->indclass[0]; + } + else + { + int i; + indclass = InvalidOid; + for (i = 0; pgindex->indkey[i]; i++) + { + if (attno == pgindex->indkey[i]) + { + indclass = pgindex->indclass[i]; + break; + } + } + } + if (!OidIsValid(indclass)) + { + /* + * Presumably this means that we are using a functional index + * clause and so had no variable to match to the index key ... + * if not we are in trouble. + */ + elog(NOTICE, "index_selectivity: no key %d in index %u", + attno, indexrelid); + continue; + } + + amopTuple = SearchSysCacheTuple(AMOPOPID, + ObjectIdGetDatum(indclass), + ObjectIdGetDatum(opno), + ObjectIdGetDatum(relam), + 0); + if (!HeapTupleIsValid(amopTuple)) + { + /* + * We might get here because indxpath.c selected a binary- + * compatible index. Try again with the compatible operator. + */ + if (opno != InvalidOid) + { + opno = indexable_operator((Expr *) expr, indclass, relam, + ((flag & SEL_RIGHT) != 0)); + amopTuple = SearchSysCacheTuple(AMOPOPID, + ObjectIdGetDatum(indclass), + ObjectIdGetDatum(opno), + ObjectIdGetDatum(relam), + 0); + } + if (!HeapTupleIsValid(amopTuple)) + elog(ERROR, "index_selectivity: no amop %u %u %u", + indclass, opno, relam); + } + amop = (Form_pg_amop) GETSTRUCT(amopTuple); + + if (!nphack) + { + amopnpages = (float64) fmgr(amop->amopnpages, + (char *) opno, + (char *) baserelid, + (char *) (int) attno, + (char *) value, + (char *) flag, + (char *) nIndexKeys, + (char *) indexrelid); + if (PointerIsValid(amopnpages)) + npages += *amopnpages; + } + + amopselect = (float64) fmgr(amop->amopselect, + (char *) opno, + (char *) baserelid, + (char *) (int) attno, + (char *) value, + (char *) flag, + (char *) nIndexKeys, + (char *) indexrelid); + if (PointerIsValid(amopselect)) + { + select *= *amopselect; + if (nphack && attno == pgindex->indkey[0]) + fattr_select *= *amopselect; + } } - IndexSelectivity(indexid, - getrelid(relid, root->rtable), - nclauses, - opno_array, - attno_array, - value_array, - flag_array, - idxPages, - idxSelec); - - pfree(opno_array); - pfree(attno_array); - pfree(value_array); - pfree(flag_array); + /* + * Estimation of npages below is hack of course, but it's better than + * it was before. - vadim 04/09/97 + */ + if (nphack) + { + npages = fattr_select * indexrelation->relpages; + *idxPages = (long) ceil((double) npages); + } + else + { + if (nIndexKeys > 1) + npages = npages / (1.0 + nIndexKeys); + *idxPages = (long) ceil((double) (npages / nIndexKeys)); + } + *idxSelec = select; } /* * restriction_selectivity * - * NOTE: The routine is now merged with RestrictionClauseSelectivity - * as defined in plancat.c - * * Returns the selectivity of a specified operator. * This code executes registered procedures stored in the * operator relation, by calling the function manager. @@ -279,7 +389,7 @@ index_selectivity(Query *root, * relation OIDs or attribute numbers are 0, then the clause * isn't of the form (op var const). */ -Cost +Selectivity restriction_selectivity(Oid functionObjectId, Oid operatorObjectId, Oid relationObjectId, @@ -297,28 +407,25 @@ restriction_selectivity(Oid functionObjectId, (char *) constFlag, NULL); if (!PointerIsValid(result)) - elog(ERROR, "RestrictionClauseSelectivity: bad pointer"); + elog(ERROR, "restriction_selectivity: bad pointer"); if (*result < 0.0 || *result > 1.0) - elog(ERROR, "RestrictionClauseSelectivity: bad value %lf", - *result); + elog(ERROR, "restriction_selectivity: bad value %lf", *result); - return (Cost) *result; + return (Selectivity) *result; } /* * join_selectivity - * Similarly, this routine is merged with JoinClauseSelectivity in - * plancat.c * - * Returns the selectivity of an operator, given the join clause - * information. + * Returns the selectivity of an operator, given the join clause + * information. * * XXX The assumption in the selectivity procedures is that if the * relation OIDs or attribute numbers are 0, then the clause * isn't of the form (op var var). */ -Cost +Selectivity join_selectivity(Oid functionObjectId, Oid operatorObjectId, Oid relationObjectId1, @@ -336,13 +443,12 @@ join_selectivity(Oid functionObjectId, (char *) (int) attributeNumber2, NULL); if (!PointerIsValid(result)) - elog(ERROR, "JoinClauseSelectivity: bad pointer"); + elog(ERROR, "join_selectivity: bad pointer"); if (*result < 0.0 || *result > 1.0) - elog(ERROR, "JoinClauseSelectivity: bad value %lf", - *result); + elog(ERROR, "join_selectivity: bad value %lf", *result); - return (Cost) *result; + return (Selectivity) *result; } /* @@ -421,172 +527,3 @@ VersionGetParents(Oid verrelid) } #endif - - -/***************************************************************************** - * - *****************************************************************************/ - -/* - * IndexSelectivity - * - * Calls the 'amopnpages' and 'amopselect' functions for each - * AM operator when a given index (specified by 'indexrelid') is used. - * The total number of pages and product of the selectivities are returned. - * - * Assumption: the attribute numbers and operator ObjectIds are in order - * WRT to each other (otherwise, you have no way of knowing which - * AM operator class or attribute number corresponds to which operator. - * - * 'nIndexKeys' is the number of qual clauses in use - * 'varAttributeNumbers' contains attribute numbers for variables - * 'constValues' contains the constant values - * 'constFlags' describes how to treat the constants in each clause - */ -static void -IndexSelectivity(Oid indexrelid, - Oid baserelid, - int nIndexKeys, - Oid *operatorObjectIds, - AttrNumber *varAttributeNumbers, - Datum *constValues, - int *constFlags, - float *idxPages, - float *idxSelec) -{ - int i, - n; - HeapTuple indexTuple, - amopTuple, - indRel; - Form_pg_class indexrelation; - Form_pg_index index; - Form_pg_amop amop; - Oid indclass; - float64data npages, - select; - float64 amopnpages, - amopselect; - Oid relam; - bool nphack = false; - float64data fattr_select = 1.0; - - indRel = SearchSysCacheTuple(RELOID, - ObjectIdGetDatum(indexrelid), - 0, 0, 0); - if (!HeapTupleIsValid(indRel)) - elog(ERROR, "IndexSelectivity: index %u not found", - indexrelid); - indexrelation = (Form_pg_class) GETSTRUCT(indRel); - relam = indexrelation->relam; - - indexTuple = SearchSysCacheTuple(INDEXRELID, - ObjectIdGetDatum(indexrelid), - 0, 0, 0); - if (!HeapTupleIsValid(indexTuple)) - elog(ERROR, "IndexSelectivity: index %u not found", - indexrelid); - index = (Form_pg_index) GETSTRUCT(indexTuple); - - /* - * Hack for non-functional btree npages estimation: npages = - * index_pages * selectivity_of_1st_attr_clause(s) - vadim 04/24/97 - */ - if (relam == BTREE_AM_OID && - varAttributeNumbers[0] != InvalidAttrNumber) - nphack = true; - - npages = 0.0; - select = 1.0; - for (n = 0; n < nIndexKeys; n++) - { - /* - * Find the AM class for this key. - * - * If the first attribute number is invalid then we have a functional - * index, and AM class is the first one defined since functional - * indices have exactly one key. - */ - indclass = (varAttributeNumbers[0] == InvalidAttrNumber) ? - index->indclass[0] : InvalidOid; - i = 0; - while ((i < nIndexKeys) && (indclass == InvalidOid)) - { - if (varAttributeNumbers[n] == index->indkey[i]) - { - indclass = index->indclass[i]; - break; - } - i++; - } - if (!OidIsValid(indclass)) - { - - /* - * Presumably this means that we are using a functional index - * clause and so had no variable to match to the index key ... - * if not we are in trouble. - */ - elog(NOTICE, "IndexSelectivity: no key %d in index %u", - varAttributeNumbers[n], indexrelid); - continue; - } - - amopTuple = SearchSysCacheTuple(AMOPOPID, - ObjectIdGetDatum(indclass), - ObjectIdGetDatum(operatorObjectIds[n]), - ObjectIdGetDatum(relam), - 0); - if (!HeapTupleIsValid(amopTuple)) - elog(ERROR, "IndexSelectivity: no amop %u %u %u", - indclass, operatorObjectIds[n], relam); - amop = (Form_pg_amop) GETSTRUCT(amopTuple); - - if (!nphack) - { - amopnpages = (float64) fmgr(amop->amopnpages, - (char *) operatorObjectIds[n], - (char *) baserelid, - (char *) (int) varAttributeNumbers[n], - (char *) constValues[n], - (char *) constFlags[n], - (char *) nIndexKeys, - (char *) indexrelid); - if (PointerIsValid(amopnpages)) - npages += *amopnpages; - } - - amopselect = (float64) fmgr(amop->amopselect, - (char *) operatorObjectIds[n], - (char *) baserelid, - (char *) (int) varAttributeNumbers[n], - (char *) constValues[n], - (char *) constFlags[n], - (char *) nIndexKeys, - (char *) indexrelid); - - if (PointerIsValid(amopselect)) - { - select *= *amopselect; - if (nphack && varAttributeNumbers[n] == index->indkey[0]) - fattr_select *= *amopselect; - } - } - - /* - * Estimation of npages below is hack of course, but it's better than - * it was before. - vadim 04/09/97 - */ - if (nphack) - { - npages = fattr_select * indexrelation->relpages; - *idxPages = ceil((double) npages); - } - else - { - if (nIndexKeys > 1) - npages = npages / (1.0 + nIndexKeys); - *idxPages = ceil((double) (npages / nIndexKeys)); - } - *idxSelec = select; -} diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index 885d0f0715..bb6773dfe1 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.19 1999/08/16 02:17:58 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.20 2000/01/09 00:26:41 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -37,21 +37,15 @@ get_base_rel(Query *root, int relid) { rel = makeNode(RelOptInfo); rel->relids = relids; - rel->indexed = false; - rel->pages = 0; - rel->tuples = 0; - rel->size = 0; + rel->rows = 0; rel->width = 0; rel->targetlist = NIL; rel->pathlist = NIL; rel->cheapestpath = (Path *) NULL; rel->pruneable = true; - rel->classlist = NULL; - rel->indexkeys = NULL; - rel->ordering = NULL; - rel->relam = InvalidOid; - rel->indproc = InvalidOid; - rel->indpred = NIL; + rel->indexed = false; + rel->pages = 0; + rel->tuples = 0; rel->restrictinfo = NIL; rel->joininfo = NIL; rel->innerjoin = NIL; diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c index 0d1ee7b64b..3424155dfb 100644 --- a/src/backend/utils/adt/selfuncs.c +++ b/src/backend/utils/adt/selfuncs.c @@ -10,7 +10,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/utils/adt/selfuncs.c,v 1.44 1999/11/25 00:21:34 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/utils/adt/selfuncs.c,v 1.45 2000/01/09 00:26:20 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -36,6 +36,9 @@ /* are we looking at a functional index selectivity request? */ #define FunctionalSelectivity(nIndKeys,attNum) ((attNum)==InvalidAttrNumber) +/* default selectivity estimate for equalities such as "A = b" */ +#define DEFAULT_EQ_SEL 0.01 + /* default selectivity estimate for inequalities such as "A < b" */ #define DEFAULT_INEQ_SEL (1.0 / 3.0) @@ -75,7 +78,7 @@ eqsel(Oid opid, result = (float64) palloc(sizeof(float64data)); if (NONVALUE(attno) || NONVALUE(relid)) - *result = 0.1; + *result = DEFAULT_EQ_SEL; else { Oid typid; @@ -369,15 +372,16 @@ eqjoinsel(Oid opid, float64data num1, num2, min; + bool unknown1 = NONVALUE(relid1) || NONVALUE(attno1); + bool unknown2 = NONVALUE(relid2) || NONVALUE(attno2); result = (float64) palloc(sizeof(float64data)); - if (NONVALUE(attno1) || NONVALUE(relid1) || - NONVALUE(attno2) || NONVALUE(relid2)) - *result = 0.1; + if (unknown1 && unknown2) + *result = DEFAULT_EQ_SEL; else { - num1 = get_attdisbursion(relid1, attno1, 0.01); - num2 = get_attdisbursion(relid2, attno2, 0.01); + num1 = unknown1 ? 1.0 : get_attdisbursion(relid1, attno1, 0.01); + num2 = unknown2 ? 1.0 : get_attdisbursion(relid2, attno2, 0.01); /* * The join selectivity cannot be more than num2, since each * tuple in table 1 could match no more than num2 fraction of @@ -386,6 +390,9 @@ eqjoinsel(Oid opid, * less). By the same reasoning it is not more than num1. * The min is therefore an upper bound. * + * If we know the disbursion of only one side, use it; the reasoning + * above still works. + * * XXX can we make a better estimate here? Using the nullfrac * statistic might be helpful, for example. Assuming the operator * is strict (does not succeed for null inputs) then the selectivity diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index 94641eff08..e66d6c4dfb 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -6,7 +6,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: nodes.h,v 1.59 1999/12/16 17:24:19 momjian Exp $ + * $Id: nodes.h,v 1.60 2000/01/09 00:26:42 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -82,6 +82,7 @@ typedef enum NodeTag T_JoinInfo, T_Stream, T_TidPath, + T_IndexOptInfo, /*--------------------- * TAGS FOR EXECUTOR NODES (execnodes.h) @@ -286,12 +287,17 @@ extern void *copyObject(void *obj); extern bool equal(void *a, void *b); -/* ---------------- - * I don't know why this is here. Most likely a hack.. - * -cim 6/3/90 - * ---------------- +/* + * Typedefs for identifying qualifier selectivities and plan costs as such. + * These are just plain "double"s, but declaring a variable as Selectivity + * or Cost makes the intent more obvious. + * + * These could have gone into plannodes.h or some such, but many files + * depend on them... */ -typedef float Cost; +typedef double Selectivity; /* fraction of tuples a qualifier will pass */ +typedef double Cost; /* execution cost (in page-access units) */ + /* * CmdType - diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index 9cd06e2d93..324423aa95 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -6,7 +6,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: plannodes.h,v 1.34 1999/11/23 20:07:02 momjian Exp $ + * $Id: plannodes.h,v 1.35 2000/01/09 00:26:43 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -63,10 +63,12 @@ typedef struct Plan { NodeTag type; + + /* planner's estimates of cost and result size */ Cost cost; - int plan_size; + double plan_rows; int plan_width; - int plan_tupperpage; + EState *state; /* at execution time, state's of * individual nodes point to one EState * for the whole top-level plan */ @@ -185,10 +187,10 @@ typedef struct IndexScan */ typedef struct TidScan { - Scan scan; + Scan scan; bool needRescan; - List *tideval; - TidScanState *tidstate; + List *tideval; + TidScanState *tidstate; } TidScan; /* diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h index 0f143017b2..55850cef5e 100644 --- a/src/include/nodes/relation.h +++ b/src/include/nodes/relation.h @@ -6,7 +6,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: relation.h,v 1.39 1999/11/23 20:07:02 momjian Exp $ + * $Id: relation.h,v 1.40 2000/01/09 00:26:44 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -33,13 +33,10 @@ typedef List *Relids; * * relids - List of base-relation identifiers; it is a base relation * if there is just one, a join relation if more than one - * indexed - true if the relation has secondary indices - * pages - number of pages in the relation - * tuples - number of tuples in the relation - * size - estimated number of tuples in the relation after restriction - * clauses have been applied + * rows - estimated number of tuples in the relation after restriction + * clauses have been applied (ie, output rows of a plan for it) * width - avg. number of bytes per tuple in the relation after the - * appropriate projections have been done + * appropriate projections have been done (ie, output width) * targetlist - List of TargetList nodes * pathlist - List of Path nodes, one for each potentially useful * method of generating the relation @@ -47,20 +44,11 @@ typedef List *Relids; * pruneable - flag to let the planner know whether it can prune the * pathlist of this RelOptInfo or not. * - * * If the relation is a (secondary) index it will have the following - * fields set: - * - * classlist - List of PG_AMOPCLASS OIDs for the index - * indexkeys - List of base-relation attribute numbers that are index keys - * ordering - List of PG_OPERATOR OIDs which order the indexscan result - * relam - the OID of the pg_am of the index - * - * NB. the last element of the arrays classlist, indexkeys and ordering - * is always 0. + * * If the relation is a base relation it will have these fields set: * - * Index relations do not participate in the join tree in the way - * that regular base relations do, but it is still convenient to - * represent them by RelOptInfos. + * indexed - true if the relation has secondary indices + * pages - number of disk pages in relation + * tuples - number of tuples in relation (not considering restrictions) * * * The presence of the remaining fields depends on the restrictions * and joins that the relation participates in: @@ -79,16 +67,11 @@ typedef struct RelOptInfo NodeTag type; /* all relations included in this RelOptInfo */ - Relids relids; /* integer list of base relids */ - - /* catalog statistics information */ - bool indexed; - int pages; - int tuples; + Relids relids; /* integer list of base relids (RT indexes) */ - /* estimates generated by planner. XXX int is probably too small... */ - int size; - int width; + /* size estimates generated by planner */ + double rows; /* estimated number of result tuples */ + int width; /* estimated avg width of result tuples */ /* materialization information */ List *targetlist; @@ -96,14 +79,10 @@ typedef struct RelOptInfo struct Path *cheapestpath; bool pruneable; - /* used solely by indices: */ - Oid *classlist; /* classes of AM operators */ - int *indexkeys; /* keys over which we're indexing */ - Oid *ordering; /* OIDs of sort operators for each key */ - Oid relam; /* OID of the access method (in pg_am) */ - - Oid indproc; /* if a functional index */ - List *indpred; /* if a partial index */ + /* statistics from pg_class (only valid if it's a base rel!) */ + bool indexed; + long pages; + double tuples; /* used by various scans and joins: */ List *restrictinfo; /* RestrictInfo structures */ @@ -116,6 +95,48 @@ typedef struct RelOptInfo } RelOptInfo; /* + * IndexOptInfo + * Per-index information for planning/optimization + * + * Prior to Postgres 7.0, RelOptInfo was used to describe both relations + * and indexes, but that created confusion without actually doing anything + * useful. So now we have a separate IndexOptInfo struct for indexes. + * + * indexoid - OID of the index relation itself + * pages - number of disk pages in index + * tuples - number of index tuples in index + * classlist - List of PG_AMOPCLASS OIDs for the index + * indexkeys - List of base-relation attribute numbers that are index keys + * ordering - List of PG_OPERATOR OIDs which order the indexscan result + * relam - the OID of the pg_am of the index + * indproc - OID of the function if a functional index, else 0 + * indpred - index predicate if a partial index, else NULL + * + * NB. the last element of the arrays classlist, indexkeys and ordering + * is always 0. + */ + +typedef struct IndexOptInfo +{ + NodeTag type; + + Oid indexoid; /* OID of the index relation */ + + /* statistics from pg_class */ + long pages; + double tuples; + + /* index descriptor information */ + Oid *classlist; /* classes of AM operators */ + int *indexkeys; /* keys over which we're indexing */ + Oid *ordering; /* OIDs of sort operators for each key */ + Oid relam; /* OID of the access method (in pg_am) */ + + Oid indproc; /* if a functional index */ + List *indpred; /* if a partial index */ +} IndexOptInfo; + +/* * PathKeys * * The sort ordering of a path is represented by a list of sublists of @@ -208,8 +229,6 @@ typedef struct JoinPath { Path path; - List *pathinfo; /* copy of parent->restrictinfo; REMOVE? */ - Path *outerjoinpath; /* path for the outer side of the join */ Path *innerjoinpath; /* path for the inner side of the join */ } JoinPath; @@ -296,10 +315,10 @@ typedef struct RestrictInfo NodeTag type; Expr *clause; /* the represented clause of WHERE cond */ - Cost selectivity; /* estimated selectivity */ /* only used if clause is an OR clause: */ - List *subclauseindices; /* lists of indexes matching subclauses */ + List *subclauseindices; /* indexes matching subclauses */ + /* subclauseindices is a List of Lists of IndexOptInfos */ /* valid if clause is mergejoinable, else InvalidOid: */ Oid mergejoinoperator; /* copy of clause operator */ @@ -346,7 +365,8 @@ typedef struct JoinInfo * cinfo -- if NULL, this stream node referes to the path node. * Otherwise this is a pointer to the current clause. * clausetype -- whether cinfo is in loc_restrictinfo or pathinfo in the - * path node (XXX this is now used only by dead code...) + * path node (XXX this is now used only by dead code, which is + * good because the distinction no longer exists...) * upstream -- linked list pointer upwards * downstream -- ditto, downwards * groupup -- whether or not this node is in a group with the node upstream @@ -365,7 +385,7 @@ typedef struct Stream StreamPtr downstream; bool groupup; Cost groupcost; - Cost groupsel; + Selectivity groupsel; } Stream; #endif /* RELATION_H */ diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h index abde39b237..c654b6953e 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -6,7 +6,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: cost.h,v 1.24 1999/11/23 20:07:05 momjian Exp $ + * $Id: cost.h,v 1.25 2000/01/09 00:26:46 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -33,34 +33,28 @@ extern bool _enable_mergejoin_; extern bool _enable_hashjoin_; extern bool _enable_tidscan_; -extern Cost cost_seqscan(int relid, int relpages, int reltuples); -extern Cost cost_index(Oid indexid, int expected_indexpages, Cost selec, - int relpages, int reltuples, int indexpages, - int indextuples, bool is_injoin); -extern Cost cost_tidscan(List *evallist); -extern Cost cost_sort(List *pathkeys, int tuples, int width); -extern Cost cost_nestloop(Cost outercost, Cost innercost, int outertuples, - int innertuples, int outerpages, bool is_indexjoin); -extern Cost cost_mergejoin(Cost outercost, Cost innercost, - List *outersortkeys, List *innersortkeys, - int outersize, int innersize, int outerwidth, int innerwidth); -extern Cost cost_hashjoin(Cost outercost, Cost innercost, - int outersize, int innersize, - int outerwidth, int innerwidth, - Cost innerdisbursion); -extern int compute_rel_size(RelOptInfo *rel); -extern int compute_rel_width(RelOptInfo *rel); -extern int compute_joinrel_size(JoinPath *joinpath); -extern int page_size(int tuples, int width); +extern Cost cost_seqscan(RelOptInfo *baserel); +extern Cost cost_index(RelOptInfo *baserel, IndexOptInfo *index, + long expected_indexpages, Selectivity selec, + bool is_injoin); +extern Cost cost_tidscan(RelOptInfo *baserel, List *tideval); +extern Cost cost_sort(List *pathkeys, double tuples, int width); +extern Cost cost_nestloop(Path *outer_path, Path *inner_path, + bool is_indexjoin); +extern Cost cost_mergejoin(Path *outer_path, Path *inner_path, + List *outersortkeys, List *innersortkeys); +extern Cost cost_hashjoin(Path *outer_path, Path *inner_path, + Selectivity innerdisbursion); +extern void set_rel_rows_width(Query *root, RelOptInfo *rel); +extern void set_joinrel_rows_width(Query *root, RelOptInfo *rel, + JoinPath *joinpath); /* - * prototypes for fuctions in clausesel.h + * prototypes for clausesel.c * routines to compute clause selectivities */ -extern void set_clause_selectivities(List *restrictinfo_list, Cost new_selectivity); -extern Cost product_selec(List *restrictinfo_list); -extern void set_rest_relselec(Query *root, List *rel_list); -extern void set_rest_selec(Query *root, List *restrictinfo_list); -extern Cost compute_clause_selec(Query *root, Node *clause); +extern Selectivity restrictlist_selec(Query *root, List *restrictinfo_list); +extern Selectivity clauselist_selec(Query *root, List *clauses); +extern Selectivity compute_clause_selec(Query *root, Node *clause); #endif /* COST_H */ diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index 2aca95e605..25781a3447 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -6,7 +6,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: pathnode.h,v 1.22 1999/11/23 20:07:06 momjian Exp $ + * $Id: pathnode.h,v 1.23 2000/01/09 00:26:47 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -21,26 +21,27 @@ extern bool path_is_cheaper(Path *path1, Path *path2); extern Path *set_cheapest(RelOptInfo *parent_rel, List *pathlist); extern List *add_pathlist(RelOptInfo *parent_rel, List *old_paths, - List *new_paths); + List *new_paths); extern Path *create_seqscan_path(RelOptInfo *rel); - extern IndexPath *create_index_path(Query *root, RelOptInfo *rel, - RelOptInfo *index, List *restriction_clauses); + IndexOptInfo *index, + List *restriction_clauses); extern TidPath *create_tidscan_path(RelOptInfo *rel, List *tideval); extern NestPath *create_nestloop_path(RelOptInfo *joinrel, - RelOptInfo *outer_rel, Path *outer_path, Path *inner_path, - List *pathkeys); - -extern MergePath *create_mergejoin_path(RelOptInfo *joinrel, int outersize, - int innersize, int outerwidth, int innerwidth, Path *outer_path, - Path *inner_path, List *pathkeys, - List *mergeclauses, List *outersortkeys, List *innersortkeys); - -extern HashPath *create_hashjoin_path(RelOptInfo *joinrel, int outersize, - int innersize, int outerwidth, int innerwidth, Path *outer_path, - Path *inner_path, List *hashclauses, Cost innerdisbursion); + Path *outer_path, Path *inner_path, + List *pathkeys); + +extern MergePath *create_mergejoin_path(RelOptInfo *joinrel, Path *outer_path, + Path *inner_path, List *pathkeys, + List *mergeclauses, + List *outersortkeys, + List *innersortkeys); + +extern HashPath *create_hashjoin_path(RelOptInfo *joinrel, Path *outer_path, + Path *inner_path, List *hashclauses, + Selectivity innerdisbursion); /* * prototypes for rel.c diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 92ce9f9719..a3f6bad36b 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -7,7 +7,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: paths.h,v 1.36 1999/11/23 20:07:06 momjian Exp $ + * $Id: paths.h,v 1.37 2000/01/09 00:26:47 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -28,6 +28,8 @@ extern RelOptInfo *make_one_rel(Query *root, List *rels); extern List *create_index_paths(Query *root, RelOptInfo *rel, List *indices, List *restrictinfo_list, List *joininfo_list); +extern Oid indexable_operator(Expr *clause, Oid opclass, Oid relam, + bool indexkey_on_left); extern List *expand_indexqual_conditions(List *indexquals); /* @@ -65,7 +67,7 @@ extern bool pathkeys_contained_in(List *keys1, List *keys2); extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, bool indexpaths_only); extern List *build_index_pathkeys(Query *root, RelOptInfo *rel, - RelOptInfo *index); + IndexOptInfo *index); extern List *build_join_pathkeys(List *outer_pathkeys, List *join_rel_tlist, List *joinclauses); extern bool commute_pathkeys(List *pathkeys); @@ -93,7 +95,7 @@ extern bool is_subset(List *s1, List *s2); * prototypes for path/prune.c */ extern void merge_rels_with_same_relids(List *rel_list); -extern void rels_set_cheapest(List *rel_list); +extern void rels_set_cheapest(Query *root, List *rel_list); extern List *del_rels_all_bushy_inactive(List *old_rels); #endif /* PATHS_H */ diff --git a/src/include/optimizer/plancat.h b/src/include/optimizer/plancat.h index 34c853d68f..307b51c3f4 100644 --- a/src/include/optimizer/plancat.h +++ b/src/include/optimizer/plancat.h @@ -6,36 +6,36 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: plancat.h,v 1.14 1999/11/21 23:25:42 tgl Exp $ + * $Id: plancat.h,v 1.15 2000/01/09 00:26:47 tgl Exp $ * *------------------------------------------------------------------------- */ #ifndef PLANCAT_H #define PLANCAT_H -#include "nodes/parsenodes.h" +#include "nodes/relation.h" extern void relation_info(Query *root, Index relid, - bool *hasindex, int *pages, int *tuples); + bool *hasindex, long *pages, double *tuples); extern List *find_secondary_indexes(Query *root, Index relid); -extern Cost restriction_selectivity(Oid functionObjectId, +extern List *find_inheritance_children(Oid inhparent); + +extern Selectivity restriction_selectivity(Oid functionObjectId, Oid operatorObjectId, Oid relationObjectId, AttrNumber attributeNumber, Datum constValue, int constFlag); -extern void index_selectivity(Query *root, int relid, Oid indexid, - List *indexquals, - float *idxPages, float *idxSelec); +extern void index_selectivity(Query *root, RelOptInfo *rel, + IndexOptInfo *index, List *indexquals, + long *idxPages, Selectivity *idxSelec); -extern Cost join_selectivity(Oid functionObjectId, Oid operatorObjectId, +extern Selectivity join_selectivity(Oid functionObjectId, Oid operatorObjectId, Oid relationObjectId1, AttrNumber attributeNumber1, Oid relationObjectId2, AttrNumber attributeNumber2); -extern List *find_inheritance_children(Oid inhparent); - #endif /* PLANCAT_H */ diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h index 8664fb9aaa..409559a696 100644 --- a/src/include/optimizer/planmain.h +++ b/src/include/optimizer/planmain.h @@ -6,7 +6,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: planmain.h,v 1.34 1999/10/07 04:23:19 tgl Exp $ + * $Id: planmain.h,v 1.35 2000/01/09 00:26:47 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -24,7 +24,7 @@ extern Plan *query_planner(Query *root, List *tlist, List *qual); /* * prototypes for plan/createplan.c */ -extern Plan *create_plan(Path *best_path); +extern Plan *create_plan(Query *root, Path *best_path); extern SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid); extern Sort *make_sort(List *tlist, Oid nonameid, Plan *lefttree, int keycount); @@ -41,7 +41,6 @@ extern Result *make_result(List *tlist, Node *resconstantqual, Plan *subplan); extern void make_var_only_tlist(Query *root, List *tlist); extern void add_restrict_and_join_to_rels(Query *root, List *clauses); extern void add_missing_rels_to_query(Query *root); -extern void set_joininfo_mergeable_hashable(List *rel_list); /* * prototypes for plan/setrefs.c -- 2.11.0