diff options
Diffstat (limited to 'src')
43 files changed, 1916 insertions, 3249 deletions
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c index ca2bd33a2c1..99b1c39c7e6 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.90 1999/08/09 06:20:23 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.91 1999/08/16 02:17:41 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -1030,10 +1030,6 @@ _copyRelOptInfo(RelOptInfo *from) newnode->indexkeys[len] = 0; } - newnode->relam = from->relam; - newnode->indproc = from->indproc; - Node_Copy(from, newnode, indpred); - if (from->ordering) { for (len = 0; from->ordering[len] != 0; len++) @@ -1044,6 +1040,10 @@ _copyRelOptInfo(RelOptInfo *from) newnode->ordering[len] = 0; } + newnode->relam = from->relam; + newnode->indproc = from->indproc; + Node_Copy(from, newnode, indpred); + Node_Copy(from, newnode, restrictinfo); Node_Copy(from, newnode, joininfo); Node_Copy(from, newnode, innerjoin); @@ -1061,8 +1061,6 @@ _copyRelOptInfo(RelOptInfo *from) static void CopyPathFields(Path *from, Path *newnode) { - newnode->pathtype = from->pathtype; - /* * Modify the next line, since it causes the copying to cycle (i.e. * the parent points right back here! -- JMH, 7/7/92. Old version: @@ -1072,32 +1070,9 @@ CopyPathFields(Path *from, Path *newnode) newnode->path_cost = from->path_cost; - newnode->pathorder = makeNode(PathOrder); - newnode->pathorder->ordtype = from->pathorder->ordtype; - if (from->pathorder->ordtype == SORTOP_ORDER) - { - int len, - i; - Oid *ordering = from->pathorder->ord.sortop; - - if (ordering) - { - for (len = 0; ordering[len] != 0; len++) - ; - newnode->pathorder->ord.sortop = (Oid *) palloc(sizeof(Oid) * (len + 1)); - for (i = 0; i < len; i++) - newnode->pathorder->ord.sortop[i] = ordering[i]; - newnode->pathorder->ord.sortop[len] = 0; - } - } - else - Node_Copy(from, newnode, pathorder->ord.merge); + newnode->pathtype = from->pathtype; Node_Copy(from, newnode, pathkeys); - - newnode->outerjoincost = from->outerjoincost; - - newnode->joinid = listCopy(from->joinid); } /* ---------------- @@ -1135,32 +1110,20 @@ _copyIndexPath(IndexPath *from) */ newnode->indexid = listCopy(from->indexid); Node_Copy(from, newnode, indexqual); - - if (from->indexkeys) - { - int i, - len; - - for (len = 0; from->indexkeys[len] != 0; len++) - ; - newnode->indexkeys = (int *) palloc(sizeof(int) * (len + 1)); - for (i = 0; i < len; i++) - newnode->indexkeys[i] = from->indexkeys[i]; - newnode->indexkeys[len] = 0; - } + newnode->joinrelids = listCopy(from->joinrelids); return newnode; } /* ---------------- - * CopyNestPathFields + * CopyJoinPathFields * - * This function copies the fields of the NestPath node. It is used by - * all the copy functions for classes which inherit from NestPath. + * This function copies the fields of the JoinPath node. It is used by + * all the copy functions for classes which inherit from JoinPath. * ---------------- */ static void -CopyNestPathFields(NestPath *from, NestPath *newnode) +CopyJoinPathFields(JoinPath *from, JoinPath *newnode) { Node_Copy(from, newnode, pathinfo); Node_Copy(from, newnode, outerjoinpath); @@ -1181,7 +1144,7 @@ _copyNestPath(NestPath *from) * ---------------- */ CopyPathFields((Path *) from, (Path *) newnode); - CopyNestPathFields(from, newnode); + CopyJoinPathFields((JoinPath *) from, (JoinPath *) newnode); return newnode; } @@ -1200,7 +1163,7 @@ _copyMergePath(MergePath *from) * ---------------- */ CopyPathFields((Path *) from, (Path *) newnode); - CopyNestPathFields((NestPath *) from, (NestPath *) newnode); + CopyJoinPathFields((JoinPath *) from, (JoinPath *) newnode); /* ---------------- * copy the remainder of the node @@ -1227,76 +1190,32 @@ _copyHashPath(HashPath *from) * ---------------- */ CopyPathFields((Path *) from, (Path *) newnode); - CopyNestPathFields((NestPath *) from, (NestPath *) newnode); + CopyJoinPathFields((JoinPath *) from, (JoinPath *) newnode); /* ---------------- * copy remainder of node * ---------------- */ Node_Copy(from, newnode, path_hashclauses); - Node_Copy(from, newnode, outerhashkeys); - Node_Copy(from, newnode, innerhashkeys); return newnode; } /* ---------------- - * _copyOrderKey + * _copyPathKeyItem * ---------------- */ -static OrderKey * -_copyOrderKey(OrderKey *from) +static PathKeyItem * +_copyPathKeyItem(PathKeyItem *from) { - OrderKey *newnode = makeNode(OrderKey); + PathKeyItem *newnode = makeNode(PathKeyItem); /* ---------------- * copy remainder of node * ---------------- */ - newnode->attribute_number = from->attribute_number; - newnode->array_index = from->array_index; - - return newnode; -} - - -/* ---------------- - * _copyJoinKey - * ---------------- - */ -static JoinKey * -_copyJoinKey(JoinKey *from) -{ - JoinKey *newnode = makeNode(JoinKey); - - /* ---------------- - * copy remainder of node - * ---------------- - */ - Node_Copy(from, newnode, outer); - Node_Copy(from, newnode, inner); - - return newnode; -} - -/* ---------------- - * _copyMergeOrder - * ---------------- - */ -static MergeOrder * -_copyMergeOrder(MergeOrder *from) -{ - MergeOrder *newnode = makeNode(MergeOrder); - - /* ---------------- - * copy remainder of node - * ---------------- - */ - newnode->join_operator = from->join_operator; - newnode->left_operator = from->left_operator; - newnode->right_operator = from->right_operator; - newnode->left_type = from->left_type; - newnode->right_type = from->right_type; + Node_Copy(from, newnode, key); + newnode->sortop = from->sortop; return newnode; } @@ -1315,84 +1234,17 @@ _copyRestrictInfo(RestrictInfo *from) * ---------------- */ Node_Copy(from, newnode, clause); - newnode->selectivity = from->selectivity; - - Node_Copy(from, newnode, indexids); - Node_Copy(from, newnode, mergejoinorder); + Node_Copy(from, newnode, subclauseindices); + newnode->mergejoinoperator = from->mergejoinoperator; + newnode->left_sortop = from->left_sortop; + newnode->right_sortop = from->right_sortop; newnode->hashjoinoperator = from->hashjoinoperator; return newnode; } /* ---------------- - * CopyJoinMethodFields - * - * This function copies the fields of the JoinMethod node. It is used by - * all the copy functions for classes which inherit from JoinMethod. - * ---------------- - */ -static void -CopyJoinMethodFields(JoinMethod *from, JoinMethod *newnode) -{ - Node_Copy(from, newnode, jmkeys); - Node_Copy(from, newnode, clauses); - return; -} - -/* ---------------- - * _copyJoinMethod - * ---------------- - */ -static JoinMethod * -_copyJoinMethod(JoinMethod *from) -{ - JoinMethod *newnode = makeNode(JoinMethod); - - CopyJoinMethodFields(from, newnode); - - return newnode; -} - -/* ---------------- - * _copyHashInfo - * ---------------- - */ -static HashInfo * -_copyHashInfo(HashInfo *from) -{ - HashInfo *newnode = makeNode(HashInfo); - - /* ---------------- - * copy remainder of node - * ---------------- - */ - CopyJoinMethodFields((JoinMethod *) from, (JoinMethod *) newnode); - newnode->hashop = from->hashop; - - return newnode; -} - -/* ---------------- - * _copyMergeInfo - * ---------------- - */ -static MergeInfo * -_copyMergeInfo(MergeInfo *from) -{ - MergeInfo *newnode = makeNode(MergeInfo); - - /* ---------------- - * copy remainder of node - * ---------------- - */ - CopyJoinMethodFields((JoinMethod *) from, (JoinMethod *) newnode); - Node_Copy(from, newnode, m_ordering); - - return newnode; -} - -/* ---------------- * _copyJoinInfo * ---------------- */ @@ -1408,9 +1260,6 @@ _copyJoinInfo(JoinInfo *from) newnode->unjoined_relids = listCopy(from->unjoined_relids); Node_Copy(from, newnode, jinfo_restrictinfo); - newnode->mergejoinable = from->mergejoinable; - newnode->hashjoinable = from->hashjoinable; - return newnode; } @@ -1756,27 +1605,12 @@ copyObject(void *from) case T_HashPath: retval = _copyHashPath(from); break; - case T_OrderKey: - retval = _copyOrderKey(from); - break; - case T_JoinKey: - retval = _copyJoinKey(from); - break; - case T_MergeOrder: - retval = _copyMergeOrder(from); + case T_PathKeyItem: + retval = _copyPathKeyItem(from); break; case T_RestrictInfo: retval = _copyRestrictInfo(from); break; - case T_JoinMethod: - retval = _copyJoinMethod(from); - break; - case T_HashInfo: - retval = _copyHashInfo(from); - break; - case T_MergeInfo: - retval = _copyMergeInfo(from); - break; case T_JoinInfo: retval = _copyJoinInfo(from); break; diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c index 337e63a6156..1c53fe6aede 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.46 1999/08/09 06:20:24 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v 1.47 1999/08/16 02:17:41 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -264,15 +264,15 @@ _equalRelOptInfo(RelOptInfo *a, RelOptInfo *b) /* We treat RelOptInfos as equal if they refer to the same base rels * joined in the same order. Is this sufficient? */ - return equal(a->relids, b->relids); + return equali(a->relids, b->relids); } static bool -_equalJoinMethod(JoinMethod *a, JoinMethod *b) +_equalPathKeyItem(PathKeyItem *a, PathKeyItem *b) { - if (!equal(a->jmkeys, b->jmkeys)) + if (a->sortop != b->sortop) return false; - if (!equal(a->clauses, b->clauses)) + if (!equal(a->key, b->key)) return false; return true; } @@ -282,48 +282,13 @@ _equalPath(Path *a, Path *b) { if (a->pathtype != b->pathtype) return false; - if (a->parent != b->parent) /* should this use equal() ? */ + if (!equal(a->parent, b->parent)) return false; /* do not check path_cost, since it may not be set yet, and being * a float there are roundoff error issues anyway... */ - - /* XXX this should probably be in an _equalPathOrder function... */ - if (a->pathorder->ordtype != b->pathorder->ordtype) - return false; - if (a->pathorder->ordtype == SORTOP_ORDER) - { - if (a->pathorder->ord.sortop == NULL || - b->pathorder->ord.sortop == NULL) - { - if (a->pathorder->ord.sortop != b->pathorder->ord.sortop) - return false; - } - else - { - int i = 0; - - while (a->pathorder->ord.sortop[i] != 0) - { - if (a->pathorder->ord.sortop[i] != b->pathorder->ord.sortop[i]) - return false; - i++; - } - if (b->pathorder->ord.sortop[i] != 0) - return false; - } - } - else - { - if (!equal(a->pathorder->ord.merge, b->pathorder->ord.merge)) - return false; - } - if (!equal(a->pathkeys, b->pathkeys)) return false; - /* do not check outerjoincost either */ - if (!equali(a->joinid, b->joinid)) - return false; return true; } @@ -336,12 +301,13 @@ _equalIndexPath(IndexPath *a, IndexPath *b) return false; if (!equal(a->indexqual, b->indexqual)) return false; - /* We do not need to check indexkeys */ + if (!equali(a->joinrelids, b->joinrelids)) + return false; return true; } static bool -_equalNestPath(NestPath *a, NestPath *b) +_equalJoinPath(JoinPath *a, JoinPath *b) { if (!_equalPath((Path *) a, (Path *) b)) return false; @@ -355,65 +321,33 @@ _equalNestPath(NestPath *a, NestPath *b) } static bool -_equalMergePath(MergePath *a, MergePath *b) -{ - if (!_equalNestPath((NestPath *) a, (NestPath *) b)) - return false; - if (!equal(a->path_mergeclauses, b->path_mergeclauses)) - return false; - if (!equal(a->outersortkeys, b->outersortkeys)) - return false; - if (!equal(a->innersortkeys, b->innersortkeys)) - return false; - return true; -} - -static bool -_equalHashPath(HashPath *a, HashPath *b) -{ - if (!_equalNestPath((NestPath *) a, (NestPath *) b)) - return false; - if (!equal(a->path_hashclauses, b->path_hashclauses)) - return false; - if (!equal(a->outerhashkeys, b->outerhashkeys)) - return false; - if (!equal(a->innerhashkeys, b->innerhashkeys)) - return false; - return true; -} - -static bool -_equalJoinKey(JoinKey *a, JoinKey *b) +_equalNestPath(NestPath *a, NestPath *b) { - if (!equal(a->outer, b->outer)) - return false; - if (!equal(a->inner, b->inner)) + if (!_equalJoinPath((JoinPath *) a, (JoinPath *) b)) return false; return true; } static bool -_equalMergeOrder(MergeOrder *a, MergeOrder *b) +_equalMergePath(MergePath *a, MergePath *b) { - if (a->join_operator != b->join_operator) - return false; - if (a->left_operator != b->left_operator) + if (!_equalJoinPath((JoinPath *) a, (JoinPath *) b)) return false; - if (a->right_operator != b->right_operator) + if (!equal(a->path_mergeclauses, b->path_mergeclauses)) return false; - if (a->left_type != b->left_type) + if (!equal(a->outersortkeys, b->outersortkeys)) return false; - if (a->right_type != b->right_type) + if (!equal(a->innersortkeys, b->innersortkeys)) return false; return true; } static bool -_equalHashInfo(HashInfo *a, HashInfo *b) +_equalHashPath(HashPath *a, HashPath *b) { - if (!_equalJoinMethod((JoinMethod *) a, (JoinMethod *) b)) + if (!_equalJoinPath((JoinPath *) a, (JoinPath *) b)) return false; - if (a->hashop != b->hashop) + if (!equal(a->path_hashclauses, b->path_hashclauses)) return false; return true; } @@ -458,30 +392,32 @@ _equalSubPlan(SubPlan *a, SubPlan *b) } static bool -_equalJoinInfo(JoinInfo *a, JoinInfo *b) +_equalRestrictInfo(RestrictInfo *a, RestrictInfo *b) { - if (!equal(a->unjoined_relids, b->unjoined_relids)) + if (!equal(a->clause, b->clause)) return false; - if (!equal(a->jinfo_restrictinfo, b->jinfo_restrictinfo)) + /* do not check selectivity because of roundoff error worries */ + if (!equal(a->subclauseindices, b->subclauseindices)) return false; - if (a->mergejoinable != b->mergejoinable) + if (a->mergejoinoperator != b->mergejoinoperator) return false; - if (a->hashjoinable != b->hashjoinable) + if (a->left_sortop != b->left_sortop) + return false; + if (a->right_sortop != b->right_sortop) + return false; + if (a->hashjoinoperator != b->hashjoinoperator) return false; return true; } static bool -_equalRestrictInfo(RestrictInfo *a, RestrictInfo *b) +_equalJoinInfo(JoinInfo *a, JoinInfo *b) { - if (!equal(a->clause, b->clause)) + if (!equali(a->unjoined_relids, b->unjoined_relids)) return false; - /* do not check selectivity because of roundoff error worries */ - if (!equal(a->mergejoinorder, b->mergejoinorder)) - return false; - if (a->hashjoinoperator != b->hashjoinoperator) + if (!equal(a->jinfo_restrictinfo, b->jinfo_restrictinfo)) return false; - return equal(a->indexids, b->indexids); + return true; } static bool @@ -778,8 +714,8 @@ equal(void *a, void *b) case T_RelOptInfo: retval = _equalRelOptInfo(a, b); break; - case T_JoinMethod: - retval = _equalJoinMethod(a, b); + case T_PathKeyItem: + retval = _equalPathKeyItem(a, b); break; case T_Path: retval = _equalPath(a, b); @@ -796,15 +732,6 @@ equal(void *a, void *b) case T_HashPath: retval = _equalHashPath(a, b); break; - case T_JoinKey: - retval = _equalJoinKey(a, b); - break; - case T_MergeOrder: - retval = _equalMergeOrder(a, b); - break; - case T_HashInfo: - retval = _equalHashInfo(a, b); - break; case T_IndexScan: retval = _equalIndexScan(a, b); break; diff --git a/src/backend/nodes/freefuncs.c b/src/backend/nodes/freefuncs.c index b06536d1977..11f92b28d05 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.24 1999/07/27 03:51:08 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/Attic/freefuncs.c,v 1.25 1999/08/16 02:17:42 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -706,6 +706,9 @@ _freeRelOptInfo(RelOptInfo *node) freeObject(node->targetlist); freeObject(node->pathlist); + /* is this right? cheapestpath will typically be a pointer into + * pathlist, won't it? + */ freeObject(node->cheapestpath); if (node->classlist) @@ -714,11 +717,11 @@ _freeRelOptInfo(RelOptInfo *node) if (node->indexkeys) pfree(node->indexkeys); - freeObject(node->indpred); - if (node->ordering) pfree(node->ordering); + freeObject(node->indpred); + freeObject(node->restrictinfo); freeObject(node->joininfo); freeObject(node->innerjoin); @@ -736,20 +739,9 @@ _freeRelOptInfo(RelOptInfo *node) static void FreePathFields(Path *node) { - if (node->pathorder->ordtype == SORTOP_ORDER) - { - if (node->pathorder->ord.sortop) - pfree(node->pathorder->ord.sortop); - } - else - freeObject(node->pathorder->ord.merge); - - pfree(node->pathorder); /* is it an object, but we don't have - * separate free for it */ + /* we do NOT free the parent; it doesn't belong to the Path */ freeObject(node->pathkeys); - - freeList(node->joinid); } /* ---------------- @@ -783,22 +775,20 @@ _freeIndexPath(IndexPath *node) */ freeList(node->indexid); freeObject(node->indexqual); - - if (node->indexkeys) - pfree(node->indexkeys); + freeList(node->joinrelids); pfree(node); } /* ---------------- - * FreeNestPathFields + * FreeJoinPathFields * - * This function frees the fields of the NestPath node. It is used by - * all the free functions for classes which inherit node NestPath. + * This function frees the fields of the JoinPath node. It is used by + * all the free functions for classes which inherit node JoinPath. * ---------------- */ static void -FreeNestPathFields(NestPath *node) +FreeJoinPathFields(JoinPath *node) { freeObject(node->pathinfo); freeObject(node->outerjoinpath); @@ -817,7 +807,7 @@ _freeNestPath(NestPath *node) * ---------------- */ FreePathFields((Path *) node); - FreeNestPathFields(node); + FreeJoinPathFields((JoinPath *) node); pfree(node); } @@ -834,7 +824,7 @@ _freeMergePath(MergePath *node) * ---------------- */ FreePathFields((Path *) node); - FreeNestPathFields((NestPath *) node); + FreeJoinPathFields((JoinPath *) node); /* ---------------- * free the remainder of the node @@ -859,60 +849,33 @@ _freeHashPath(HashPath *node) * ---------------- */ FreePathFields((Path *) node); - FreeNestPathFields((NestPath *) node); + FreeJoinPathFields((JoinPath *) node); /* ---------------- * free remainder of node * ---------------- */ freeObject(node->path_hashclauses); - freeObject(node->outerhashkeys); - freeObject(node->innerhashkeys); - - pfree(node); -} -/* ---------------- - * _freeOrderKey - * ---------------- - */ -static void -_freeOrderKey(OrderKey *node) -{ pfree(node); } - /* ---------------- - * _freeJoinKey + * _freePathKeyItem * ---------------- */ static void -_freeJoinKey(JoinKey *node) +_freePathKeyItem(PathKeyItem *node) { /* ---------------- * free remainder of node * ---------------- */ - freeObject(node->outer); - freeObject(node->inner); + freeObject(node->key); pfree(node); } -/* ---------------- - * _freeMergeOrder - * ---------------- - */ -static void -_freeMergeOrder(MergeOrder *node) -{ - /* ---------------- - * free remainder of node - * ---------------- - */ - pfree(node); -} /* ---------------- * _freeRestrictInfo @@ -926,68 +889,10 @@ _freeRestrictInfo(RestrictInfo *node) * ---------------- */ freeObject(node->clause); - freeObject(node->indexids); - freeObject(node->mergejoinorder); - - pfree(node); -} - -/* ---------------- - * FreeJoinMethodFields - * - * This function frees the fields of the JoinMethod node. It is used by - * all the free functions for classes which inherit node JoinMethod. - * ---------------- - */ -static void -FreeJoinMethodFields(JoinMethod *node) -{ - freeObject(node->jmkeys); - freeObject(node->clauses); - return; -} - -/* ---------------- - * _freeJoinMethod - * ---------------- - */ -static void -_freeJoinMethod(JoinMethod *node) -{ - FreeJoinMethodFields(node); - - pfree(node); -} - -/* ---------------- - * _freeHInfo - * ---------------- - */ -static void -_freeHashInfo(HashInfo *node) -{ - /* ---------------- - * free remainder of node - * ---------------- - */ - FreeJoinMethodFields((JoinMethod *) node); - - pfree(node); -} - -/* ---------------- - * _freeMInfo - * ---------------- - */ -static void -_freeMergeInfo(MergeInfo *node) -{ - /* ---------------- - * free remainder of node - * ---------------- + /* this is certainly wrong? index RelOptInfos don't belong to + * RestrictInfo... */ - FreeJoinMethodFields((JoinMethod *) node); - freeObject(node->m_ordering); + freeObject(node->subclauseindices); pfree(node); } @@ -1279,27 +1184,12 @@ freeObject(void *node) case T_HashPath: _freeHashPath(node); break; - case T_OrderKey: - _freeOrderKey(node); - break; - case T_JoinKey: - _freeJoinKey(node); - break; - case T_MergeOrder: - _freeMergeOrder(node); + case T_PathKeyItem: + _freePathKeyItem(node); break; case T_RestrictInfo: _freeRestrictInfo(node); break; - case T_JoinMethod: - _freeJoinMethod(node); - break; - case T_HashInfo: - _freeHashInfo(node); - break; - case T_MergeInfo: - _freeMergeInfo(node); - break; case T_JoinInfo: _freeJoinInfo(node); break; diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c index 87dd3b6562b..f814047af43 100644 --- a/src/backend/nodes/list.c +++ b/src/backend/nodes/list.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/nodes/list.c,v 1.26 1999/08/14 19:29:35 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/list.c,v 1.27 1999/08/16 02:17:42 tgl Exp $ * * NOTES * XXX a few of the following functions are duplicated to handle @@ -448,6 +448,31 @@ intLispRemove(int elem, List *list) #endif /* + * ltruncate + * Truncate a list to n elements. + * Does nothing if n >= length(list). + * NB: the list is modified in-place! + */ +List * +ltruncate(int n, List *list) +{ + List *ptr; + + if (n <= 0) + return NIL; /* truncate to zero length */ + + foreach(ptr, list) + { + if (--n == 0) + { + lnext(ptr) = NIL; + break; + } + } + return list; +} + +/* * set_difference * * Return l1 without the elements in l2. diff --git a/src/backend/nodes/nodes.c b/src/backend/nodes/nodes.c index 0e60597949d..b1ebcf53ff2 100644 --- a/src/backend/nodes/nodes.c +++ b/src/backend/nodes/nodes.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/nodes/nodes.c,v 1.10 1999/07/17 20:17:07 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/nodes.c,v 1.11 1999/08/16 02:17:42 tgl Exp $ * * HISTORY * Andrew Yu Oct 20, 1994 file creation @@ -32,7 +32,7 @@ newNode(Size size, NodeTag tag) { Node *newNode; - Assert(size >= 4); /* need the tag, at least */ + Assert(size >= sizeof(Node)); /* need the tag, at least */ newNode = (Node *) palloc(size); MemSet((char *) newNode, 0, size); diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index 5c9f4599deb..39b0625d933 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.92 1999/08/09 06:20:24 momjian Exp $ + * $Id: outfuncs.c,v 1.93 1999/08/16 02:17:42 tgl Exp $ * * NOTES * Every (plan) node in POSTGRES has an associated "out" routine which @@ -884,44 +884,12 @@ _outRowMark(StringInfo str, RowMark *node) * Path is a subclass of Node. */ static void -_outPathOrder(StringInfo str, PathOrder *node) -{ - appendStringInfo(str, " PATHORDER :ordtype %d ", - node->ordtype); - if (node->ordtype == SORTOP_ORDER) - { - int i; - - appendStringInfo(str, " :sortop "); - if (node->ord.sortop == NULL) - appendStringInfo(str, "<>"); - else - { - for (i = 0; node->ord.sortop[i] != 0; i++) - appendStringInfo(str, " %d ", node->ord.sortop[i]); - appendStringInfo(str, " %d ", 0); - } - } - else - { - appendStringInfo(str, " :merge "); - _outNode(str, node->ord.merge); - } -} - -/* - * Path is a subclass of Node. - */ -static void _outPath(StringInfo str, Path *node) { appendStringInfo(str, " PATH :pathtype %d :cost %f :pathkeys ", node->pathtype, node->path_cost); _outNode(str, node->pathkeys); - - appendStringInfo(str, " :pathorder "); - _outNode(str, node->pathorder); } /* @@ -936,14 +904,14 @@ _outIndexPath(StringInfo str, IndexPath *node) node->path.path_cost); _outNode(str, node->path.pathkeys); - appendStringInfo(str, " :pathorder "); - _outNode(str, node->path.pathorder); - appendStringInfo(str, " :indexid "); _outIntList(str, node->indexid); appendStringInfo(str, " :indexqual "); _outNode(str, node->indexqual); + + appendStringInfo(str, " :joinrelids "); + _outIntList(str, node->joinrelids); } /* @@ -958,9 +926,6 @@ _outNestPath(StringInfo str, NestPath *node) node->path.path_cost); _outNode(str, node->path.pathkeys); - appendStringInfo(str, " :pathorder "); - _outNode(str, node->path.pathorder); - appendStringInfo(str, " :pathinfo "); _outNode(str, node->pathinfo); @@ -970,11 +935,9 @@ _outNestPath(StringInfo str, NestPath *node) */ appendStringInfo(str, - " :outerjoinpath @ 0x%x :innerjoinpath @ 0x%x :outjoincost %f :joinid ", + " :outerjoinpath @ 0x%x :innerjoinpath @ 0x%x ", (int) node->outerjoinpath, - (int) node->innerjoinpath, - node->path.outerjoincost); - _outIntList(str, node->path.joinid); + (int) node->innerjoinpath); } /* @@ -989,9 +952,6 @@ _outMergePath(StringInfo str, MergePath *node) node->jpath.path.path_cost); _outNode(str, node->jpath.path.pathkeys); - appendStringInfo(str, " :pathorder "); - _outNode(str, node->jpath.path.pathorder); - appendStringInfo(str, " :pathinfo "); _outNode(str, node->jpath.pathinfo); @@ -1001,11 +961,9 @@ _outMergePath(StringInfo str, MergePath *node) */ appendStringInfo(str, - " :outerjoinpath @ 0x%x :innerjoinpath @ 0x%x :outerjoincost %f :joinid ", + " :outerjoinpath @ 0x%x :innerjoinpath @ 0x%x ", (int) node->jpath.outerjoinpath, - (int) node->jpath.innerjoinpath, - (int) node->jpath.path.outerjoincost); - _outIntList(str, node->jpath.path.joinid); + (int) node->jpath.innerjoinpath); appendStringInfo(str, " :path_mergeclauses "); _outNode(str, node->path_mergeclauses); @@ -1029,9 +987,6 @@ _outHashPath(StringInfo str, HashPath *node) node->jpath.path.path_cost); _outNode(str, node->jpath.path.pathkeys); - appendStringInfo(str, " :pathorder "); - _outNode(str, node->jpath.path.pathorder); - appendStringInfo(str, " :pathinfo "); _outNode(str, node->jpath.pathinfo); @@ -1041,64 +996,23 @@ _outHashPath(StringInfo str, HashPath *node) */ appendStringInfo(str, - " :outerjoinpath @ 0x%x :innerjoinpath @ 0x%x :outerjoincost %f :joinid ", + " :outerjoinpath @ 0x%x :innerjoinpath @ 0x%x ", (int) node->jpath.outerjoinpath, - (int) node->jpath.innerjoinpath, - node->jpath.path.outerjoincost); - _outIntList(str, node->jpath.path.joinid); + (int) node->jpath.innerjoinpath); appendStringInfo(str, " :path_hashclauses "); _outNode(str, node->path_hashclauses); - - appendStringInfo(str, " :outerhashkeys "); - _outNode(str, node->outerhashkeys); - - appendStringInfo(str, " :innerhashkeys "); - _outNode(str, node->innerhashkeys); -} - -/* - * OrderKey is a subclass of Node. - */ -static void -_outOrderKey(StringInfo str, OrderKey *node) -{ - appendStringInfo(str, - " ORDERKEY :attribute_number %d :array_index %d ", - node->attribute_number, - node->array_index); -} - -/* - * JoinKey is a subclass of Node. - */ -static void -_outJoinKey(StringInfo str, JoinKey *node) -{ - appendStringInfo(str, " JOINKEY :outer "); - _outNode(str, node->outer); - - appendStringInfo(str, " :inner "); - _outNode(str, node->inner); - } /* - * MergeOrder is a subclass of Node. + * PathKeyItem is a subclass of Node. */ static void -_outMergeOrder(StringInfo str, MergeOrder *node) +_outPathKeyItem(StringInfo str, PathKeyItem *node) { - appendStringInfo(str, - " MERGEORDER :join_operator %u :left_operator %u :right_operator %u ", - node->join_operator, - node->left_operator, - node->right_operator); - - appendStringInfo(str, - " :left_type %u :right_type %u ", - node->left_type, - node->right_type); + appendStringInfo(str, " PATHKEYITEM :sortop %u :key ", + node->sortop); + _outNode(str, node->key); } /* @@ -1111,41 +1025,14 @@ _outRestrictInfo(StringInfo str, RestrictInfo *node) _outNode(str, node->clause); appendStringInfo(str, - " :selectivity %f :indexids ", + " :selectivity %f :subclauseindices ", node->selectivity); - _outNode(str, node->indexids); - - appendStringInfo(str, " :mergejoinorder "); - _outNode(str, node->mergejoinorder); + _outNode(str, node->subclauseindices); + appendStringInfo(str, " :mergejoinoperator %u ", node->mergejoinoperator); + appendStringInfo(str, " :left_sortop %u ", node->left_sortop); + appendStringInfo(str, " :right_sortop %u ", node->right_sortop); appendStringInfo(str, " :hashjoinoperator %u ", node->hashjoinoperator); - -} - -/* - * JoinMethod is a subclass of Node. - */ -static void -_outJoinMethod(StringInfo str, JoinMethod *node) -{ - appendStringInfo(str, " JOINMETHOD :jmkeys "); - _outNode(str, node->jmkeys); - - appendStringInfo(str, " :clauses "); - _outNode(str, node->clauses); -} - -/* - * HashInfo is a subclass of JoinMethod. - */ -static void -_outHashInfo(StringInfo str, HashInfo *node) -{ - appendStringInfo(str, " HASHINFO :hashop %u :jmkeys ", node->hashop); - _outNode(str, node->jmethod.jmkeys); - - appendStringInfo(str, " :clauses "); - _outNode(str, node->jmethod.clauses); } /* @@ -1159,10 +1046,6 @@ _outJoinInfo(StringInfo str, JoinInfo *node) appendStringInfo(str, " :jinfo_restrictinfo "); _outNode(str, node->jinfo_restrictinfo); - - appendStringInfo(str, " :mergejoinable %s :hashjoinable %s ", - node->mergejoinable ? "true" : "false", - node->hashjoinable ? "true" : "false"); } /* @@ -1541,9 +1424,6 @@ _outNode(StringInfo str, void *obj) case T_RowMark: _outRowMark(str, obj); break; - case T_PathOrder: - _outPathOrder(str, obj); - break; case T_Path: _outPath(str, obj); break; @@ -1559,24 +1439,12 @@ _outNode(StringInfo str, void *obj) case T_HashPath: _outHashPath(str, obj); break; - case T_OrderKey: - _outOrderKey(str, obj); - break; - case T_JoinKey: - _outJoinKey(str, obj); - break; - case T_MergeOrder: - _outMergeOrder(str, obj); + case T_PathKeyItem: + _outPathKeyItem(str, obj); break; case T_RestrictInfo: _outRestrictInfo(str, obj); break; - case T_JoinMethod: - _outJoinMethod(str, obj); - break; - case T_HashInfo: - _outHashInfo(str, obj); - break; case T_JoinInfo: _outJoinInfo(str, obj); break; diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c index 995e226c163..9cb04181cde 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.31 1999/07/17 20:17:08 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/print.c,v 1.32 1999/08/16 02:17:43 tgl Exp $ * * HISTORY * AUTHOR DATE MAJOR EVENT @@ -204,7 +204,7 @@ print_expr(Node *expr, List *rtable) /* * print_pathkeys - - * pathkeys list of list of Var's + * pathkeys list of list of PathKeyItems */ void print_pathkeys(List *pathkeys, List *rtable) @@ -220,9 +220,9 @@ print_pathkeys(List *pathkeys, List *rtable) printf("("); foreach(k, pathkey) { - Node *var = lfirst(k); + PathKeyItem *item = lfirst(k); - print_expr(var, rtable); + print_expr(item->key, rtable); if (lnext(k)) printf(", "); } diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c index c49ad053f1b..98385dd96f6 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.71 1999/08/09 06:20:24 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/readfuncs.c,v 1.72 1999/08/16 02:17:43 tgl Exp $ * * NOTES * Most of the read functions for plan nodes are tested. (In fact, they @@ -1414,55 +1414,6 @@ _readRowMark() } /* ---------------- - * _readPathOrder - * - * PathOrder is part of Path and it's subclasses. - * ---------------- - */ -static PathOrder * -_readPathOrder() -{ - PathOrder *local_node; - char *token; - int length; - - local_node = makeNode(PathOrder); - - token = lsptok(NULL, &length); /* get :ordtype */ - token = lsptok(NULL, &length); /* now read it */ - local_node->ordtype = atol(token); - - if (local_node->ordtype == SORTOP_ORDER) - { - token = lsptok(NULL, &length); /* get :sortop */ - - if (length == 0) - local_node->ord.sortop = NULL; - else - { - int i = -1; - - local_node->ord.sortop = palloc(sizeof(Oid) * (INDEX_MAX_KEYS + 1)); - - do - { - i++; - Assert(i <= INDEX_MAX_KEYS); - token = lsptok(NULL, &length); /* now read it */ - local_node->ord.sortop[i] = strtoul(token, NULL, 10); - } while (local_node->ord.sortop[i] != 0); - } - } - else - { - token = lsptok(NULL, &length); /* get :merge */ - local_node->ord.merge = nodeRead(true); /* now read it */ - } - - return local_node; -} - -/* ---------------- * _readPath * * Path is a subclass of Node. @@ -1485,9 +1436,6 @@ _readPath() token = lsptok(NULL, &length); /* now read it */ local_node->path_cost = (Cost) atof(token); - token = lsptok(NULL, &length); /* get :pathorder */ - local_node->pathorder = nodeRead(true); /* now read it */ - token = lsptok(NULL, &length); /* get :pathkeys */ local_node->pathkeys = nodeRead(true); /* now read it */ @@ -1517,9 +1465,6 @@ _readIndexPath() token = lsptok(NULL, &length); /* now read it */ local_node->path.path_cost = (Cost) atof(token); - token = lsptok(NULL, &length); /* get :pathorder */ - local_node->path.pathorder = nodeRead(true); /* now read it */ - token = lsptok(NULL, &length); /* get :pathkeys */ local_node->path.pathkeys = nodeRead(true); /* now read it */ @@ -1529,6 +1474,9 @@ _readIndexPath() token = lsptok(NULL, &length); /* get :indexqual */ local_node->indexqual = nodeRead(true); /* now read it */ + token = lsptok(NULL, &length); /* get :joinrelids */ + local_node->joinrelids = toIntList(nodeRead(true)); + return local_node; } @@ -1545,7 +1493,6 @@ _readNestPath() char *token; int length; - local_node = makeNode(NestPath); token = lsptok(NULL, &length); /* get :pathtype */ @@ -1556,9 +1503,6 @@ _readNestPath() token = lsptok(NULL, &length); /* now read it */ local_node->path.path_cost = (Cost) atof(token); - token = lsptok(NULL, &length); /* get :pathorder */ - local_node->path.pathorder = nodeRead(true); /* now read it */ - token = lsptok(NULL, &length); /* get :pathkeys */ local_node->path.pathkeys = nodeRead(true); /* now read it */ @@ -1585,14 +1529,6 @@ _readNestPath() local_node->innerjoinpath = NULL; - token = lsptok(NULL, &length); /* get :outerjoincost */ - token = lsptok(NULL, &length); /* now read it */ - - local_node->path.outerjoincost = (Cost) atof(token); - - token = lsptok(NULL, &length); /* get :joinid */ - local_node->path.joinid = toIntList(nodeRead(true)); /* now read it */ - return local_node; } @@ -1621,9 +1557,6 @@ _readMergePath() local_node->jpath.path.path_cost = (Cost) atof(token); - token = lsptok(NULL, &length); /* get :pathorder */ - local_node->jpath.path.pathorder = nodeRead(true); /* now read it */ - token = lsptok(NULL, &length); /* get :pathkeys */ local_node->jpath.path.pathkeys = nodeRead(true); /* now read it */ @@ -1650,14 +1583,6 @@ _readMergePath() local_node->jpath.innerjoinpath = NULL; - token = lsptok(NULL, &length); /* get :outerjoincost */ - token = lsptok(NULL, &length); /* now read it */ - - local_node->jpath.path.outerjoincost = (Cost) atof(token); - - token = lsptok(NULL, &length); /* get :joinid */ - local_node->jpath.path.joinid = toIntList(nodeRead(true)); /* now read it */ - token = lsptok(NULL, &length); /* get :path_mergeclauses */ local_node->path_mergeclauses = nodeRead(true); /* now read it */ @@ -1695,9 +1620,6 @@ _readHashPath() local_node->jpath.path.path_cost = (Cost) atof(token); - token = lsptok(NULL, &length); /* get :pathorder */ - local_node->jpath.path.pathorder = nodeRead(true); /* now read it */ - token = lsptok(NULL, &length); /* get :pathkeys */ local_node->jpath.path.pathkeys = nodeRead(true); /* now read it */ @@ -1724,116 +1646,34 @@ _readHashPath() local_node->jpath.innerjoinpath = NULL; - token = lsptok(NULL, &length); /* get :outerjoincost */ - token = lsptok(NULL, &length); /* now read it */ - - local_node->jpath.path.outerjoincost = (Cost) atof(token); - - token = lsptok(NULL, &length); /* get :joinid */ - local_node->jpath.path.joinid = toIntList(nodeRead(true)); /* now read it */ - token = lsptok(NULL, &length); /* get :path_hashclauses */ local_node->path_hashclauses = nodeRead(true); /* now read it */ - token = lsptok(NULL, &length); /* get :outerhashkeys */ - local_node->outerhashkeys = nodeRead(true); /* now read it */ - - token = lsptok(NULL, &length); /* get :innerhashkeys */ - local_node->innerhashkeys = nodeRead(true); /* now read it */ - - return local_node; -} - -/* ---------------- - * _readOrderKey - * - * OrderKey is a subclass of Node. - * ---------------- - */ -static OrderKey * -_readOrderKey() -{ - OrderKey *local_node; - char *token; - int length; - - local_node = makeNode(OrderKey); - - token = lsptok(NULL, &length); /* get :attribute_number */ - token = lsptok(NULL, &length); /* now read it */ - - local_node->attribute_number = atoi(token); - - token = lsptok(NULL, &length); /* get :array_index */ - token = lsptok(NULL, &length); /* now read it */ - - local_node->array_index = strtoul(token, NULL, 10); - - return local_node; -} - -/* ---------------- - * _readJoinKey - * - * JoinKey is a subclass of Node. - * ---------------- - */ -static JoinKey * -_readJoinKey() -{ - JoinKey *local_node; - char *token; - int length; - - local_node = makeNode(JoinKey); - - token = lsptok(NULL, &length); /* get :outer */ - local_node->outer = nodeRead(true); /* now read it */ - - token = lsptok(NULL, &length); /* get :inner */ - local_node->inner = nodeRead(true); /* now read it */ - return local_node; } /* ---------------- - * _readMergeOrder + * _readPathKeyItem * - * MergeOrder is a subclass of Node. + * PathKeyItem is a subclass of Node. * ---------------- */ -static MergeOrder * -_readMergeOrder() +static PathKeyItem * +_readPathKeyItem() { - MergeOrder *local_node; + PathKeyItem *local_node; char *token; int length; - local_node = makeNode(MergeOrder); - token = lsptok(NULL, &length); /* get :join_operator */ - token = lsptok(NULL, &length); /* now read it */ - - local_node->join_operator = atol(token); + local_node = makeNode(PathKeyItem); - token = lsptok(NULL, &length); /* get :left_operator */ + token = lsptok(NULL, &length); /* get :sortop */ token = lsptok(NULL, &length); /* now read it */ - local_node->left_operator = atol(token); - - token = lsptok(NULL, &length); /* get :right_operator */ - token = lsptok(NULL, &length); /* now read it */ + local_node->sortop = atol(token); - local_node->right_operator = atol(token); - - token = lsptok(NULL, &length); /* get :left_type */ - token = lsptok(NULL, &length); /* now read it */ - - local_node->left_type = atol(token); - - token = lsptok(NULL, &length); /* get :right_type */ - token = lsptok(NULL, &length); /* now read it */ - - local_node->right_type = atol(token); + token = lsptok(NULL, &length); /* get :key */ + local_node->key = nodeRead(true); /* now read it */ return local_node; } @@ -1858,72 +1698,26 @@ _readRestrictInfo() token = lsptok(NULL, &length); /* get :selectivity */ token = lsptok(NULL, &length); /* now read it */ - local_node->selectivity = atof(token); - token = lsptok(NULL, &length); /* get :indexids */ - local_node->indexids = nodeRead(true); /* now read it */ + token = lsptok(NULL, &length); /* get :subclauseindices */ + local_node->subclauseindices = nodeRead(true); /* now read it */ - token = lsptok(NULL, &length); /* get :mergejoinorder */ - local_node->mergejoinorder = (MergeOrder *) nodeRead(true); - - token = lsptok(NULL, &length); /* get :hashjoinoperator */ + token = lsptok(NULL, &length); /* get :mergejoinoperator */ token = lsptok(NULL, &length); /* now read it */ + local_node->mergejoinoperator = atol(token); - local_node->hashjoinoperator = atol(token); - - return local_node; -} - -/* ---------------- - * _readJoinMethod - * - * JoinMethod is a subclass of Node. - * ---------------- - */ -static JoinMethod * -_readJoinMethod() -{ - JoinMethod *local_node; - char *token; - int length; - - local_node = makeNode(JoinMethod); - - token = lsptok(NULL, &length); /* get :jmkeys */ - local_node->jmkeys = nodeRead(true); /* now read it */ - - token = lsptok(NULL, &length); /* get :clauses */ - local_node->clauses = nodeRead(true); /* now read it */ - - return local_node; -} - -/* ---------------- - * _readHashInfo - * - * HashInfo is a subclass of JoinMethod. - * ---------------- - */ -static HashInfo * -_readHashInfo() -{ - HashInfo *local_node; - char *token; - int length; - - local_node = makeNode(HashInfo); - - token = lsptok(NULL, &length); /* get :hashop */ + token = lsptok(NULL, &length); /* get :left_sortop */ token = lsptok(NULL, &length); /* now read it */ + local_node->left_sortop = atol(token); - local_node->hashop = strtoul(token, NULL, 10); - - token = lsptok(NULL, &length); /* get :jmkeys */ - local_node->jmethod.jmkeys = nodeRead(true); /* now read it */ + token = lsptok(NULL, &length); /* get :right_sortop */ + token = lsptok(NULL, &length); /* now read it */ + local_node->right_sortop = atol(token); - token = lsptok(NULL, &length); /* get :clauses */ - local_node->jmethod.clauses = nodeRead(true); /* now read it */ + token = lsptok(NULL, &length); /* get :hashjoinoperator */ + token = lsptok(NULL, &length); /* now read it */ + local_node->hashjoinoperator = atol(token); return local_node; } @@ -1949,20 +1743,6 @@ _readJoinInfo() token = lsptok(NULL, &length); /* get :jinfo_restrictinfo */ local_node->jinfo_restrictinfo = nodeRead(true); /* now read it */ - token = lsptok(NULL, &length); /* get :mergejoinable */ - - if (!strncmp(token, "true", 4)) - local_node->mergejoinable = true; - else - local_node->mergejoinable = false; - - token = lsptok(NULL, &length); /* get :hashjoinable */ - - if (!strncmp(token, "true", 4)) - local_node->hashjoinable = true; - else - local_node->hashjoinable = false; - return local_node; } @@ -2065,8 +1845,6 @@ parsePlanString(void) return_value = _readTargetEntry(); else if (!strncmp(token, "RTE", length)) return_value = _readRangeTblEntry(); - else if (!strncmp(token, "PATHORDER", length)) - return_value = _readPathOrder(); else if (!strncmp(token, "PATH", length)) return_value = _readPath(); else if (!strncmp(token, "INDEXPATH", length)) @@ -2077,20 +1855,12 @@ parsePlanString(void) return_value = _readMergePath(); else if (!strncmp(token, "HASHPATH", length)) return_value = _readHashPath(); - else if (!strncmp(token, "ORDERKEY", length)) - return_value = _readOrderKey(); - else if (!strncmp(token, "JOINKEY", length)) - return_value = _readJoinKey(); - else if (!strncmp(token, "MERGEORDER", length)) - return_value = _readMergeOrder(); - else if (!strncmp(token, "RETRICTINFO", length)) + else if (!strncmp(token, "PATHKEYITEM", length)) + return_value = _readPathKeyItem(); + else if (!strncmp(token, "RESTRICTINFO", length)) return_value = _readRestrictInfo(); - else if (!strncmp(token, "JOINMETHOD", length)) - return_value = _readJoinMethod(); else if (!strncmp(token, "JOININFO", length)) return_value = _readJoinInfo(); - else if (!strncmp(token, "HASHINFO", length)) - return_value = _readHashInfo(); else if (!strncmp(token, "ITER", length)) return_value = _readIter(); else if (!strncmp(token, "QUERY", length)) diff --git a/src/backend/optimizer/README b/src/backend/optimizer/README index b25d7fb5f1a..20a4e477428 100644 --- a/src/backend/optimizer/README +++ b/src/backend/optimizer/README @@ -1,37 +1,63 @@ Summary ------- -The optimizer generates optimial query plans by doing several steps: - -1) Take each relation in a query, and make a RelOptInfo structure for -it. Find each way of accessing the relation, called a Path, including -sequential and index scans, and add it to RelOptInfo.pathlist. Also -create RelOptInfo.joininfo that lists all the joins that involve this -relation. For example, the WHERE clause "tab1.col1 = tab2.col1" -generates a JoinInfo for tab1 listing tab2 as an unjoined relation, and -tab2's joininfo shows tab1 as an unjoined relation. - -2) Join each RelOptInfo to other RelOptInfo as specified in -RelOptInfo.joininfo. At this point each RelOptInfo is a single -relation, so you are joining every relation to the other relations as -joined in the WHERE clause. - -Joins occur using two RelOptInfos. One is outer, the other inner. -Outers drive lookups of values in the inner. In a nested loop, lookups -of values in the inner occur by scanning to find each matching inner -row. In a mergejoin, inner and outer rows are ordered, and are accessed -in order, so only one scan of inner is required to perform the entire -join. In a hashjoin, inner rows are hashed for lookups. - -Each unique join combination becomes a new RelOptInfo. The RelOptInfo -is now the joining of two relations. RelOptInfo.pathlist are various -paths to create the joined result, having different orderings depending -on the join method used. - -3) At this point, every RelOptInfo is joined to each other again, with -a new relation added to each RelOptInfo. This continues until all -relations have been joined into one RelOptInfo, and the cheapest Path is -chosen. +The optimizer generates optimal query plans by doing a more-or-less +exhaustive search through the ways of executing the query. During +the planning/optimizing process, we build "Path" trees representing +the different ways of doing a query. We select the cheapest Path +that generates the desired relation and turn it into a Plan to pass +to the executor. (There is pretty much a one-to-one correspondence +between the Path and Plan trees, but Path nodes omit info that won't +be needed during planning, and include info needed for planning that +won't be needed by the executor.) + +The best Path tree is found by a recursive process: + +1) Take each base relation in the query, and make a RelOptInfo structure +for it. Find each potentially useful way of accessing the relation, +including sequential and index scans, and make a Path representing that +way. All the Paths made for a given relation are placed in its +RelOptInfo.pathlist. (Actually, we discard Paths that are obviously +inferior alternatives before they ever get into the pathlist --- what +ends up in the pathlist is the cheapest way of generating each potentially +useful sort ordering of the relation.) Also create RelOptInfo.joininfo +nodes that list all the joins that involve this relation. For example, +the WHERE clause "tab1.col1 = tab2.col1" generates a JoinInfo for tab1 +listing tab2 as an unjoined relation, and also one for tab2 showing tab1 +as an unjoined relation. + +2) Consider joining each RelOptInfo to each other RelOptInfo specified in +its RelOptInfo.joininfo, and generate a Path for each possible join method. +At this stage each input RelOptInfo is a single relation, so we are joining +every relation to the other relations as joined in the WHERE clause. We +generate a new "join" RelOptInfo for each possible combination of two +"base" RelOptInfos, and put all the plausible paths for that combination +into the join RelOptInfo's pathlist. (As before, we keep only the cheapest +alternative that generates any one sort ordering of the result.) + +Joins always occur using two RelOptInfos. One is outer, the other inner. +Outers drive lookups of values in the inner. In a nested loop, lookups of +values in the inner occur by scanning the inner path once per outer tuple +to find each matching inner row. In a mergejoin, inner and outer rows are +ordered, and are accessed in order, so only one scan is required to perform +the entire join: both inner and outer paths are scanned in-sync. (There's +not a lot of difference between inner and outer in a mergejoin...) In a +hashjoin, the inner is scanned first and all its rows are entered in a +hashtable, then the outer is scanned and for each row we lookup the join +key in the hashtable. + +A Path for a join relation is actually a tree structure, with the top +Path node representing the join method. It has left and right subpaths +that represent the scan methods used for the two input relations. + +3) If we only had two base relations, we are done: we just pick the +cheapest path for the join RelOptInfo. If we had more than two, we now +need to consider ways of joining join RelOptInfos to each other to make +join RelOptInfos that represent more than two base relations. This process +is repeated until we have finally built a RelOptInfo that represents all +the base relations in the query. Then we pick its cheapest Path. + +For example: SELECT * FROM tab1, tab2, tab3, tab4 @@ -67,8 +93,11 @@ Optimizer Functions These directories take the Query structure returned by the parser, and generate a plan used by the executor. The /plan directory generates the -plan, the /path generates all possible ways to join the tables, and -/prep handles special cases like inheritance. /utils is utility stuff. +actual output plan, the /path code generates all possible ways to join the +tables, and /prep handles special cases like inheritance. /util is utility +stuff. /geqo is the separate "genetic optimization" planner --- it does +a semi-random search rather than exhaustively considering all possible +join trees. planner() handle inheritance by processing separately @@ -136,8 +165,8 @@ planner() -Optimizer Structures --------------------- +Optimizer Data Structures +------------------------- RelOptInfo - a relation or joined relations @@ -145,9 +174,39 @@ RelOptInfo - a relation or joined relations JoinInfo - join clauses, including the relids needed for the join Path - every way to generate a RelOptInfo(sequential,index,joins) + SeqScan - a plain Path node with nodeTag = T_SeqScan IndexPath - index scans - NestPath - nested joins + NestPath - nested-loop joins MergePath - merge joins HashPath - hash joins - PathOrder - every ordering type (sort, merge of relations) + PathKeys - a data structure representing the ordering of a path + +The optimizer spends a good deal of its time worrying about the ordering +of the tuples returned by a path. The reason this is useful is that by +knowing the sort ordering of a path, we may be able to use that path as +the left or right input of a mergejoin and avoid an explicit sort step. +Nestloops and hash joins don't really care what the order of their inputs +is, but mergejoin needs suitably ordered inputs. Therefore, all paths +generated during the optimization process are marked with their sort order +(to the extent that it is known) for possible use by a higher-level merge. + +It is also possible to avoid an explicit sort step to implement a user's +ORDER BY clause if the final path has the right ordering already. +Currently, this is not very well implemented: we avoid generating a +redundant sort if the chosen path has the desired order, but we do not do +anything to encourage the selection of such a path --- so we only avoid the +sort if the path that would be chosen anyway (because it is cheapest +without regard to its ordering) is properly sorted. The path winnowing +process needs to be aware of the desired output order and account for the +cost of doing an explicit sort while it is choosing the best path. + +When we are generating paths for a particular RelOptInfo, we discard a path +if it is more expensive than another known path that has the same or better +sort order. We will never discard a path that is the only known way to +achieve a given sort order. In this way, the next level up will have the +maximum freedom to build mergejoins without sorting, since it can pick from +any of the paths retained for its inputs. + +See path/pathkeys.c for an explanation of the PathKeys data structure that +represents what is known about the sort order of a particular Path. diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c index 31ffdb14d48..fd9c2fb1ae4 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.42 1999/07/16 04:59:08 momjian Exp $ + * $Id: geqo_eval.c,v 1.43 1999/08/16 02:17:48 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -23,9 +23,6 @@ #include "postgres.h" #ifdef HAVE_LIMITS_H #include <limits.h> -#ifndef MAXINT -#define MAXINT INT_MAX -#endif #else #include <values.h> #endif diff --git a/src/backend/optimizer/geqo/geqo_misc.c b/src/backend/optimizer/geqo/geqo_misc.c index 615c4354611..db55aadcfce 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.23 1999/07/17 20:17:09 momjian Exp $ + * $Id: geqo_misc.c,v 1.24 1999/08/16 02:17:48 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -21,7 +21,10 @@ #include "postgres.h" + #include "optimizer/geqo_misc.h" +#include "nodes/print.h" + static float avg_pool(Pool *pool); @@ -213,32 +216,14 @@ geqo_print_path(Query *root, Path *path, int indent) int size = path->parent->size; int relid = lfirsti(path->parent->relids); - printf("%s(%d) size=%d cost=%f", + printf("%s(%d) size=%d cost=%f\n", ptype, relid, size, path->path_cost); - if (nodeTag(path) == T_IndexPath) + if (IsA(path, IndexPath)) { - List *k, - *l; - - printf(" pathkeys="); - foreach(k, path->pathkeys) - { - printf("("); - foreach(l, lfirst(k)) - { - Var *var = lfirst(l); - - printf("%d.%d", var->varnoold, var->varoattno); - if (lnext(l)) - printf(", "); - } - printf(")"); - if (lnext(k)) - printf(", "); - } + printf(" pathkeys="); + print_pathkeys(path->pathkeys, root->rtable); } - printf("\n"); } } diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile index 7db01b05aea..cdc401b8310 100644 --- a/src/backend/optimizer/path/Makefile +++ b/src/backend/optimizer/path/Makefile @@ -4,7 +4,7 @@ # Makefile for optimizer/path # # IDENTIFICATION -# $Header: /cvsroot/pgsql/src/backend/optimizer/path/Makefile,v 1.8 1999/02/20 15:27:42 momjian Exp $ +# $Header: /cvsroot/pgsql/src/backend/optimizer/path/Makefile,v 1.9 1999/08/16 02:17:50 tgl Exp $ # #------------------------------------------------------------------------- @@ -13,8 +13,8 @@ include ../../../Makefile.global CFLAGS += -I../.. -OBJS = allpaths.o clausesel.o costsize.o hashutils.o indxpath.o \ - joinpath.o joinrels.o mergeutils.o orindxpath.o pathkeys.o prune.o +OBJS = allpaths.o clausesel.o costsize.o indxpath.o \ + joinpath.o joinrels.o orindxpath.o pathkeys.o prune.o all: SUBSYS.o diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 6e59451e558..23c759bd6e6 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.52 1999/07/30 22:34:17 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.53 1999/08/16 02:17:50 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -331,32 +331,14 @@ print_path(Query *root, Path *path, int indent) int size = path->parent->size; int relid = lfirsti(path->parent->relids); - printf("%s(%d) size=%d cost=%f", + printf("%s(%d) size=%d cost=%f\n", ptype, relid, size, path->path_cost); - if (nodeTag(path) == T_IndexPath) + if (IsA(path, IndexPath)) { - List *k, - *l; - - printf(" pathkeys="); - foreach(k, path->pathkeys) - { - printf("("); - foreach(l, lfirst(k)) - { - Var *var = lfirst(l); - - printf("%d.%d", var->varnoold, var->varoattno); - if (lnext(l)) - printf(", "); - } - printf(")"); - if (lnext(k)) - printf(", "); - } + printf(" pathkeys="); + print_pathkeys(path->pathkeys, root->rtable); } - printf("\n"); } } diff --git a/src/backend/optimizer/path/hashutils.c b/src/backend/optimizer/path/hashutils.c deleted file mode 100644 index d6456af6da3..00000000000 --- a/src/backend/optimizer/path/hashutils.c +++ /dev/null @@ -1,118 +0,0 @@ -/*------------------------------------------------------------------------- - * - * hashutils.c - * Utilities for finding applicable merge clauses and pathkeys - * - * Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/hashutils.c,v 1.18 1999/07/16 04:59:14 momjian Exp $ - * - *------------------------------------------------------------------------- - */ -#include "postgres.h" - -#include "optimizer/clauses.h" -#include "optimizer/paths.h" - - -static HashInfo *match_hashop_hashinfo(Oid hashop, List *hashinfo_list); - -/* - * group_clauses_by_hashop - * If a join clause node in 'restrictinfo_list' is hashjoinable, store - * it within a hashinfo node containing other clause nodes with the same - * hash operator. - * - * 'restrictinfo_list' is the list of restrictinfo nodes - * 'inner_relids' is the list of relids in the inner join relation - * (used to determine whether a join var is inner or outer) - * - * Returns the new list of hashinfo nodes. - * - */ -List * -group_clauses_by_hashop(List *restrictinfo_list, - Relids inner_relids) -{ - List *hashinfo_list = NIL; - RestrictInfo *restrictinfo; - List *i; - Oid hashjoinop; - - foreach(i, restrictinfo_list) - { - restrictinfo = (RestrictInfo *) lfirst(i); - hashjoinop = restrictinfo->hashjoinoperator; - - /* - * Create a new hashinfo node and add it to 'hashinfo_list' if one - * does not yet exist for this hash operator. - */ - if (hashjoinop) - { - Expr *clause = restrictinfo->clause; - Var *leftop = get_leftop(clause); - Var *rightop = get_rightop(clause); - HashInfo *xhashinfo; - JoinKey *joinkey; - - xhashinfo = match_hashop_hashinfo(hashjoinop, hashinfo_list); - joinkey = makeNode(JoinKey); - if (intMember(leftop->varno, inner_relids)) - { - joinkey->outer = rightop; - joinkey->inner = leftop; - } - else - { - joinkey->outer = leftop; - joinkey->inner = rightop; - } - - if (xhashinfo == NULL) - { - xhashinfo = makeNode(HashInfo); - xhashinfo->hashop = hashjoinop; - xhashinfo->jmethod.jmkeys = NIL; - xhashinfo->jmethod.clauses = NIL; - hashinfo_list = lcons(xhashinfo, hashinfo_list); - } - - xhashinfo->jmethod.clauses = lcons(clause, - xhashinfo->jmethod.clauses); - xhashinfo->jmethod.jmkeys = lcons(joinkey, - xhashinfo->jmethod.jmkeys); - } - } - return hashinfo_list; -} - - -/* - * match_hashop_hashinfo - * Searches the list 'hashinfo_list' for a hashinfo node whose hash op - * field equals 'hashop'. - * - * Returns the node if it exists. - * - */ -static HashInfo * -match_hashop_hashinfo(Oid hashop, List *hashinfo_list) -{ - Oid key = 0; - HashInfo *xhashinfo = (HashInfo *) NULL; - List *i = NIL; - - foreach(i, hashinfo_list) - { - xhashinfo = (HashInfo *) lfirst(i); - key = xhashinfo->hashop; - if (hashop == key) - { /* found */ - return xhashinfo; /* should be a hashinfo node ! */ - } - } - return (HashInfo *) NIL; -} diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 01e663b255b..99ce241fed1 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.68 1999/08/12 04:32:51 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.69 1999/08/16 02:17:50 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -27,8 +27,6 @@ #include "nodes/nodeFuncs.h" #include "optimizer/clauses.h" #include "optimizer/cost.h" -#include "optimizer/keys.h" -#include "optimizer/ordering.h" #include "optimizer/pathnode.h" #include "optimizer/paths.h" #include "optimizer/plancat.h" @@ -70,7 +68,8 @@ static void indexable_joinclauses(RelOptInfo *rel, RelOptInfo *index, List **clausegroups, List **outerrelids); static List *index_innerjoin(Query *root, RelOptInfo *rel, RelOptInfo *index, List *clausegroup_list, List *outerrelids_list); -static bool useful_for_mergejoin(RelOptInfo *index, List *clausegroup_list); +static bool useful_for_mergejoin(RelOptInfo *rel, RelOptInfo *index, + List *joininfo_list); static bool match_index_to_operand(int indexkey, Var *operand, RelOptInfo *rel, RelOptInfo *index); static bool function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index); @@ -189,36 +188,34 @@ create_index_paths(Query *root, restrictclauses)); /* - * 3. If this index can be used with any join clause, then create - * an index path for it even if there were no restriction clauses. + * 3. If this index can be used for a mergejoin, then create an + * index path for it even if there were no restriction clauses. * (If there were, there is no need to make another index path.) * This will allow the index to be considered as a base for a * mergejoin in later processing. - * Also, create an innerjoin index path for each combination of + */ + if (restrictclauses == NIL && + useful_for_mergejoin(rel, index, joininfo_list)) + { + retval = lappend(retval, + create_index_path(root, rel, index, NIL)); + } + + /* + * 4. Create an innerjoin index path for each combination of * other rels used in available join clauses. These paths will * be considered as the inner side of nestloop joins against - * those sets of other rels. - * indexable_joinclauses() finds clauses that are potentially - * applicable to either case. useful_for_mergejoin() tests to - * see whether any of the join clauses might support a mergejoin. - * index_innerjoin() builds an innerjoin index path for each - * potential set of outer rels, which we add to the rel's - * innerjoin list. + * those sets of other rels. indexable_joinclauses() finds sets + * of clauses that can be used with each combination of outer rels, + * and index_innerjoin builds the paths themselves. We add the + * paths to the rel's innerjoin list, NOT to the result list. */ indexable_joinclauses(rel, index, joininfo_list, restrictinfo_list, &joinclausegroups, &joinouterrelids); - if (joinclausegroups != NIL) { - /* no need to create a plain path if we already did */ - if (restrictclauses == NIL && - useful_for_mergejoin(index, joinclausegroups)) - retval = lappend(retval, - create_index_path(root, rel, index, - NIL)); - rel->innerjoin = nconc(rel->innerjoin, index_innerjoin(root, rel, index, joinclausegroups, @@ -272,11 +269,11 @@ match_index_orclauses(RelOptInfo *rel, * Add this index to the subclause index list for each * subclause that it matches. */ - restrictinfo->indexids = + restrictinfo->subclauseindices = match_index_orclause(rel, index, indexkey, xclass, restrictinfo->clause->args, - restrictinfo->indexids); + restrictinfo->subclauseindices); } } } @@ -439,7 +436,8 @@ group_clauses_by_indexkey(RelOptInfo *rel, /* * group_clauses_by_ikey_for_joins - * Generates a list of join clauses that can be used with an index. + * Generates a list of join clauses that can be used with an index + * to scan the inner side of a nestloop join. * * This is much like group_clauses_by_indexkey(), but we consider both * join and restriction clauses. For each indexkey in the index, we @@ -447,7 +445,7 @@ group_clauses_by_indexkey(RelOptInfo *rel, * will make useful indexquals if the index is being used to scan the * inner side of a nestloop join. But there must be at least one matching * join clause, or we return NIL indicating that this index isn't useful - * for joining. + * for nestloop joining. */ static List * group_clauses_by_ikey_for_joins(RelOptInfo *rel, @@ -1156,7 +1154,7 @@ clause_pred_clause_test(Expr *predicate, Node *clause) /* * indexable_joinclauses * Finds all groups of join clauses from among 'joininfo_list' that can - * be used in conjunction with 'index'. + * be used in conjunction with 'index' for the inner scan of a nestjoin. * * Each clause group comes from a single joininfo node plus the current * rel's restrictinfo list. Therefore, every clause in the group references @@ -1224,7 +1222,7 @@ indexable_joinclauses(RelOptInfo *rel, RelOptInfo *index, * 'rel' is the relation for which 'index' is defined * 'clausegroup_list' is a list of lists of restrictinfo nodes which can use * 'index'. Each sublist refers to the same set of outer rels. - * 'outerrelids_list' is a list of the required outer rels for each group + * 'outerrelids_list' is a list of the required outer rels for each sublist * of join clauses. * * Returns a list of index pathnodes. @@ -1255,14 +1253,11 @@ index_innerjoin(Query *root, RelOptInfo *rel, RelOptInfo *index, &npages, &selec); - /* XXX this code ought to be merged with create_index_path */ + /* XXX this code ought to be merged with create_index_path? */ pathnode->path.pathtype = T_IndexScan; pathnode->path.parent = rel; - pathnode->path.pathorder = makeNode(PathOrder); - pathnode->path.pathorder->ordtype = SORTOP_ORDER; - pathnode->path.pathorder->ord.sortop = index->ordering; - pathnode->path.pathkeys = NIL; + pathnode->path.pathkeys = build_index_pathkeys(root, rel, index); /* Note that we are making a pathnode for a single-scan indexscan; * therefore, both indexid and indexqual should be single-element @@ -1272,10 +1267,8 @@ index_innerjoin(Query *root, RelOptInfo *rel, RelOptInfo *index, pathnode->indexid = index->relids; pathnode->indexqual = lcons(indexquals, NIL); - pathnode->indexkeys = index->indexkeys; - - /* joinid saves the rels needed on the outer side of the join */ - pathnode->path.joinid = lfirst(outerrelids_list); + /* 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, @@ -1295,33 +1288,53 @@ index_innerjoin(Query *root, RelOptInfo *rel, RelOptInfo *index, /* * useful_for_mergejoin * Determine whether the given index can support a mergejoin based - * on any join clause within the given list. The clauses have already - * been found to be relevant to the index by indexable_joinclauses. - * We just need to check whether any are mergejoin material. + * on any available join clause. * - * 'index' is the index of interest. - * 'clausegroup_list' is a list of clause groups (sublists of restrictinfo - * nodes) + * We look to see whether the first indexkey of the index matches the + * left or right sides of any of the mergejoinable clauses and provides + * the ordering needed for that side. If so, the index is useful. + * Matching a second or later indexkey is not useful unless there is + * also a mergeclause for the first indexkey, so we need not consider + * secondary indexkeys at this stage. + * + * 'rel' is the relation for which 'index' is defined + * 'joininfo_list' is the list of JoinInfo nodes for 'rel' */ static bool -useful_for_mergejoin(RelOptInfo *index, - List *clausegroup_list) +useful_for_mergejoin(RelOptInfo *rel, + RelOptInfo *index, + List *joininfo_list) { + int *indexkeys = index->indexkeys; + Oid *ordering = index->ordering; List *i; - foreach(i, clausegroup_list) + if (!indexkeys || indexkeys[0] == 0 || + !ordering || ordering[0] == InvalidOid) + return false; /* unordered index is not useful */ + + foreach(i, joininfo_list) { - List *clausegroup = lfirst(i); + JoinInfo *joininfo = (JoinInfo *) lfirst(i); List *j; - foreach(j, clausegroup) + foreach(j, joininfo->jinfo_restrictinfo) { RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j); - if (is_joinable((Node *) restrictinfo->clause) && - equal_path_merge_ordering(index->ordering, - restrictinfo->mergejoinorder)) - return true; + if (restrictinfo->mergejoinoperator) + { + if (restrictinfo->left_sortop == ordering[0] && + match_index_to_operand(indexkeys[0], + get_leftop(restrictinfo->clause), + rel, index)) + return true; + if (restrictinfo->right_sortop == ordering[0] && + match_index_to_operand(indexkeys[0], + get_rightop(restrictinfo->clause), + rel, index)) + return true; + } } } return false; @@ -1348,7 +1361,12 @@ match_index_to_operand(int indexkey, /* * Normal index. */ - return match_indexkey_operand(indexkey, operand, rel); + if (IsA(operand, Var) && + lfirsti(rel->relids) == operand->varno && + indexkey == operand->varattno) + return true; + else + return false; } /* @@ -1384,7 +1402,7 @@ function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index) /* * Check that the arguments correspond to the same arguments used to * create the functional index. To do this we must check that 1. - * refer to the right relatiion. 2. the args have the right attr. + * refer to the right relation. 2. the args have the right attr. * numbers in the right order. */ i = 0; @@ -1402,6 +1420,9 @@ function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index) i++; } + if (indexKeys[i] != 0) + return false; /* not enough arguments */ + return true; } diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c index 4a7018aa64a..55891d87a95 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.44 1999/08/09 03:16:43 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.45 1999/08/16 02:17:51 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -22,20 +22,26 @@ #include "optimizer/cost.h" #include "optimizer/pathnode.h" #include "optimizer/paths.h" +#include "optimizer/restrictinfo.h" #include "parser/parsetree.h" #include "utils/lsyscache.h" static Path *best_innerjoin(List *join_paths, List *outer_relid); -static List *sort_inner_and_outer(RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, - List *mergeinfo_list); -static List *match_unsorted_outer(RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, - List *outerpath_list, Path *cheapest_inner, Path *best_innerjoin, - List *mergeinfo_list); -static List *match_unsorted_inner(RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, - List *innerpath_list, List *mergeinfo_list); +static List *sort_inner_and_outer(RelOptInfo *joinrel, + RelOptInfo *outerrel, + RelOptInfo *innerrel, + List *mergeclause_list); +static List *match_unsorted_outer(RelOptInfo *joinrel, RelOptInfo *outerrel, + RelOptInfo *innerrel, List *outerpath_list, + Path *cheapest_inner, Path *best_innerjoin, + List *mergeclause_list); +static List *match_unsorted_inner(RelOptInfo *joinrel, RelOptInfo *outerrel, + RelOptInfo *innerrel, List *innerpath_list, + 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 List *select_mergejoin_clauses(List *restrictinfo_list); /* * update_rels_pathlist_for_joins @@ -43,19 +49,10 @@ static Cost estimate_disbursion(Query *root, Var *var); * relations in the list 'joinrels.' Each unique path will be included * in the join relation's 'pathlist' field. * - * In postgres, n-way joins are handled left-only(permuting clauseless - * joins doesn't usually win much). - * - * if BushyPlanFlag is true, bushy tree plans will be generated - * * 'joinrels' is the list of relation entries to be joined * * Modifies the pathlist field of each joinrel node to contain * the unique join paths. - * If bushy trees are considered, may modify the relid field of the - * join rel nodes to flatten the lists. - * - * It does a destructive modification. */ void update_rels_pathlist_for_joins(Query *root, List *joinrels) @@ -70,8 +67,8 @@ update_rels_pathlist_for_joins(Query *root, List *joinrels) RelOptInfo *innerrel; RelOptInfo *outerrel; Path *bestinnerjoin; - List *pathlist = NIL; - List *mergeinfo_list = NIL; + List *pathlist; + List *mergeclause_list = NIL; /* * On entry, joinrel->relids is a list of two sublists of relids, @@ -98,24 +95,26 @@ update_rels_pathlist_for_joins(Query *root, List *joinrels) get_join_rel(root, outerrelids); /* - * Get the best inner join for match_unsorted_outer. + * Get the best inner join for match_unsorted_outer(). */ bestinnerjoin = best_innerjoin(innerrel->innerjoin, outerrel->relids); + /* + * Find potential mergejoin clauses. + */ if (_enable_mergejoin_) - mergeinfo_list = group_clauses_by_order(joinrel->restrictinfo, - innerrel->relids); + mergeclause_list = select_mergejoin_clauses(joinrel->restrictinfo); /* * 1. Consider mergejoin paths where both relations must be * explicitly sorted. */ pathlist = sort_inner_and_outer(joinrel, outerrel, - innerrel, mergeinfo_list); + innerrel, mergeclause_list); /* * 2. Consider paths where the outer relation need not be - * explicitly sorted. This may include either nestloops and + * explicitly sorted. This includes both nestloops and * mergejoins where the outer path is already ordered. */ pathlist = add_pathlist(joinrel, pathlist, @@ -123,21 +122,20 @@ update_rels_pathlist_for_joins(Query *root, List *joinrels) outerrel, innerrel, outerrel->pathlist, - innerrel->cheapestpath, + innerrel->cheapestpath, bestinnerjoin, - mergeinfo_list)); + mergeclause_list)); /* * 3. Consider paths where the inner relation need not be - * explicitly sorted. This may include nestloops and mergejoins - * the actual nestloop nodes were constructed in - * (match_unsorted_outer). + * explicitly sorted. This includes mergejoins only + * (nestloops were already built in match_unsorted_outer). */ pathlist = add_pathlist(joinrel, pathlist, match_unsorted_inner(joinrel, outerrel, innerrel, innerrel->pathlist, - mergeinfo_list)); + mergeclause_list)); /* * 4. Consider paths where both outer and inner relations must be @@ -176,11 +174,13 @@ best_innerjoin(List *join_paths, Relids outer_relids) { Path *path = (Path *) lfirst(join_path); - /* path->joinid is the set of base rels that must be part of + Assert(IsA(path, IndexPath)); + + /* path->joinrelids is the set of base rels that must be part of * outer_relids in order to use this inner path, because those * rels are used in the index join quals of this inner path. */ - if (is_subset(path->joinid, outer_relids) && + if (is_subset(((IndexPath *) path)->joinrelids, outer_relids) && (cheapest == NULL || path_is_cheaper(path, cheapest))) cheapest = path; @@ -196,8 +196,8 @@ best_innerjoin(List *join_paths, Relids outer_relids) * 'joinrel' is the join relation * 'outerrel' is the outer join relation * 'innerrel' is the inner join relation - * 'mergeinfo_list' is a list of nodes containing info on(mergejoinable) - * clauses for joining the relations + * 'mergeclause_list' is a list of RestrictInfo nodes for available + * mergejoin clauses between these two relations * * Returns a list of mergejoin paths. */ @@ -205,32 +205,59 @@ static List * sort_inner_and_outer(RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, - List *mergeinfo_list) + List *mergeclause_list) { - List *ms_list = NIL; - MergeInfo *xmergeinfo = (MergeInfo *) NULL; - MergePath *temp_node = (MergePath *) NULL; + List *path_list = NIL; List *i; - List *outerkeys = NIL; - List *innerkeys = NIL; - List *merge_pathkeys = NIL; - foreach(i, mergeinfo_list) + /* + * Each possible ordering of the available mergejoin clauses will + * generate a differently-sorted result path at essentially the + * same cost. We have no basis for choosing one over another at + * this level of joining, but some sort orders may be more useful + * than others for higher-level mergejoins. Generating a path here + * for *every* permutation of mergejoin clauses doesn't seem like + * a winning strategy, however; the cost in planning time is too high. + * + * For now, we generate one path for each mergejoin clause, listing that + * clause first and the rest in random order. This should allow at least + * a one-clause mergejoin without re-sorting against any other possible + * mergejoin partner path. But if we've not guessed the right ordering + * of secondary clauses, we may end up evaluating clauses as qpquals when + * they could have been done as mergeclauses. We need to figure out a + * better way. (Two possible approaches: look at all the relevant index + * relations to suggest plausible sort orders, or make just one output + * path and somehow mark it as having a sort-order that can be rearranged + * freely.) + */ + foreach(i, mergeclause_list) { - xmergeinfo = (MergeInfo *) lfirst(i); - - outerkeys = make_pathkeys_from_joinkeys(xmergeinfo->jmethod.jmkeys, - outerrel->targetlist, - OUTER); - - innerkeys = make_pathkeys_from_joinkeys(xmergeinfo->jmethod.jmkeys, - innerrel->targetlist, - INNER); - - merge_pathkeys = new_join_pathkeys(outerkeys, joinrel->targetlist, - xmergeinfo->jmethod.clauses); - - temp_node = create_mergejoin_path(joinrel, + RestrictInfo *restrictinfo = lfirst(i); + List *curclause_list; + List *outerkeys; + List *innerkeys; + List *merge_pathkeys; + MergePath *path_node; + + /* Make a mergeclause list with this guy first. */ + curclause_list = lcons(restrictinfo, + lremove(restrictinfo, + listCopy(mergeclause_list))); + /* Build sort pathkeys for both sides. + * + * Note: it's possible that the cheapest path will already be + * sorted properly --- create_mergejoin_path will detect that case + * and suppress an explicit sort step. + */ + outerkeys = make_pathkeys_for_mergeclauses(curclause_list, + outerrel->targetlist); + innerkeys = make_pathkeys_for_mergeclauses(curclause_list, + innerrel->targetlist); + /* Build pathkeys representing output sort order. */ + merge_pathkeys = build_join_pathkeys(outerkeys, joinrel->targetlist, + curclause_list); + /* And now we can make the path. */ + path_node = create_mergejoin_path(joinrel, outerrel->size, innerrel->size, outerrel->width, @@ -238,40 +265,50 @@ sort_inner_and_outer(RelOptInfo *joinrel, (Path *) outerrel->cheapestpath, (Path *) innerrel->cheapestpath, merge_pathkeys, - xmergeinfo->m_ordering, - xmergeinfo->jmethod.clauses, + get_actual_clauses(curclause_list), outerkeys, innerkeys); - ms_list = lappend(ms_list, temp_node); + path_list = lappend(path_list, path_node); } - return ms_list; + return path_list; } /* * match_unsorted_outer * Creates possible join paths for processing a single join relation * 'joinrel' by employing either iterative substitution or - * mergejoining on each of its possible outer paths(assuming that the - * outer relation need not be explicitly sorted). + * mergejoining on each of its possible outer paths (considering + * only outer paths that are already ordered well enough for merging). * - * 1. The inner path is the cheapest available inner path. - * 2. Mergejoin wherever possible. Mergejoin are considered if there - * are mergejoinable join clauses between the outer and inner join - * relations such that the outer path is keyed on the variables - * appearing in the clauses. The corresponding inner merge path is - * either a path whose keys match those of the outer path(if such a - * path is available) or an explicit sort on the appropriate inner - * join keys, whichever is cheaper. + * We always generate a nestloop path for each available outer path. + * If an indexscan inner path exists that is compatible with this outer rel + * and cheaper than the cheapest general-purpose inner path, then we use + * the indexscan inner path; else we use the cheapest general-purpose inner. + * + * We also consider mergejoins if mergejoin clauses are available. We have + * two ways to generate the inner path for a mergejoin: use the cheapest + * inner path (sorting it if it's not suitably ordered already), or using an + * inner path that is already suitably ordered for the merge. If the + * cheapest inner path is suitably ordered, then by definition it's the one + * to use. Otherwise, we look for ordered paths that are cheaper than the + * cheapest inner + sort costs. If we have several mergeclauses, it could be + * that there is no inner path (or only a very expensive one) for the full + * list of mergeclauses, but better paths exist if we truncate the + * mergeclause list (thereby discarding some sort key requirements). So, we + * consider truncations of the mergeclause list as well as the full list. + * In any case, we find the cheapest suitable path and generate a single + * output mergejoin path. (Since all the possible mergejoins will have + * identical output pathkeys, there is no need to keep any but the cheapest.) * * 'joinrel' is the join relation * 'outerrel' is the outer join relation * 'innerrel' is the inner join relation * 'outerpath_list' is the list of possible outer paths * 'cheapest_inner' is the cheapest inner path - * 'best_innerjoin' is the best inner index path(if any) - * 'mergeinfo_list' is a list of nodes containing info on mergejoinable - * clauses + * 'best_innerjoin' is the best inner index path (if any) + * 'mergeclause_list' is a list of RestrictInfo nodes for available + * mergejoin clauses between these two relations * * Returns a list of possible join path nodes. */ @@ -282,139 +319,139 @@ match_unsorted_outer(RelOptInfo *joinrel, List *outerpath_list, Path *cheapest_inner, Path *best_innerjoin, - List *mergeinfo_list) + List *mergeclause_list) { - Path *outerpath = (Path *) NULL; - List *jp_list = NIL; - List *temp_node = NIL; - List *merge_pathkeys = NIL; - Path *nestinnerpath = (Path *) NULL; - List *paths = NIL; - List *i = NIL; - PathOrder *outerpath_ordering = NULL; + List *path_list = NIL; + Path *nestinnerpath; + List *i; + + /* + * We only use the best innerjoin indexpath if it is cheaper + * than the cheapest general-purpose inner path. + */ + if (best_innerjoin && + path_is_cheaper(best_innerjoin, cheapest_inner)) + nestinnerpath = best_innerjoin; + else + nestinnerpath = cheapest_inner; foreach(i, outerpath_list) { - List *clauses = NIL; - List *matchedJoinKeys = NIL; - List *matchedJoinClauses = NIL; - MergeInfo *xmergeinfo = NULL; - - outerpath = (Path *) lfirst(i); - - outerpath_ordering = outerpath->pathorder; - - if (outerpath_ordering) - xmergeinfo = match_order_mergeinfo(outerpath_ordering, - mergeinfo_list); - - if (xmergeinfo) - clauses = xmergeinfo->jmethod.clauses; - - if (clauses) + Path *outerpath = (Path *) lfirst(i); + List *mergeclauses; + List *merge_pathkeys; + List *innersortkeys; + Path *mergeinnerpath; + int mergeclausecount; + + /* Look for useful mergeclauses (if any) */ + mergeclauses = find_mergeclauses_for_pathkeys(outerpath->pathkeys, + mergeclause_list); + /* + * The result will have this sort order (even if it is implemented + * as a nestloop, and even if some of the mergeclauses are implemented + * by qpquals rather than as true mergeclauses): + */ + merge_pathkeys = build_join_pathkeys(outerpath->pathkeys, + joinrel->targetlist, + mergeclauses); + + /* 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)); + + /* Done with this outer path if no chance for a mergejoin */ + if (mergeclauses == NIL) + continue; + + /* Compute the required ordering of the inner path */ + innersortkeys = make_pathkeys_for_mergeclauses(mergeclauses, + innerrel->targetlist); + + /* Set up on the assumption that we will use the cheapest_inner */ + mergeinnerpath = cheapest_inner; + mergeclausecount = length(mergeclauses); + + /* If the cheapest_inner doesn't need to be sorted, it is the winner + * by definition. + */ + if (pathkeys_contained_in(innersortkeys, + cheapest_inner->pathkeys)) { - List *jmkeys = xmergeinfo->jmethod.jmkeys; - - order_joinkeys_by_pathkeys(outerpath->pathkeys, - jmkeys, - clauses, - OUTER, - &matchedJoinKeys, - &matchedJoinClauses); - merge_pathkeys = new_join_pathkeys(outerpath->pathkeys, - joinrel->targetlist, clauses); + /* cheapest_inner is the winner */ + innersortkeys = NIL; /* we do not need to sort it... */ } else - merge_pathkeys = outerpath->pathkeys; - - if (best_innerjoin && - path_is_cheaper(best_innerjoin, cheapest_inner)) - nestinnerpath = best_innerjoin; - else - nestinnerpath = cheapest_inner; + { + /* look for a presorted path that's cheaper */ + List *trialsortkeys = listCopy(innersortkeys); + Cost cheapest_cost; + int clausecount; - paths = lcons(create_nestloop_path(joinrel, - outerrel, - outerpath, - nestinnerpath, - merge_pathkeys), - NIL); + cheapest_cost = cheapest_inner->path_cost + + cost_sort(innersortkeys, innerrel->size, innerrel->width); - if (clauses && matchedJoinKeys) - { - bool path_is_cheaper_than_sort; - List *varkeys = NIL; - Path *mergeinnerpath = get_cheapest_path_for_joinkeys( - matchedJoinKeys, - outerpath_ordering, - innerrel->pathlist, - INNER); - - /* Should we use the mergeinner, or sort the cheapest inner? */ - path_is_cheaper_than_sort = (bool) (mergeinnerpath && - (mergeinnerpath->path_cost < - (cheapest_inner->path_cost + - cost_sort(matchedJoinKeys, innerrel->size, - innerrel->width)))); - if (!path_is_cheaper_than_sort) + for (clausecount = mergeclausecount; + clausecount > 0; + clausecount--) { - varkeys = make_pathkeys_from_joinkeys(matchedJoinKeys, - innerrel->targetlist, - INNER); + Path *trialinnerpath; + + /* Look for an inner path ordered well enough to merge with + * the first 'clausecount' mergeclauses. NB: trialsortkeys + * is modified destructively, which is why we made a copy... + */ + trialinnerpath = + get_cheapest_path_for_pathkeys(innerrel->pathlist, + ltruncate(clausecount, + trialsortkeys)); + if (trialinnerpath != NULL && + trialinnerpath->path_cost < cheapest_cost) + { + /* Found a cheaper (or even-cheaper) sorted path */ + cheapest_cost = trialinnerpath->path_cost; + mergeinnerpath = trialinnerpath; + mergeclausecount = clausecount; + innersortkeys = NIL; /* we will not need to sort it... */ + } } - - - /* - * Keep track of the cost of the outer path used with this - * ordered inner path for later processing in - * (match_unsorted_inner), since it isn't a sort and thus - * wouldn't otherwise be considered. - */ - if (path_is_cheaper_than_sort) - mergeinnerpath->outerjoincost = outerpath->path_cost; - else - mergeinnerpath = cheapest_inner; - - temp_node = lcons(create_mergejoin_path(joinrel, - outerrel->size, - innerrel->size, - outerrel->width, - innerrel->width, - outerpath, - mergeinnerpath, - merge_pathkeys, - xmergeinfo->m_ordering, - matchedJoinClauses, - NIL, - varkeys), - paths); } - else - temp_node = paths; - jp_list = nconc(jp_list, temp_node); + + /* Finally, we can build the mergejoin path */ + mergeclauses = ltruncate(mergeclausecount, + 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, + mergeclauses, + NIL, + innersortkeys)); } - return jp_list; + + return path_list; } /* * match_unsorted_inner - * Find the cheapest ordered join path for a given(ordered, unsorted) - * inner join path. - * - * Scans through each path available on an inner join relation and tries - * matching its ordering keys against those of mergejoin clauses. - * If 1. an appropriately_ordered inner path and matching mergeclause are - * found, and - * 2. sorting the cheapest outer path is cheaper than using an ordered - * but unsorted outer path(as was considered in - * (match_unsorted_outer)), then this merge path is considered. + * Generate mergejoin paths that use an explicit sort of the outer path + * with an already-ordered inner path. * * 'joinrel' is the join result relation * 'outerrel' is the outer join relation * 'innerrel' is the inner join relation * 'innerpath_list' is the list of possible inner join paths - * 'mergeinfo_list' is a list of nodes containing info on mergejoinable - * clauses + * 'mergeclause_list' is a list of RestrictInfo nodes for available + * mergejoin clauses between these two relations * * Returns a list of possible merge paths. */ @@ -423,78 +460,74 @@ match_unsorted_inner(RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *innerpath_list, - List *mergeinfo_list) + List *mergeclause_list) { - List *mp_list = NIL; + List *path_list = NIL; List *i; foreach(i, innerpath_list) { Path *innerpath = (Path *) lfirst(i); - PathOrder *innerpath_ordering = innerpath->pathorder; - MergeInfo *xmergeinfo = (MergeInfo *) NULL; - List *clauses = NIL; - List *matchedJoinKeys = NIL; - List *matchedJoinClauses = NIL; + List *mergeclauses; - if (innerpath_ordering) - xmergeinfo = match_order_mergeinfo(innerpath_ordering, - mergeinfo_list); + /* Look for useful mergeclauses (if any) */ + mergeclauses = find_mergeclauses_for_pathkeys(innerpath->pathkeys, + mergeclause_list); - if (xmergeinfo) - clauses = ((JoinMethod *) xmergeinfo)->clauses; - - if (clauses) - { - List *jmkeys = xmergeinfo->jmethod.jmkeys; - - order_joinkeys_by_pathkeys(innerpath->pathkeys, - jmkeys, - clauses, - INNER, - &matchedJoinKeys, - &matchedJoinClauses); - } - - /* - * (match_unsorted_outer) if it is applicable. 'OuterJoinCost was - * set above in - */ - if (clauses && matchedJoinKeys) + if (mergeclauses) { - Cost temp1; - - temp1 = outerrel->cheapestpath->path_cost + - cost_sort(matchedJoinKeys, outerrel->size, outerrel->width); - - if (innerpath->outerjoincost <= 0 /* unset? */ - || innerpath->outerjoincost > temp1) + List *outersortkeys; + Path *mergeouterpath; + List *merge_pathkeys; + + /* Compute the required ordering of the outer path */ + outersortkeys = + make_pathkeys_for_mergeclauses(mergeclauses, + outerrel->targetlist); + + /* Look for an outer path already ordered well enough to merge */ + mergeouterpath = + get_cheapest_path_for_pathkeys(outerrel->pathlist, + outersortkeys); + + /* Should we use the mergeouter, or sort the cheapest outer? */ + if (mergeouterpath != NULL && + mergeouterpath->path_cost <= + (outerrel->cheapestpath->path_cost + + cost_sort(outersortkeys, outerrel->size, outerrel->width))) { - List *outerkeys = make_pathkeys_from_joinkeys(matchedJoinKeys, - outerrel->targetlist, - OUTER); - List *merge_pathkeys = new_join_pathkeys(outerkeys, - joinrel->targetlist, - clauses); - - mp_list = lappend(mp_list, - create_mergejoin_path(joinrel, - outerrel->size, - innerrel->size, - outerrel->width, - innerrel->width, - (Path *) outerrel->cheapestpath, - innerpath, - merge_pathkeys, - xmergeinfo->m_ordering, - matchedJoinClauses, - outerkeys, - NIL)); + /* Use mergeouterpath */ + outersortkeys = NIL; /* no explicit sort step */ } + else + { + /* Use outerrel->cheapestpath, with the outersortkeys */ + mergeouterpath = outerrel->cheapestpath; + } + + /* Compute pathkeys the result will have */ + merge_pathkeys = build_join_pathkeys( + outersortkeys ? outersortkeys : mergeouterpath->pathkeys, + joinrel->targetlist, + mergeclauses); + + 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, + mergeclauses, + outersortkeys, + NIL)); } } - return mp_list; + return path_list; } /* @@ -520,49 +553,23 @@ hash_inner_and_outer(Query *root, foreach(i, joinrel->restrictinfo) { RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i); - Oid hashjoinop = restrictinfo->hashjoinoperator; /* we consider only clauses previously marked hashjoinable */ - if (hashjoinop) + if (restrictinfo->hashjoinoperator) { Expr *clause = restrictinfo->clause; Var *leftop = get_leftop(clause); Var *rightop = get_rightop(clause); - JoinKey *joinkey = makeNode(JoinKey); - List *joinkey_list; - List *outerkeys; - List *innerkeys; + Var *innerop; Cost innerdisbursion; - List *hash_pathkeys; HashPath *hash_path; - /* construct joinkey and pathkeys for this clause */ + /* find the inner var and estimate its disbursion */ if (intMember(leftop->varno, innerrel->relids)) - { - joinkey->outer = rightop; - joinkey->inner = leftop; - } + innerop = leftop; else - { - joinkey->outer = leftop; - joinkey->inner = rightop; - } - joinkey_list = lcons(joinkey, NIL); - - outerkeys = make_pathkeys_from_joinkeys(joinkey_list, - outerrel->targetlist, - OUTER); - innerkeys = make_pathkeys_from_joinkeys(joinkey_list, - innerrel->targetlist, - INNER); - - innerdisbursion = estimate_disbursion(root, joinkey->inner); - - /* - * We cannot assume that the output of the hashjoin appears in - * any particular order, so it should have NIL pathkeys. - */ - hash_pathkeys = NIL; + innerop = rightop; + innerdisbursion = estimate_disbursion(root, innerop); hash_path = create_hashjoin_path(joinrel, outerrel->size, @@ -571,11 +578,7 @@ hash_inner_and_outer(Query *root, innerrel->width, (Path *) outerrel->cheapestpath, (Path *) innerrel->cheapestpath, - hash_pathkeys, - hashjoinop, lcons(clause, NIL), - outerkeys, - innerkeys, innerdisbursion); hpath_list = lappend(hpath_list, hash_path); } @@ -605,3 +608,36 @@ estimate_disbursion(Query *root, Var *var) return (Cost) get_attdisbursion(relid, var->varattno, 0.1); } + +/* + * select_mergejoin_clauses + * Select mergejoin clauses that are usable for a particular join. + * Returns a list of RestrictInfo nodes for those clauses. + * + * Currently, all we need is the restrictinfo list of the joinrel. + * By definition, any mergejoinable clause in that list will work --- + * it must involve only vars in the join, or it wouldn't have been + * in the restrict list, and it must involve vars on both sides of + * the join, or it wouldn't have made it up to this level of join. + * Since we currently allow only simple Vars as the left and right + * sides of mergejoin clauses, that means the mergejoin clauses must + * be usable for this join. If we ever allow more complex expressions + * containing multiple Vars, we would need to check that each side + * of a potential joinclause uses only vars from one side of the join. + */ +static List * +select_mergejoin_clauses(List *restrictinfo_list) +{ + List *result_list = NIL; + List *i; + + foreach(i, restrictinfo_list) + { + RestrictInfo *restrictinfo = lfirst(i); + + if (restrictinfo->mergejoinoperator != InvalidOid) + result_list = lcons(restrictinfo, result_list); + } + + return result_list; +} diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c index 1eac6770744..9085e0a3934 100644 --- a/src/backend/optimizer/path/joinrels.c +++ b/src/backend/optimizer/path/joinrels.c @@ -7,12 +7,22 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.38 1999/07/27 06:23:12 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.39 1999/08/16 02:17:51 tgl Exp $ * *------------------------------------------------------------------------- */ #include "postgres.h" +#ifdef HAVE_LIMITS_H +#include <limits.h> +#ifndef MAXINT +#define MAXINT INT_MAX +#endif +#else +#ifdef HAVE_VALUES_H +#include <values.h> +#endif +#endif #include "optimizer/cost.h" #include "optimizer/joininfo.h" @@ -20,17 +30,18 @@ #include "optimizer/paths.h" #include "optimizer/tlist.h" -static List *new_joininfo_list(List *joininfo_list, Relids join_relids); -static void set_joinrel_size(RelOptInfo *joinrel, RelOptInfo *outer_rel, - RelOptInfo *inner_rel, JoinInfo *jinfo); -static RelOptInfo *make_join_rel(RelOptInfo *outer_rel, RelOptInfo *inner_rel, - JoinInfo *joininfo); +static RelOptInfo *make_join_rel(RelOptInfo *outer_rel, RelOptInfo *inner_rel); 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 * Find all possible joins for each of the outer join relations in - * 'outer_rels'. A rel node is created for each possible join relation, + * 'old_rels'. A rel node is created for each possible join relation, * and the resulting list of nodes is returned. If at all possible, only * those relations for which join clauses exist are considered. If none * of these exist for a given relation, all remaining possibilities are @@ -41,19 +52,18 @@ static List *new_join_tlist(List *tlist, int first_resdomno); List * make_rels_by_joins(Query *root, List *old_rels) { - List *joined_rels = NIL; List *join_list = NIL; - List *r = NIL; + List *r; foreach(r, old_rels) { RelOptInfo *old_rel = (RelOptInfo *) lfirst(r); + List *joined_rels; if (!(joined_rels = make_rels_by_clause_joins(root, old_rel, old_rel->joininfo, NIL))) { - /* * Oops, we have a relation that is not joined to any other * relation. Cartesian product time. @@ -73,16 +83,16 @@ make_rels_by_joins(Query *root, List *old_rels) /* * make_rels_by_clause_joins - * Determines whether joins can be performed between an outer relation - * 'outer_rel' and those relations within 'outer_rel's joininfo nodes - * (i.e., relations that participate in join clauses that 'outer_rel' - * participates in). This is possible if all but one of the relations - * contained within the join clauses of the joininfo node are already - * contained within 'outer_rel'. + * Build joins between an outer relation 'old_rel' and relations + * within old_rel's joininfo nodes + * (i.e., relations that participate in join clauses that 'old_rel' + * also participates in). * - * 'outer_rel' is the relation entry for the outer relation - * 'joininfo_list' is a list of join clauses which 'outer_rel' + * 'old_rel' is the relation entry for the outer relation + * 'joininfo_list' is a list of join clauses which 'old_rel' * participates in + * 'only_relids': if not NIL, only joins against base rels mentioned in + * only_relids are allowable. * * Returns a list of new join relations. */ @@ -91,55 +101,55 @@ make_rels_by_clause_joins(Query *root, RelOptInfo *old_rel, List *joininfo_list, Relids only_relids) { List *join_list = NIL; - List *i = NIL; + List *i; foreach(i, joininfo_list) { JoinInfo *joininfo = (JoinInfo *) lfirst(i); - RelOptInfo *joined_rel; Relids unjoined_relids = joininfo->unjoined_relids; + RelOptInfo *joined_rel; + + if (unjoined_relids == NIL) + continue; /* probably can't happen */ - if (unjoined_relids != NIL) + if (length(unjoined_relids) == 1 && + (only_relids == NIL || + /* geqo only wants certain relids to be joined to old_rel */ + intMember(lfirsti(unjoined_relids), only_relids))) { - if (length(unjoined_relids) == 1 && - (only_relids == NIL || - /* geqo only wants certain relids to make new rels */ - intMember(lfirsti(unjoined_relids), only_relids))) + RelOptInfo *base_rel = get_base_rel(root, + lfirsti(unjoined_relids)); + + /* Left-sided join of outer rel against a single base rel */ + joined_rel = make_join_rel(old_rel, base_rel); + join_list = lappend(join_list, joined_rel); + + /* Consider right-sided plan as well */ + if (length(old_rel->relids) > 1) { - joined_rel = make_join_rel(old_rel, - get_base_rel(root, - lfirsti(unjoined_relids)), - joininfo); + joined_rel = make_join_rel(base_rel, old_rel); join_list = lappend(join_list, joined_rel); - - /* Right-sided plan */ - if (length(old_rel->relids) > 1) - { - joined_rel = make_join_rel( - get_base_rel(root, lfirsti(unjoined_relids)), - old_rel, - joininfo); - join_list = lappend(join_list, joined_rel); - } } + } + + if (only_relids == NIL) /* no bushy plans for geqo */ + { + List *r; - if (only_relids == NIL) /* no bushy from geqo */ + /* Build "bushy" plans: join old_rel against all pre-existing + * joins of rels it doesn't already contain, if there is a + * suitable join clause. + */ + foreach(r, root->join_rel_list) { - List *r; + RelOptInfo *join_rel = lfirst(r); - foreach(r, root->join_rel_list) + Assert(length(join_rel->relids) > 1); + if (is_subset(unjoined_relids, join_rel->relids) && + nonoverlap_sets(old_rel->relids, join_rel->relids)) { - RelOptInfo *join_rel = lfirst(r); - - Assert(length(join_rel->relids) > 1); - if (is_subset(unjoined_relids, join_rel->relids) && - nonoverlap_sets(old_rel->relids, join_rel->relids)) - { - joined_rel = make_join_rel(old_rel, - join_rel, - joininfo); - join_list = lappend(join_list, joined_rel); - } + joined_rel = make_join_rel(old_rel, join_rel); + join_list = lappend(join_list, joined_rel); } } } @@ -150,32 +160,30 @@ make_rels_by_clause_joins(Query *root, RelOptInfo *old_rel, /* * make_rels_by_clauseless_joins - * Given an outer relation 'outer_rel' and a list of inner relations - * 'inner_rels', create a join relation between 'outer_rel' and each - * member of 'inner_rels' that isn't already included in 'outer_rel'. + * Given an outer relation 'old_rel' and a list of inner relations + * 'inner_rels', create a join relation between 'old_rel' and each + * member of 'inner_rels' that isn't already included in 'old_rel'. * * Returns a list of new join relations. */ List * make_rels_by_clauseless_joins(RelOptInfo *old_rel, List *inner_rels) { - RelOptInfo *inner_rel; - List *t_list = NIL; - List *i = NIL; + List *join_list = NIL; + List *i; foreach(i, inner_rels) { - inner_rel = (RelOptInfo *) lfirst(i); + RelOptInfo *inner_rel = (RelOptInfo *) lfirst(i); + if (nonoverlap_sets(inner_rel->relids, old_rel->relids)) { - t_list = lappend(t_list, - make_join_rel(old_rel, - inner_rel, - (JoinInfo *) NULL)); + join_list = lappend(join_list, + make_join_rel(old_rel, inner_rel)); } } - return t_list; + return join_list; } /* @@ -184,65 +192,58 @@ make_rels_by_clauseless_joins(RelOptInfo *old_rel, List *inner_rels) * * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be * joined - * 'joininfo' is the joininfo node(join clause) containing both - * 'outer_rel' and 'inner_rel', if any exists * * Returns the new join relation node. */ static RelOptInfo * -make_join_rel(RelOptInfo *outer_rel, RelOptInfo *inner_rel, JoinInfo *joininfo) +make_join_rel(RelOptInfo *outer_rel, RelOptInfo *inner_rel) { RelOptInfo *joinrel = makeNode(RelOptInfo); - List *joinrel_joininfo_list = NIL; List *new_outer_tlist; List *new_inner_tlist; /* - * Create a new tlist by removing irrelevant elements from both tlists - * of the outer and inner join relations and then merging the results - * together. + * This function uses a trick to pass inner/outer rels as two sublists. + * The list will be flattened out in update_rels_pathlist_for_joins(). */ - new_outer_tlist = new_join_tlist(outer_rel->targetlist, 1); - new_inner_tlist = new_join_tlist(inner_rel->targetlist, - length(new_outer_tlist) + 1); - - joinrel->relids = NIL; + joinrel->relids = lcons(outer_rel->relids, lcons(inner_rel->relids, NIL)); joinrel->indexed = false; joinrel->pages = 0; joinrel->tuples = 0; + joinrel->size = 0; joinrel->width = 0; /* joinrel->targetlist = NIL;*/ joinrel->pathlist = NIL; joinrel->cheapestpath = (Path *) NULL; joinrel->pruneable = true; joinrel->classlist = NULL; - joinrel->relam = InvalidOid; + joinrel->indexkeys = NULL; joinrel->ordering = NULL; + joinrel->relam = InvalidOid; joinrel->restrictinfo = NIL; - joinrel->joininfo = NULL; + joinrel->joininfo = NIL; joinrel->innerjoin = NIL; /* - * This function uses a trick to pass inner/outer rels as different - * lists, and then flattens it out later. bjm + * Create a new tlist by removing irrelevant elements from both tlists + * of the outer and inner join relations and then merging the results + * together. */ - joinrel->relids = lcons(outer_rel->relids, lcons(inner_rel->relids, NIL)); - - new_outer_tlist = nconc(new_outer_tlist, new_inner_tlist); - joinrel->targetlist = new_outer_tlist; - - if (joininfo) - joinrel->restrictinfo = joininfo->jinfo_restrictinfo; - - joinrel_joininfo_list = new_joininfo_list( - nconc(copyObject(outer_rel->joininfo), - copyObject(inner_rel->joininfo)), - nconc(listCopy(outer_rel->relids), - listCopy(inner_rel->relids))); + new_outer_tlist = new_join_tlist(outer_rel->targetlist, 1); + new_inner_tlist = new_join_tlist(inner_rel->targetlist, + length(new_outer_tlist) + 1); + joinrel->targetlist = nconc(new_outer_tlist, new_inner_tlist); - joinrel->joininfo = joinrel_joininfo_list; + /* + * Construct restrict and join clause lists for the new joinrel. + */ + build_joinrel_restrict_and_join(joinrel, + nconc(copyObject(outer_rel->joininfo), + copyObject(inner_rel->joininfo)), + nconc(listCopy(outer_rel->relids), + listCopy(inner_rel->relids))); - set_joinrel_size(joinrel, outer_rel, inner_rel, joininfo); + set_joinrel_size(joinrel, outer_rel, inner_rel); return joinrel; } @@ -255,6 +256,9 @@ make_join_rel(RelOptInfo *outer_rel, RelOptInfo *inner_rel, JoinInfo *joininfo) * for future joins, its 'joinlist' field must not be empty after removal * of all relids in 'other_relids'. * + * XXX this seems to be a dead test --- we don't keep track of joinlists + * for individual targetlist entries anymore, if we ever did... + * * 'tlist' is the target list of one of the join relations * 'other_relids' is a list of relids contained within the other * join relation @@ -268,15 +272,14 @@ new_join_tlist(List *tlist, int first_resdomno) { int resdomno = first_resdomno - 1; - TargetEntry *xtl = NULL; List *t_list = NIL; - List *i = NIL; + List *i; List *join_list = NIL; - bool in_final_tlist = false; foreach(i, tlist) { - xtl = lfirst(i); + TargetEntry *xtl = lfirst(i); + bool in_final_tlist; /* * XXX surely this is wrong? join_list is never changed? tgl @@ -286,7 +289,8 @@ new_join_tlist(List *tlist, if (in_final_tlist) { resdomno += 1; - t_list = lappend(t_list, create_tl_element(get_expr(xtl), resdomno)); + t_list = lappend(t_list, + create_tl_element(get_expr(xtl), resdomno)); } } @@ -294,69 +298,81 @@ new_join_tlist(List *tlist, } /* - * new_joininfo_list - * Builds a join relation's joininfo list by checking for join clauses - * which still need to used in future joins involving this relation. A - * join clause is still needed if there are still relations in the clause - * not contained in the list of relations comprising this join relation. - * New joininfo nodes are only created and added to - * 'current_joininfo_list' if a node for a particular join hasn't already - * been created. + * build_joinrel_restrict_and_join + * Builds a join relation's restrictinfo and joininfo lists from the + * joininfo lists of the relations it joins. If a join clause from an + * input relation refers to base rels still not present in the joinrel, + * then it is still a join clause for the joinrel; we put it into an + * appropriate JoinInfo list for the joinrel. Otherwise, the clause is + * now a restrict clause for the joined relation, and we put it into + * the joinrel's restrictinfo list. (It will not need to be considered + * further up the join tree.) * - * 'current_joininfo_list' contains a list of those joininfo nodes that - * have already been built - * 'joininfo_list' is the list of join clauses involving this relation - * 'join_relids' is a list of relids corresponding to the relations - * currently being joined + * '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 * - * Returns a list of joininfo nodes, new and old. + * 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... */ -static List * -new_joininfo_list(List *joininfo_list, Relids join_relids) +static void +build_joinrel_restrict_and_join(RelOptInfo *joinrel, + List *joininfo_list, + Relids join_relids) { - List *current_joininfo_list = NIL; - Relids new_unjoined_relids = NIL; - JoinInfo *other_joininfo = (JoinInfo *) NULL; - List *xjoininfo = NIL; + List *output_restrictinfo_list = NIL; + List *output_joininfo_list = NIL; + List *xjoininfo; foreach(xjoininfo, joininfo_list) { - List *or; JoinInfo *joininfo = (JoinInfo *) lfirst(xjoininfo); + Relids new_unjoined_relids; - new_unjoined_relids = joininfo->unjoined_relids; - foreach(or, new_unjoined_relids) + new_unjoined_relids = set_differencei(joininfo->unjoined_relids, + join_relids); + if (new_unjoined_relids == NIL) { - if (intMember(lfirsti(or), join_relids)) - new_unjoined_relids = lremove((void *) lfirst(or), new_unjoined_relids); + /* + * Clauses in this JoinInfo list become restriction clauses + * for the joinrel, since they refer to no outside rels. + * + * Be careful to eliminate duplicates, since we will see the + * same clauses arriving from both input relations... + */ + output_restrictinfo_list = + LispUnion(output_restrictinfo_list, + joininfo->jinfo_restrictinfo); } - joininfo->unjoined_relids = new_unjoined_relids; - if (new_unjoined_relids != NIL) + else { - other_joininfo = joininfo_member(new_unjoined_relids, - current_joininfo_list); - if (other_joininfo) + 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. + */ + old_joininfo = joininfo_member(new_unjoined_relids, + output_joininfo_list); + if (old_joininfo) { - other_joininfo->jinfo_restrictinfo = (List *) - LispUnion(joininfo->jinfo_restrictinfo, - other_joininfo->jinfo_restrictinfo); + old_joininfo->jinfo_restrictinfo = + LispUnion(old_joininfo->jinfo_restrictinfo, + joininfo->jinfo_restrictinfo); } else { - other_joininfo = makeNode(JoinInfo); - - other_joininfo->unjoined_relids = joininfo->unjoined_relids; - other_joininfo->jinfo_restrictinfo = joininfo->jinfo_restrictinfo; - other_joininfo->mergejoinable = joininfo->mergejoinable; - other_joininfo->hashjoinable = joininfo->hashjoinable; - - current_joininfo_list = lcons(other_joininfo, - current_joininfo_list); + joininfo->unjoined_relids = new_unjoined_relids; + output_joininfo_list = lcons(joininfo, + output_joininfo_list); } } } - return current_joininfo_list; + joinrel->restrictinfo = output_restrictinfo_list; + joinrel->joininfo = output_joininfo_list; } /* @@ -376,7 +392,12 @@ get_cheapest_complete_rel(List *join_rel_list) /* * find the relations that have no further joins, i.e., its joininfos - * all have unjoined_relids nil. + * all have unjoined_relids nil. (Actually, a JoinInfo shouldn't + * ever have nil unjoined_relids, so I think this code is overly + * complex. In fact it seems wrong; shouldn't we be looking for + * rels with complete relids lists??? Seems like a cartesian-product + * case could fail because sub-relations could have nil JoinInfo lists. + * Doesn't actually fail but I don't really understand why...) */ foreach(xrel, join_rel_list) { @@ -404,26 +425,24 @@ get_cheapest_complete_rel(List *join_rel_list) } static void -set_joinrel_size(RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel, JoinInfo *jinfo) +set_joinrel_size(RelOptInfo *joinrel, RelOptInfo *outer_rel, + RelOptInfo *inner_rel) { + double dtuples; int ntuples; - float selec; - /* - * voodoo magic. but better than a size of 0. I have no idea why we - * didn't set the size before. -ay 2/95 + /* avoid overflow ... probably, tuple estimates in RelOptInfo + * just ought to be double ... */ - if (jinfo == NULL) - { - /* worst case: the cartesian product */ - ntuples = outer_rel->tuples * inner_rel->tuples; - } + 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 - { - selec = product_selec(jinfo->jinfo_restrictinfo); -/* ntuples = Min(outer_rel->tuples,inner_rel->tuples) * selec; */ - ntuples = outer_rel->tuples * inner_rel->tuples * selec; - } + ntuples = (int) dtuples; /* * I bet sizes less than 1 will screw up optimization so make the best diff --git a/src/backend/optimizer/path/mergeutils.c b/src/backend/optimizer/path/mergeutils.c deleted file mode 100644 index 1cc19693f8d..00000000000 --- a/src/backend/optimizer/path/mergeutils.c +++ /dev/null @@ -1,131 +0,0 @@ -/*------------------------------------------------------------------------- - * - * mergeutils.c - * Utilities for finding applicable merge clauses and pathkeys - * - * Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/mergeutils.c,v 1.24 1999/07/16 04:59:15 momjian Exp $ - * - *------------------------------------------------------------------------- - */ -#include "postgres.h" - - -#include "optimizer/clauses.h" -#include "optimizer/ordering.h" -#include "optimizer/paths.h" - -/* - * group_clauses_by_order - * If a join clause node in 'restrictinfo_list' is mergejoinable, store - * it within a mergeinfo node containing other clause nodes with the same - * mergejoin ordering. - * - * XXX This is completely braindead: there is no reason anymore to segregate - * mergejoin clauses by join operator, since the executor can handle mergejoin - * clause sets with different operators in them. Instead, we ought to be - * building a MergeInfo for each potentially useful ordering of the input - * relations. But right now the optimizer's internal data structures do not - * support that (MergeInfo can only store one MergeOrder for a set of clauses). - * Something to fix next time... - * - * 'restrictinfo_list' is the list of restrictinfo nodes - * 'inner_relids' is the list of relids in the inner join relation - * (used to determine whether a join var is inner or outer) - * - * Returns the new list of mergeinfo nodes. - * - */ -List * -group_clauses_by_order(List *restrictinfo_list, - Relids inner_relids) -{ - List *mergeinfo_list = NIL; - List *xrestrictinfo; - - foreach(xrestrictinfo, restrictinfo_list) - { - RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(xrestrictinfo); - MergeOrder *merge_ordering = restrictinfo->mergejoinorder; - - if (merge_ordering) - { - - /* - * Create a new mergeinfo node and add it to 'mergeinfo_list' - * if one does not yet exist for this merge ordering. - */ - Expr *clause = restrictinfo->clause; - Var *leftop = get_leftop(clause); - Var *rightop = get_rightop(clause); - PathOrder *pathorder; - MergeInfo *xmergeinfo; - JoinKey *jmkeys; - - pathorder = makeNode(PathOrder); - pathorder->ordtype = MERGE_ORDER; - pathorder->ord.merge = merge_ordering; - xmergeinfo = match_order_mergeinfo(pathorder, mergeinfo_list); - jmkeys = makeNode(JoinKey); - if (intMember(leftop->varno, inner_relids)) - { - jmkeys->outer = rightop; - jmkeys->inner = leftop; - } - else - { - jmkeys->outer = leftop; - jmkeys->inner = rightop; - } - - if (xmergeinfo == NULL) - { - xmergeinfo = makeNode(MergeInfo); - xmergeinfo->m_ordering = merge_ordering; - mergeinfo_list = lcons(xmergeinfo, mergeinfo_list); - } - - xmergeinfo->jmethod.clauses = lcons(clause, - xmergeinfo->jmethod.clauses); - xmergeinfo->jmethod.jmkeys = lcons(jmkeys, - xmergeinfo->jmethod.jmkeys); - } - } - return mergeinfo_list; -} - - -/* - * match_order_mergeinfo - * Searches the list 'mergeinfo_list' for a mergeinfo node whose order - * field equals 'ordering'. - * - * Returns the node if it exists. - * - */ -MergeInfo * -match_order_mergeinfo(PathOrder *ordering, List *mergeinfo_list) -{ - MergeOrder *xmergeorder; - List *xmergeinfo = NIL; - - foreach(xmergeinfo, mergeinfo_list) - { - MergeInfo *mergeinfo = (MergeInfo *) lfirst(xmergeinfo); - - xmergeorder = mergeinfo->m_ordering; - - if ((ordering->ordtype == MERGE_ORDER && - equal_merge_ordering(ordering->ord.merge, xmergeorder)) || - (ordering->ordtype == SORTOP_ORDER && - equal_path_merge_ordering(ordering->ord.sortop, xmergeorder))) - { - - return mergeinfo; - } - } - return (MergeInfo *) NIL; -} diff --git a/src/backend/optimizer/path/orindxpath.c b/src/backend/optimizer/path/orindxpath.c index 450b8d7b2dc..51699a73d21 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.31 1999/07/27 03:51:02 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.32 1999/08/16 02:17:52 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -66,12 +66,12 @@ create_or_index_paths(Query *root, * saved by create_index_paths(). */ if (restriction_is_or_clause(clausenode) && - clausenode->indexids) + clausenode->subclauseindices) { bool all_indexable = true; List *temp; - foreach(temp, clausenode->indexids) + foreach(temp, clausenode->subclauseindices) { if (lfirst(temp) == NIL) { @@ -94,7 +94,7 @@ create_or_index_paths(Query *root, best_or_subclause_indices(root, rel, clausenode->clause->args, - clausenode->indexids, + clausenode->subclauseindices, &indexquals, &indexids, &cost, @@ -102,20 +102,17 @@ create_or_index_paths(Query *root, pathnode->path.pathtype = T_IndexScan; pathnode->path.parent = rel; - pathnode->path.pathorder = makeNode(PathOrder); - pathnode->path.pathorder->ordtype = SORTOP_ORDER; - /* * This is an IndexScan, but the overall result will consist * of tuples extracted in multiple passes (one for each * subclause of the OR), so the result cannot be claimed * to have any particular ordering. */ - pathnode->path.pathorder->ord.sortop = NULL; pathnode->path.pathkeys = NIL; - pathnode->indexqual = indexquals; pathnode->indexid = indexids; + pathnode->indexqual = indexquals; + pathnode->joinrelids = NIL; /* no join clauses here */ pathnode->path.path_cost = cost; clausenode->selectivity = (Cost) selec; diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index c0782c5665b..44a7b614b69 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -1,70 +1,84 @@ /*------------------------------------------------------------------------- * - * joinutils.c - * Utilities for matching and building join and path keys + * pathkeys.c + * Utilities for matching and building path keys * * Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.13 1999/08/13 01:17:16 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.14 1999/08/16 02:17:52 tgl Exp $ * *------------------------------------------------------------------------- */ #include "postgres.h" - +#include "nodes/makefuncs.h" +#include "optimizer/clauses.h" #include "optimizer/joininfo.h" -#include "optimizer/keys.h" -#include "optimizer/ordering.h" #include "optimizer/paths.h" #include "optimizer/tlist.h" +#include "optimizer/var.h" +#include "parser/parsetree.h" +#include "utils/lsyscache.h" -static int match_pathkey_joinkeys(List *pathkey, List *joinkeys, - int outer_or_inner); -static List *new_join_pathkey(List *pathkeys, List *join_rel_tlist, - List *joinclauses); +static PathKeyItem *makePathKeyItem(Node *key, Oid sortop); +static bool pathkeyitem_equal(PathKeyItem *a, PathKeyItem *b); +static bool pathkeyitem_member(PathKeyItem *a, List *l); +static Var *find_indexkey_var(int indexkey, List *tlist); +static List *build_join_pathkey(List *pathkeys, List *join_rel_tlist, + List *joinclauses); /*-------------------- * Explanation of Path.pathkeys * - * Path.pathkeys is a List of List of Var nodes that represent the sort - * order of the result generated by the Path. + * Path.pathkeys is a List of Lists of PathKeyItem nodes that represent + * the sort order of the result generated by the Path. The n'th sublist + * represents the n'th sort key of the result. * - * In single/base relation RelOptInfo's, the Path's represent various ways + * In single/base relation RelOptInfo's, the Paths represent various ways * of scanning the relation and the resulting ordering of the tuples. * Sequential scan Paths have NIL pathkeys, indicating no known ordering. * Index scans have Path.pathkeys that represent the chosen index's ordering, * if any. A single-key index would create a pathkey with a single sublist, - * e.g. ( (tab1_indexkey1) ). A multi-key index generates a sublist per key, - * e.g. ( (tab1_indexkey1) (tab1_indexkey2) ) which shows major sort by - * indexkey1 and minor sort by indexkey2. + * e.g. ( (tab1.indexkey1/sortop1) ). A multi-key index generates a sublist + * per key, e.g. ( (tab1.indexkey1/sortop1) (tab1.indexkey2/sortop2) ) which + * shows major sort by indexkey1 (ordering by sortop1) and minor sort by + * indexkey2 with sortop2. * * Note that a multi-pass indexscan (OR clause scan) has NIL pathkeys since - * we can say nothing about the overall order of its result. Also, an index - * scan on an unordered type of index generates no useful pathkeys. However, + * we can say nothing about the overall order of its result. Also, an + * indexscan on an unordered type of index generates NIL pathkeys. However, * we can always create a pathkey by doing an explicit sort. * * Multi-relation RelOptInfo Path's are more complicated. Mergejoins are - * only performed with equijoins ("="). Because of this, the multi-relation - * path actually has more than one primary Var key. For example, a - * mergejoin Path of "tab1.col1 = tab2.col1" would generate pathkeys of - * ( (tab1.col1 tab2.col1) ), indicating that the major sort order of the - * Path can be taken to be *either* tab1.col1 or tab2.col1. + * only performed with equijoins ("="). Because of this, the resulting + * multi-relation path actually has more than one primary key. For example, + * a mergejoin using a clause "tab1.col1 = tab2.col1" would generate pathkeys + * of ( (tab1.col1/sortop1 tab2.col1/sortop2) ), indicating that the major + * sort order of the Path can be taken to be *either* tab1.col1 or tab2.col1. * They are equal, so they are both primary sort keys. This allows future - * joins to use either Var as a pre-sorted key to prevent upper Mergejoins + * joins to use either var as a pre-sorted key to prevent upper Mergejoins * from having to re-sort the Path. This is why pathkeys is a List of Lists. * * Note that while the order of the top list is meaningful (primary vs. - * secondary sort key), the order of each sublist is arbitrary. - * - * We can actually keep all of the keys of the outer path of a merge or - * nestloop join, since the ordering of the outer path will be reflected - * in the result. We add to each pathkey sublist any inner vars that are - * equijoined to any of the outer vars in the sublist. In the nestloop - * case we have to be careful to consider only equijoin operators; the - * nestloop's join clauses might include non-equijoin operators. + * secondary sort key), the order of each sublist is arbitrary. No code + * working with pathkeys should generate a result that depends on the order + * of a pathkey sublist. + * + * We keep a sortop associated with each PathKeyItem because cross-data-type + * mergejoins are possible; for example int4=int8 is mergejoinable. In this + * case we need to remember that the left var is ordered by int4lt while + * the right var is ordered by int8lt. So the different members of each + * sublist could have different sortops. + * + * When producing the pathkeys for a merge or nestloop join, we can keep + * all of the keys of the outer path, since the ordering of the outer path + * will be preserved in the result. We add to each pathkey sublist any inner + * vars that are equijoined to any of the outer vars in the sublist. In the + * nestloop case we have to be careful to consider only equijoin operators; + * the nestloop's join clauses might include non-equijoin operators. * (Currently, we do this by considering only mergejoinable operators while * making the pathkeys, since we have no separate marking for operators that * are equijoins but aren't mergejoinable.) @@ -75,180 +89,174 @@ static List *new_join_pathkey(List *pathkeys, List *join_rel_tlist, * executor might have to split the join into multiple batches. Therefore * a Hashjoin is always given NIL pathkeys. * - * Notice that pathkeys only say *what* is being ordered, and not *how* - * it is ordered. The actual sort ordering is indicated by a separate - * data structure, the PathOrder. The PathOrder provides a sort operator - * OID for each of the sublists of the path key. This is fairly bogus, - * since in cross-datatype cases we really want to keep track of more than - * one sort operator... - * * -- bjm & tgl *-------------------- */ + +/* + * makePathKeyItem + * create a PathKeyItem node + */ +static PathKeyItem * +makePathKeyItem(Node *key, Oid sortop) +{ + PathKeyItem *item = makeNode(PathKeyItem); + + item->key = key; + item->sortop = sortop; + return item; +} + /**************************************************************************** - * KEY COMPARISONS + * PATHKEY COMPARISONS ****************************************************************************/ /* - * order_joinkeys_by_pathkeys - * Attempts to match the keys of a path against the keys of join clauses. - * This is done by looking for a matching join key in 'joinkeys' for - * every path key in the list 'path.keys'. If there is a matching join key - * (not necessarily unique) for every path key, then the list of - * corresponding join keys and join clauses are returned in the order in - * which the keys matched the path keys. - * - * 'pathkeys' is a list of path keys: - * ( ( (var) (var) ... ) ( (var) ... ) ) - * 'joinkeys' is a list of join keys: - * ( (outer inner) (outer inner) ... ) - * 'joinclauses' is a list of clauses corresponding to the join keys in - * 'joinkeys' - * 'outer_or_inner' is a flag that selects the desired pathkey of a join key - * in 'joinkeys' - * - * Returns the join keys and corresponding join clauses in a list if all - * of the path keys were matched: - * ( - * ( (outerkey0 innerkey0) ... (outerkeyN or innerkeyN) ) - * ( clause0 ... clauseN ) - * ) - * and nil otherwise. - * - * Returns a list of matched join keys and a list of matched join clauses - * in pointers if valid order can be found. + * Compare two pathkey items for equality. + * + * This is unlike straight equal() because when the two keys are both Vars, + * we want to apply the weaker var_equal() condition (doesn't check varnoold + * or varoattno). But if that fails, try equal() so that we recognize + * functional-index keys. */ -bool -order_joinkeys_by_pathkeys(List *pathkeys, - List *joinkeys, - List *joinclauses, - int outer_or_inner, - List **matchedJoinKeysPtr, - List **matchedJoinClausesPtr) +static bool +pathkeyitem_equal (PathKeyItem *a, PathKeyItem *b) { - List *matched_joinkeys = NIL; - List *matched_joinclauses = NIL; - List *pathkey = NIL; - List *i = NIL; - int matched_joinkey_index = -1; - int matched_keys = 0; - - /* - * Reorder the joinkeys by picking out one that matches each pathkey, - * and create a new joinkey/joinclause list in pathkey order - */ - foreach(i, pathkeys) + Assert(a && IsA(a, PathKeyItem)); + Assert(b && IsA(b, PathKeyItem)); + + if (a->sortop != b->sortop) + return false; + if (var_equal((Var *) a->key, (Var *) b->key)) + return true; + return equal(a->key, b->key); +} + +/* + * member() test using pathkeyitem_equal + */ +static bool +pathkeyitem_member (PathKeyItem *a, List *l) +{ + List *i; + + Assert(a && IsA(a, PathKeyItem)); + + foreach(i, l) + { + if (pathkeyitem_equal(a, (PathKeyItem *) lfirst(i))) + return true; + } + return false; +} + +/* + * compare_pathkeys + * Compare two pathkeys to see if they are equivalent, and if not whether + * one is "better" than the other. + * + * A pathkey can be considered better than another if it is a superset: + * it contains all the keys of the other plus more. For example, either + * ((A) (B)) or ((A B)) is better than ((A)). + * + * This gets called a lot, so it is optimized. + */ +PathKeysComparison +compare_pathkeys(List *keys1, List *keys2) +{ + List *key1, + *key2; + bool key1_subsetof_key2 = true, + key2_subsetof_key1 = true; + + for (key1 = keys1, key2 = keys2; + key1 != NIL && key2 != NIL; + key1 = lnext(key1), key2 = lnext(key2)) { - pathkey = lfirst(i); - matched_joinkey_index = match_pathkey_joinkeys(pathkey, joinkeys, - outer_or_inner); + List *subkey1 = lfirst(key1); + List *subkey2 = lfirst(key2); + List *i; - if (matched_joinkey_index != -1) + /* We have to do this the hard way since the ordering of the subkey + * lists is arbitrary. + */ + if (key1_subsetof_key2) { - matched_keys++; - if (matchedJoinKeysPtr) + foreach(i, subkey1) { - JoinKey *joinkey = nth(matched_joinkey_index, joinkeys); - - matched_joinkeys = lappend(matched_joinkeys, joinkey); + if (! pathkeyitem_member((PathKeyItem *) lfirst(i), subkey2)) + { + key1_subsetof_key2 = false; + break; + } } + } - if (matchedJoinClausesPtr) + if (key2_subsetof_key1) + { + foreach(i, subkey2) { - Expr *joinclause = nth(matched_joinkey_index, - joinclauses); - - Assert(joinclauses); - matched_joinclauses = lappend(matched_joinclauses, joinclause); + if (! pathkeyitem_member((PathKeyItem *) lfirst(i), subkey1)) + { + key2_subsetof_key1 = false; + break; + } } } - else - /* A pathkey could not be matched. */ - break; - } - /* - * Did we fail to match all the joinkeys? Extra pathkeys are no - * problem. - */ - if (matched_keys != length(joinkeys)) - { - if (matchedJoinKeysPtr) - *matchedJoinKeysPtr = NIL; - if (matchedJoinClausesPtr) - *matchedJoinClausesPtr = NIL; - return false; + if (!key1_subsetof_key2 && !key2_subsetof_key1) + return PATHKEYS_DIFFERENT; /* no need to keep looking */ } - if (matchedJoinKeysPtr) - *matchedJoinKeysPtr = matched_joinkeys; - if (matchedJoinClausesPtr) - *matchedJoinClausesPtr = matched_joinclauses; - return true; + /* If we reached the end of only one list, the other is longer and + * therefore not a subset. (We assume the additional sublist(s) + * of the other list are not NIL --- no pathkey list should ever have + * a NIL sublist.) + */ + if (key1 != NIL) + key1_subsetof_key2 = false; + if (key2 != NIL) + key2_subsetof_key1 = false; + + if (key1_subsetof_key2 && key2_subsetof_key1) + return PATHKEYS_EQUAL; + if (key1_subsetof_key2) + return PATHKEYS_BETTER2; + if (key2_subsetof_key1) + return PATHKEYS_BETTER1; + return PATHKEYS_DIFFERENT; } - /* - * match_pathkey_joinkeys - * Returns the 0-based index into 'joinkeys' of the first joinkey whose - * outer or inner pathkey matches any subkey of 'pathkey'. - * - * All these keys are equivalent, so any of them can match. See above. + * pathkeys_contained_in + * Common special case of compare_pathkeys: we just want to know + * if keys2 are at least as well sorted as keys1. */ -static int -match_pathkey_joinkeys(List *pathkey, - List *joinkeys, - int outer_or_inner) +bool +pathkeys_contained_in(List *keys1, List *keys2) { - Var *key; - int pos; - List *i, - *x; - JoinKey *jk; - - foreach(i, pathkey) + switch (compare_pathkeys(keys1, keys2)) { - key = (Var *) lfirst(i); - pos = 0; - foreach(x, joinkeys) - { - jk = (JoinKey *) lfirst(x); - if (equal(key, extract_join_key(jk, outer_or_inner))) - return pos; - pos++; - } + case PATHKEYS_EQUAL: + case PATHKEYS_BETTER2: + return true; + default: + break; } - return -1; /* no index found */ + return false; } - /* - * get_cheapest_path_for_joinkeys - * Attempts to find a path in 'paths' whose keys match a set of join - * keys 'joinkeys'. To match, - * 1. the path node ordering must equal 'ordering'. - * 2. each pathkey of a given path must match(i.e., be(equal) to) the - * appropriate pathkey of the corresponding join key in 'joinkeys', - * i.e., the Nth path key must match its pathkeys against the pathkey of - * the Nth join key in 'joinkeys'. - * - * 'joinkeys' is the list of key pairs to which the path keys must be - * matched - * 'ordering' is the ordering of the(outer) path to which 'joinkeys' - * must correspond - * 'paths' is a list of(inner) paths which are to be matched against - * each join key in 'joinkeys' - * 'outer_or_inner' is a flag that selects the desired pathkey of a join key - * in 'joinkeys' - * - * Find the cheapest path that matches the join keys + * get_cheapest_path_for_pathkeys + * Find the cheapest path in 'paths' that satisfies the given pathkeys. + * Return NULL if no such path. + * + * 'paths' is a list of possible paths (either inner or outer) + * 'pathkeys' represents a required ordering */ Path * -get_cheapest_path_for_joinkeys(List *joinkeys, - PathOrder *ordering, - List *paths, - int outer_or_inner) +get_cheapest_path_for_pathkeys(List *paths, List *pathkeys) { Path *matched_path = NULL; List *i; @@ -256,12 +264,8 @@ get_cheapest_path_for_joinkeys(List *joinkeys, foreach(i, paths) { Path *path = (Path *) lfirst(i); - int better_sort; - if (order_joinkeys_by_pathkeys(path->pathkeys, joinkeys, NIL, - outer_or_inner, NULL, NULL) && - pathorder_match(ordering, path->pathorder, &better_sort) && - better_sort == 0) + if (pathkeys_contained_in(pathkeys, path->pathkeys)) { if (matched_path == NULL || path->path_cost < matched_path->path_cost) @@ -271,78 +275,116 @@ get_cheapest_path_for_joinkeys(List *joinkeys, return matched_path; } +/**************************************************************************** + * NEW PATHKEY FORMATION + ****************************************************************************/ /* - * make_pathkeys_from_joinkeys - * Builds a pathkey list for a path by pulling one of the pathkeys from - * a list of join keys 'joinkeys' and then finding the var node in the - * target list 'tlist' that corresponds to that pathkey. - * - * 'joinkeys' is a list of join key pairs - * 'tlist' is a relation target list - * 'outer_or_inner' is a flag that selects the desired pathkey of a join key - * in 'joinkeys' - * - * Returns a list of pathkeys: ((tlvar1)(tlvar2)...(tlvarN)). - * It is a list of lists because of multi-key indexes. + * build_index_pathkeys + * Build a pathkeys list that describes the ordering induced by an index + * scan using the given index. (Note that an unordered index doesn't + * induce any ordering; such an index will have no sortop OIDS in + * its "ordering" field.) + * + * Vars in the resulting pathkeys list are taken from the rel's targetlist. + * If we can't find the indexkey in the targetlist, we assume that the + * ordering of that key is not interesting. */ List * -make_pathkeys_from_joinkeys(List *joinkeys, - List *tlist, - int outer_or_inner) +build_index_pathkeys(Query *root, RelOptInfo *rel, RelOptInfo *index) { - List *pathkeys = NIL; - List *jk; + List *retval = NIL; + int *indexkeys = index->indexkeys; + Oid *ordering = index->ordering; + + if (!indexkeys || indexkeys[0] == 0 || + !ordering || ordering[0] == InvalidOid) + return NIL; /* unordered index? */ - foreach(jk, joinkeys) + if (index->indproc) { - JoinKey *jkey = (JoinKey *) lfirst(jk); - Var *key; - List *p, - *p2; - bool found = false; + /* Functional index: build a representation of the function call */ + int relid = lfirsti(rel->relids); + Oid reloid = getrelid(relid, root->rtable); + Func *funcnode = makeNode(Func); + List *funcargs = NIL; + + funcnode->funcid = index->indproc; + funcnode->functype = get_func_rettype(index->indproc); + funcnode->funcisindex = false; + funcnode->funcsize = 0; + funcnode->func_fcache = NULL; + funcnode->func_tlist = NIL; + funcnode->func_planlist = NIL; + + while (*indexkeys != 0) + { + int varattno = *indexkeys; + Oid vartypeid = get_atttype(reloid, varattno); + int32 type_mod = get_atttypmod(reloid, varattno); + + funcargs = lappend(funcargs, + makeVar(relid, varattno, vartypeid, type_mod, + 0, relid, varattno)); + indexkeys++; + } - key = (Var *) extract_join_key(jkey, outer_or_inner); + /* Make a one-sublist pathkeys list for the function expression */ + retval = lcons(lcons( + makePathKeyItem((Node *) make_funcclause(funcnode, funcargs), + *ordering), + NIL), NIL); + } + else + { + /* Normal non-functional index */ + List *rel_tlist = rel->targetlist; - /* check to see if it is in the target list */ - if (matching_tlist_var(key, tlist)) + while (*indexkeys != 0 && *ordering != InvalidOid) { + Var *relvar = find_indexkey_var(*indexkeys, rel_tlist); - /* - * Include it in the pathkeys list if we haven't already done - * so + /* If we can find no tlist entry for the n'th sort key, + * then we're done generating pathkeys; any subsequent sort keys + * no longer apply, since we can't represent the ordering properly + * even if there are tlist entries for them. */ - foreach(p, pathkeys) - { - List *pathkey = lfirst(p); - - foreach(p2, pathkey) - { - Var *pkey = lfirst(p2); - - if (equal(key, pkey)) - { - found = true; - break; - } - } - if (found) - break; - } - if (!found) - pathkeys = lappend(pathkeys, lcons(key, NIL)); + if (!relvar) + break; + /* OK, make a one-element sublist for this sort key */ + retval = lappend(retval, + lcons(makePathKeyItem((Node *) relvar, + *ordering), + NIL)); + + indexkeys++; + ordering++; } } - return pathkeys; + + return retval; } +/* + * Find a var in a relation's targetlist that matches an indexkey attrnum. + */ +static Var * +find_indexkey_var(int indexkey, List *tlist) +{ + List *temp; -/**************************************************************************** - * NEW PATHKEY FORMATION - ****************************************************************************/ + foreach(temp, tlist) + { + Var *tle_var = get_expr(lfirst(temp)); + + if (IsA(tle_var, Var) && tle_var->varattno == indexkey) + return tle_var; + } + return NULL; +} /* - * new_join_pathkeys + * build_join_pathkeys * Build the path keys for a join relation constructed by mergejoin or * nestloop join. These keys should include all the path key vars of the * outer path (since the join will retain the ordering of the outer path) @@ -362,21 +404,26 @@ make_pathkeys_from_joinkeys(List *joinkeys, * the inner var will acquire the outer's ordering no matter which join * method is actually used. * - * All vars in the result are copied from the join relation's tlist, not from - * the given pathkeys or the join clauses. (Is that necessary? I suspect - * not --- tgl) + * We drop pathkeys that are not vars of the join relation's tlist, + * on the assumption that they are not interesting to higher levels. + * (Is this correct?? To support expression pathkeys we might want to + * check that all vars mentioned in the key are in the tlist, instead.) + * + * All vars in the result are taken from the join relation's tlist, + * not from the given pathkeys or joinclauses. * * 'outer_pathkeys' is the list of the outer path's path keys * 'join_rel_tlist' is the target list of the join relation - * 'joinclauses' is the list of mergejoinable join clauses + * 'joinclauses' is the list of mergejoinable clauses to consider (note this + * is a list of RestrictInfos, not just bare qual clauses); can be NIL * * Returns the list of new path keys. * */ List * -new_join_pathkeys(List *outer_pathkeys, - List *join_rel_tlist, - List *joinclauses) +build_join_pathkeys(List *outer_pathkeys, + List *join_rel_tlist, + List *joinclauses) { List *final_pathkeys = NIL; List *i; @@ -386,11 +433,11 @@ new_join_pathkeys(List *outer_pathkeys, List *outer_pathkey = lfirst(i); List *new_pathkey; - new_pathkey = new_join_pathkey(outer_pathkey, join_rel_tlist, - joinclauses); + new_pathkey = build_join_pathkey(outer_pathkey, join_rel_tlist, + joinclauses); /* if we can find no sortable vars for the n'th sort key, - * then we're done generating pathkeys; can't expect to order - * subsequent vars. Not clear that this can really happen. + * then we're done generating pathkeys; any subsequent sort keys + * no longer apply, since we can't represent the ordering properly. */ if (new_pathkey == NIL) break; @@ -400,25 +447,22 @@ new_join_pathkeys(List *outer_pathkeys, } /* - * new_join_pathkey + * build_join_pathkey * Generate an individual pathkey sublist, consisting of the outer vars * already mentioned in 'pathkey' plus any inner vars that are joined to * them (and thus can now also be considered path keys, per discussion * at the top of this file). * - * Note that each returned pathkey is the var node found in + * Note that each returned pathkey uses the var node found in * 'join_rel_tlist' rather than the input pathkey or joinclause var node. - * (Is this important?) Also, we return a fully copied list - * that does not share any subnodes with existing data structures. - * (Is that important, either?) - * - * Returns a new pathkey (list of pathkey variables). + * (Is this important?) * + * Returns a new pathkey (list of PathKeyItems). */ static List * -new_join_pathkey(List *pathkey, - List *join_rel_tlist, - List *joinclauses) +build_join_pathkey(List *pathkey, + List *join_rel_tlist, + List *joinclauses) { List *new_pathkey = NIL; List *i, @@ -426,27 +470,193 @@ new_join_pathkey(List *pathkey, foreach(i, pathkey) { - Var *key = (Var *) lfirst(i); + PathKeyItem *key = (PathKeyItem *) lfirst(i); Expr *tlist_key; - Assert(key); + Assert(key && IsA(key, PathKeyItem)); - tlist_key = matching_tlist_var(key, join_rel_tlist); - if (tlist_key && !member(tlist_key, new_pathkey)) - new_pathkey = lcons(copyObject(tlist_key), new_pathkey); + tlist_key = matching_tlist_var((Var *) key->key, join_rel_tlist); + if (tlist_key) + new_pathkey = lcons(makePathKeyItem((Node *) tlist_key, + key->sortop), + new_pathkey); foreach(j, joinclauses) { - Expr *joinclause = lfirst(j); - Expr *tlist_other_var; - - tlist_other_var = matching_tlist_var( - other_join_clause_var(key, joinclause), - join_rel_tlist); - if (tlist_other_var && !member(tlist_other_var, new_pathkey)) - new_pathkey = lcons(copyObject(tlist_other_var), new_pathkey); + RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j); + Expr *joinclause = restrictinfo->clause; + /* We assume the clause is a binary opclause... */ + Var *l = get_leftop(joinclause); + Var *r = get_rightop(joinclause); + Var *other_var = NULL; + Oid other_sortop = InvalidOid; + + if (var_equal((Var *) key->key, l)) + { + other_var = r; + other_sortop = restrictinfo->right_sortop; + } + else if (var_equal((Var *) key->key, r)) + { + other_var = l; + other_sortop = restrictinfo->left_sortop; + } + + if (other_var && other_sortop) + { + tlist_key = matching_tlist_var(other_var, join_rel_tlist); + if (tlist_key) + new_pathkey = lcons(makePathKeyItem((Node *) tlist_key, + other_sortop), + new_pathkey); + } } } return new_pathkey; } + +/**************************************************************************** + * PATHKEYS AND MERGECLAUSES + ****************************************************************************/ + +/* + * find_mergeclauses_for_pathkeys + * This routine attempts to find a set of mergeclauses that can be + * used with a specified ordering for one of the input relations. + * If successful, it returns a list of mergeclauses. + * + * 'pathkeys' is a pathkeys list showing the ordering of an input path. + * It doesn't matter whether it is for the inner or outer path. + * 'restrictinfos' is a list of mergejoinable restriction clauses for the + * join relation being formed. + * + * The result is NIL if no merge can be done, else a maximal list of + * usable mergeclauses (represented as a list of their restrictinfo nodes). + * + * XXX Ideally we ought to be considering context, ie what path orderings + * are available on the other side of the join, rather than just making + * an arbitrary choice among the mergeclause orders that will work for + * this side of the join. + */ +List * +find_mergeclauses_for_pathkeys(List *pathkeys, List *restrictinfos) +{ + List *mergeclauses = NIL; + List *i; + + foreach(i, pathkeys) + { + List *pathkey = lfirst(i); + RestrictInfo *matched_restrictinfo = NULL; + List *j; + + /* + * We can match any of the keys in this pathkey sublist, + * since they're all equivalent. And we can match against + * either left or right side of any mergejoin clause we haven't + * used yet. For the moment we use a dumb "greedy" algorithm + * with no backtracking. Is it worth being any smarter to + * make a longer list of usable mergeclauses? Probably not. + */ + foreach(j, pathkey) + { + PathKeyItem *keyitem = lfirst(j); + Var *keyvar = (Var *) keyitem->key; + List *k; + + if (! IsA(keyvar, Var)) + continue; /* for now, only Vars can be mergejoined */ + + foreach(k, restrictinfos) + { + RestrictInfo *restrictinfo = lfirst(k); + + Assert(restrictinfo->mergejoinoperator != InvalidOid); + + if ((var_equal(keyvar, get_leftop(restrictinfo->clause)) || + var_equal(keyvar, get_rightop(restrictinfo->clause))) && + ! member(restrictinfo, mergeclauses)) + { + matched_restrictinfo = restrictinfo; + break; + } + } + if (matched_restrictinfo) + break; + } + + /* + * If we didn't find a mergeclause, we're done --- any additional + * sort-key positions in the pathkeys are useless. (But we can + * still mergejoin if we found at least one mergeclause.) + */ + if (! matched_restrictinfo) + break; + /* + * If we did find a usable mergeclause for this sort-key position, + * add it to result list. + */ + mergeclauses = lappend(mergeclauses, matched_restrictinfo); + } + + return mergeclauses; +} + +/* + * make_pathkeys_for_mergeclauses + * Builds a pathkey list representing the explicit sort order that + * must be applied to a path in order to make it usable for the + * given mergeclauses. + * + * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses + * that will be used in a merge join. + * 'tlist' is a relation target list for either the inner or outer + * side of the proposed join rel. + * + * Returns a pathkeys list that can be applied to the indicated relation. + * + * Note that it is not this routine's job to decide whether sorting is + * actually needed for a particular input path. Assume a sort is necessary; + * just make the keys, eh? + */ +List * +make_pathkeys_for_mergeclauses(List *mergeclauses, List *tlist) +{ + List *pathkeys = NIL; + List *i; + + foreach(i, mergeclauses) + { + RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i); + Var *key; + Oid sortop; + + /* + * Find the key and sortop needed for this mergeclause. + * + * We can use either side of the mergeclause, since we haven't yet + * committed to which side will be inner. + */ + Assert(restrictinfo->mergejoinoperator != InvalidOid); + key = (Var *) matching_tlist_var(get_leftop(restrictinfo->clause), + tlist); + sortop = restrictinfo->left_sortop; + if (! key) + { + key = (Var *) matching_tlist_var(get_rightop(restrictinfo->clause), + tlist); + sortop = restrictinfo->right_sortop; + } + if (! key) + elog(ERROR, "make_pathkeys_for_mergeclauses: can't find key"); + /* + * Add a pathkey sublist for this sort item + */ + pathkeys = lappend(pathkeys, + lcons(makePathKeyItem((Node *) key, sortop), + NIL)); + } + + return pathkeys; +} diff --git a/src/backend/optimizer/path/prune.c b/src/backend/optimizer/path/prune.c index 5b032491600..33fb67bc573 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.42 1999/07/16 04:59:16 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/prune.c,v 1.43 1999/08/16 02:17:52 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -18,17 +18,15 @@ #include "optimizer/pathnode.h" #include "optimizer/paths.h" - - -static List *merge_rel_with_same_relids(RelOptInfo *rel, Relids unjoined_relids); +static List *merge_rel_with_same_relids(RelOptInfo *rel, List *unmerged_rels); /* * merge_rels_with_same_relids * Removes any redundant relation entries from a list of rel nodes - * 'rel_list'. Obviously, the first relation can't be a duplicate. + * 'rel_list', merging their pathlists into the first non-duplicate + * relation entry for each value of relids. * * Returns the resulting list. - * */ void merge_rels_with_same_relids(List *rel_list) @@ -37,17 +35,21 @@ merge_rels_with_same_relids(List *rel_list) /* * rel_list can shorten while running as duplicate relations are - * deleted + * deleted. Obviously, the first relation can't be a duplicate, + * so the list head pointer won't change. */ foreach(i, rel_list) - lnext(i) = merge_rel_with_same_relids((RelOptInfo *) lfirst(i), lnext(i)); + { + lnext(i) = merge_rel_with_same_relids((RelOptInfo *) lfirst(i), + lnext(i)); + } } /* * merge_rel_with_same_relids - * Prunes those relations from 'unjoined_relids' that are redundant with + * Prunes those relations from 'unmerged_rels' that are redundant with * 'rel'. A relation is redundant if it is built up of the same - * relations as 'rel'. Paths for the redundant relation are merged into + * relations as 'rel'. Paths for the redundant relations are merged into * the pathlist of 'rel'. * * Returns a list of non-redundant relations, and sets the pathlist field @@ -55,50 +57,52 @@ merge_rels_with_same_relids(List *rel_list) * */ static List * -merge_rel_with_same_relids(RelOptInfo *rel, Relids unjoined_relids) +merge_rel_with_same_relids(RelOptInfo *rel, List *unmerged_rels) { - List *i = NIL; List *result = NIL; + List *i; - foreach(i, unjoined_relids) + foreach(i, unmerged_rels) { - RelOptInfo *unjoined_rel = (RelOptInfo *) lfirst(i); - - if (same(rel->relids, unjoined_rel->relids)) + RelOptInfo *unmerged_rel = (RelOptInfo *) lfirst(i); + if (same(rel->relids, unmerged_rel->relids)) + { /* - * This are on the same relations, so get the best of their - * pathlists. + * These rels are for the same set of base relations, + * so get the best of their pathlists. We assume it's + * ok to reassign a path to the other RelOptInfo without + * doing more than changing its parent pointer (cf. pathnode.c). */ rel->pathlist = add_pathlist(rel, rel->pathlist, - unjoined_rel->pathlist); + unmerged_rel->pathlist); + } else - result = lappend(result, unjoined_rel); + result = lappend(result, unmerged_rel); } return result; } /* * rels_set_cheapest - * For each relation entry in 'rel_list' (which corresponds to a join - * relation), set pointers to the cheapest path + * For each relation entry in 'rel_list' (which should contain only join + * relations), set pointers to the cheapest path and compute rel size. */ void rels_set_cheapest(List *rel_list) { - List *x = NIL; - RelOptInfo *rel = (RelOptInfo *) NULL; - JoinPath *cheapest; + List *x; foreach(x, rel_list) { - rel = (RelOptInfo *) lfirst(x); + RelOptInfo *rel = (RelOptInfo *) lfirst(x); + JoinPath *cheapest; cheapest = (JoinPath *) set_cheapest(rel, rel->pathlist); if (IsA_JoinPath(cheapest)) rel->size = compute_joinrel_size(cheapest); else - elog(ERROR, "non JoinPath called"); + elog(ERROR, "rels_set_cheapest: non JoinPath found"); } } diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 281e3685160..17f98389a8e 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.70 1999/08/12 04:32:53 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.71 1999/08/16 02:17:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -27,12 +27,8 @@ #include "utils/syscache.h" -#define NONAME_SORT 1 -#define NONAME_MATERIAL 2 - static List *switch_outer(List *clauses); -static Oid *generate_merge_input_sortorder(List *pathkeys, - MergeOrder *mergeorder); +static List *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 SeqScan *create_seqscan_node(Path *best_path, List *tlist, @@ -53,8 +49,7 @@ static List *fix_indxqual_sublist(List *indexqual, IndexPath *index_path, Form_pg_index index); static Node *fix_indxqual_operand(Node *node, IndexPath *index_path, Form_pg_index index); -static Noname *make_noname(List *tlist, List *pathkeys, Oid *operators, - Plan *plan_node, int nonametype); +static Noname *make_noname(List *tlist, List *pathkeys, Plan *plan_node); static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid, List *indxid, List *indxqual, List *indxqualorig); static NestLoop *make_nestloop(List *qptlist, List *qpqual, Plan *lefttree, @@ -482,9 +477,7 @@ create_nestloop_node(NestPath *best_path, /* Materialize the inner join for speed reasons */ inner_node = (Plan *) make_noname(inner_tlist, NIL, - NULL, - inner_node, - NONAME_MATERIAL); + inner_node); } join_node = make_nestloop(tlist, @@ -531,34 +524,18 @@ create_mergejoin_node(MergePath *best_path, inner_tlist)); /* - * Create explicit sort paths for the outer and inner join paths if + * Create explicit sort nodes for the outer and inner join paths if * necessary. The sort cost was already accounted for in the path. */ if (best_path->outersortkeys) - { - Oid *outer_order = generate_merge_input_sortorder( - best_path->outersortkeys, - best_path->jpath.path.pathorder->ord.merge); - outer_node = (Plan *) make_noname(outer_tlist, best_path->outersortkeys, - outer_order, - outer_node, - NONAME_SORT); - } + outer_node); if (best_path->innersortkeys) - { - Oid *inner_order = generate_merge_input_sortorder( - best_path->innersortkeys, - best_path->jpath.path.pathorder->ord.merge); - inner_node = (Plan *) make_noname(inner_tlist, best_path->innersortkeys, - inner_order, - inner_node, - NONAME_SORT); - } + inner_node); join_node = make_mergejoin(tlist, qpqual, @@ -589,7 +566,7 @@ create_hashjoin_node(HashPath *best_path, /* * NOTE: there will always be exactly one hashclause in the list * best_path->path_hashclauses (cf. hash_inner_and_outer()). - * We represent it as a list anyway for convenience with routines + * We represent it as a list anyway, for convenience with routines * that want to work on lists of clauses. */ @@ -782,9 +759,9 @@ fix_indxqual_operand(Node *node, IndexPath *index_path, /* * switch_outer - * Given a list of merge clauses, rearranges the elements within the - * clauses so the outer join variable is on the left and the inner is on - * the right. The original list is not touched; a modified list + * Given a list of merge or hash joinclauses, rearrange the elements within + * the clauses so the outer join variable is on the left and the inner is + * on the right. The original list is not touched; a modified list * is returned. */ static List * @@ -796,15 +773,12 @@ switch_outer(List *clauses) foreach(i, clauses) { Expr *clause = (Expr *) lfirst(i); - Node *op; + Var *op; Assert(is_opclause((Node *) clause)); - op = (Node *) get_rightop(clause); - Assert(op != (Node *) NULL); - if (IsA(op, ArrayRef)) /* I think this test is dead code ... tgl */ - op = ((ArrayRef *) op)->refexpr; - Assert(IsA(op, Var)); - if (var_is_outer((Var *) op)) + op = get_rightop(clause); + Assert(op && IsA(op, Var)); + if (var_is_outer(op)) { /* * Duplicate just enough of the structure to allow commuting @@ -826,80 +800,42 @@ switch_outer(List *clauses) } /* - * generate_merge_input_sortorder - * - * Generate the list of sort ops needed to sort one of the input paths for - * a merge. We may have to use either left or right sortop for each item, - * since the original mergejoin clause may or may not have been commuted - * (compare switch_outer above). - * - * XXX This is largely a crock. It works only because group_clauses_by_order - * only groups together mergejoin clauses that have identical MergeOrder info, - * which means we can safely use a single MergeOrder input to deal with all - * the data. There should be a more general data structure that allows coping - * with groups of mergejoin clauses that have different join operators. - */ -static Oid * -generate_merge_input_sortorder(List *pathkeys, MergeOrder *mergeorder) -{ - int listlength = length(pathkeys); - Oid *result = (Oid *) palloc(sizeof(Oid) * (listlength + 1)); - Oid *nextsortop = result; - List *p; - - foreach(p, pathkeys) - { - Var *pkey = (Var *) lfirst((List *) lfirst(p)); - - Assert(IsA(pkey, Var)); - if (pkey->vartype == mergeorder->left_type) - *nextsortop++ = mergeorder->left_operator; - else if (pkey->vartype == mergeorder->right_type) - *nextsortop++ = mergeorder->right_operator; - else - elog(ERROR, - "generate_merge_input_sortorder: can't handle data type %d", - pkey->vartype); - } - *nextsortop++ = InvalidOid; - return result; -} - -/* - * set_noname_tlist_operators - * Sets the key and keyop fields of resdom nodes in a target list. + * set_tlist_sort_info + * Sets the reskey and reskeyop fields of resdom nodes in a target list + * for a sort node. * - * 'tlist' is the target list - * 'pathkeys' is a list of N keys in the form((key1) (key2)...(keyn)), - * corresponding to vars in the target list that are to - * be sorted or hashed - * 'operators' is the corresponding list of N sort or hash operators + * 'tlist' is the target list + * 'pathkeys' is the desired pathkeys for the sort. NIL means no sort. * - * Returns the modified-in-place target list. + * Returns the modified-in-place target list. */ static List * -set_noname_tlist_operators(List *tlist, List *pathkeys, Oid *operators) +set_tlist_sort_info(List *tlist, List *pathkeys) { int keyno = 1; - Node *pathkey; - Resdom *resdom; List *i; foreach(i, pathkeys) { - pathkey = lfirst((List *) lfirst(i)); - resdom = tlist_member((Var *) pathkey, tlist); - if (resdom) - { + List *keysublist = (List *) lfirst(i); + PathKeyItem *pathkey; + Resdom *resdom; - /* - * Order the resdom pathkey and replace the operator OID for - * each key with the regproc OID. - */ - resdom->reskey = keyno; - resdom->reskeyop = get_opcode(operators[keyno - 1]); - } - keyno += 1; + /* + * We can sort by any one of the sort key items listed in this + * sublist. For now, we always take the first one --- is there + * any way of figuring out which might be cheapest to execute? + * (For example, int4lt is likely much cheaper to execute than + * numericlt, but both might appear in the same pathkey sublist...) + */ + pathkey = lfirst(keysublist); + Assert(IsA(pathkey, PathKeyItem)); + resdom = tlist_member((Var *) pathkey->key, tlist); + if (!resdom) + elog(ERROR, "set_tlist_sort_info: cannot find tlist item to sort"); + resdom->reskey = keyno; + resdom->reskeyop = get_opcode(pathkey->sortop); + keyno++; } return tlist; } @@ -909,7 +845,6 @@ set_noname_tlist_operators(List *tlist, List *pathkeys, Oid *operators) * 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) { @@ -939,52 +874,44 @@ copy_costsize(Plan *dest, Plan *src) * result returned for a sort will look like (SEQSCAN(SORT(plan_node))) * or (SEQSCAN(MATERIAL(plan_node))) * - * 'tlist' is the target list of the scan to be sorted or hashed - * 'pathkeys' is the list of keys which the sort or hash will be done on - * 'operators' is the operators with which the sort or hash is to be done - * (a list of operator OIDs) - * 'plan_node' is the node which yields tuples for the sort - * 'nonametype' indicates which operation(sort or hash) to perform + * 'tlist' is the target list of the scan to be sorted or materialized + * 'pathkeys' is the list of pathkeys by which the result is to be sorted + * (NIL implies no sort needed, just materialize it) + * 'plan_node' is the node which yields input tuples */ static Noname * make_noname(List *tlist, List *pathkeys, - Oid *operators, - Plan *plan_node, - int nonametype) + Plan *plan_node) { List *noname_tlist; - Noname *retval = NULL; + Noname *retval; - /* Create a new target list for the noname, with keys set. */ - noname_tlist = set_noname_tlist_operators(new_unsorted_tlist(tlist), - pathkeys, - operators); - switch (nonametype) + /* Create a new target list for the noname, with sort keys set. */ + noname_tlist = set_tlist_sort_info(new_unsorted_tlist(tlist), + pathkeys); + + if (pathkeys != NIL) { - case NONAME_SORT: - retval = (Noname *) make_seqscan(tlist, - NIL, - _NONAME_RELATION_ID_, + /* need to sort */ + retval = (Noname *) make_seqscan(tlist, + NIL, + _NONAME_RELATION_ID_, (Plan *) make_sort(noname_tlist, _NONAME_RELATION_ID_, plan_node, - length(pathkeys))); - break; - - case NONAME_MATERIAL: - retval = (Noname *) make_seqscan(tlist, - NIL, - _NONAME_RELATION_ID_, - (Plan *) make_material(noname_tlist, + length(pathkeys))); + } + else + { + /* no sort */ + retval = (Noname *) make_seqscan(tlist, + NIL, + _NONAME_RELATION_ID_, + (Plan *) make_material(noname_tlist, _NONAME_RELATION_ID_, - plan_node, - length(pathkeys))); - break; - - default: - elog(ERROR, "make_noname: unknown noname type %d", nonametype); - + plan_node, + 0)); } return retval; } diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c index 1971ccb9282..db97c732070 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.36 1999/08/10 03:00:14 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.37 1999/08/16 02:17:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -28,11 +28,10 @@ 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); + Relids join_relids); static void add_vars_to_targetlist(Query *root, List *vars); - -static MergeOrder *mergejoinop(Expr *clause); -static Oid hashjoinop(Expr *clause); +static void check_mergejoinable(RestrictInfo *restrictinfo); +static void check_hashjoinable(RestrictInfo *restrictinfo); /***************************************************************************** @@ -123,8 +122,8 @@ add_missing_vars_to_tlist(Query *root, List *tlist) /* - * add_restrict_and_join_to_rels- - * Initializes RestrictInfo and JoinInfo fields of relation entries for all + * add_restrict_and_join_to_rels + * Fill RestrictInfo and JoinInfo lists of relation entries for all * relations appearing within clauses. Creates new relation entries if * necessary, adding them to *query_relation_list*. * @@ -140,11 +139,11 @@ add_restrict_and_join_to_rels(Query *root, List *clauses) } /* - * add_restrict_and_join_to_rel- + * add_restrict_and_join_to_rel * Add clause information to either the 'RestrictInfo' or 'JoinInfo' field - * of a relation entry (depending on whether or not the clause is a join) - * by creating a new RestrictInfo node and setting appropriate fields - * within the nodes. + * (depending on whether the clause is a join) of each base relation + * mentioned in the clause. A RestrictInfo node is created and added to + * the appropriate list for each rel. */ static void add_restrict_and_join_to_rel(Query *root, Node *clause) @@ -154,9 +153,11 @@ add_restrict_and_join_to_rel(Query *root, Node *clause) List *vars; restrictinfo->clause = (Expr *) clause; - restrictinfo->indexids = NIL; - restrictinfo->mergejoinorder = (MergeOrder *) NULL; - restrictinfo->hashjoinoperator = (Oid) 0; + restrictinfo->subclauseindices = NIL; + restrictinfo->mergejoinoperator = InvalidOid; + restrictinfo->left_sortop = InvalidOid; + restrictinfo->right_sortop = InvalidOid; + restrictinfo->hashjoinoperator = InvalidOid; /* * The selectivity of the clause must be computed regardless of @@ -196,7 +197,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 node (creating a new one and adding it to the + * the appropriate joininfo list (creating a new one and adding it to the * appropriate rel node if necessary). * * 'restrictinfo' describes the join clause @@ -211,21 +212,22 @@ add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo, /* For every relid, find the joininfo, and add the proper join entries */ foreach(join_relid, join_relids) { + int cur_relid = lfirsti(join_relid); JoinInfo *joininfo; Relids unjoined_relids = NIL; - List *rel; + List *otherrel; /* Get the relids not equal to the current relid */ - foreach(rel, join_relids) + foreach(otherrel, join_relids) { - if (lfirsti(rel) != lfirsti(join_relid)) - unjoined_relids = lappendi(unjoined_relids, lfirsti(rel)); + if (lfirsti(otherrel) != cur_relid) + unjoined_relids = lappendi(unjoined_relids, lfirsti(otherrel)); } /* * Find or make the joininfo node for this combination of rels */ - joininfo = find_joininfo_node(get_base_rel(root, lfirsti(join_relid)), + joininfo = find_joininfo_node(get_base_rel(root, cur_relid), unjoined_relids); /* @@ -247,12 +249,8 @@ add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo, /* * set_joininfo_mergeable_hashable - * Set the MergeJoinable or HashJoinable field for every joininfo node - * (within a rel node) and the mergejoinorder or hashjoinop field for - * each restrictinfo node (within a joininfo node) for all relations in a - * query. - * - * Returns nothing. + * Examine each join clause used in a query and set the merge and hash + * info fields in those that are mergejoinable or hashjoinable. */ void set_joininfo_mergeable_hashable(List *rel_list) @@ -272,111 +270,102 @@ set_joininfo_mergeable_hashable(List *rel_list) foreach(z, joininfo->jinfo_restrictinfo) { RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(z); - Expr *clause = restrictinfo->clause; - - if (is_joinable((Node *) clause)) - { - if (_enable_mergejoin_) - { - MergeOrder *sortop = mergejoinop(clause); - if (sortop) - { - restrictinfo->mergejoinorder = sortop; - joininfo->mergejoinable = true; - } - } - - if (_enable_hashjoin_) - { - Oid hashop = hashjoinop(clause); - if (hashop) - { - restrictinfo->hashjoinoperator = hashop; - joininfo->hashjoinable = true; - } - } - } + + if (_enable_mergejoin_) + check_mergejoinable(restrictinfo); + if (_enable_hashjoin_) + check_hashjoinable(restrictinfo); } } } } /* - * mergejoinop - * Returns a MergeOrder node for 'clause' iff 'clause' is mergejoinable, - * i.e., both operands are single vars and the operator is - * a mergejoinable operator. + * check_mergejoinable + * If the restrictinfo's clause is mergejoinable, set the mergejoin + * info fields in the restrictinfo. + * + * Currently, we support mergejoin for binary opclauses where + * both operands are simple Vars and the operator is a mergejoinable + * operator. (Note: since we are only examining clauses that were + * classified as joins, it is certain that the two Vars belong to + * different relations... if we accepted more general clause structures + * we might need to check that the two sides refer to different rels...) */ -static MergeOrder * -mergejoinop(Expr *clause) +static void +check_mergejoinable(RestrictInfo *restrictinfo) { + Expr *clause = restrictinfo->clause; Var *left, *right; Oid opno, leftOp, rightOp; - bool sortable; - if (!is_opclause((Node *) clause)) - return NULL; + if (! is_opclause((Node *) clause)) + return; left = get_leftop(clause); right = get_rightop(clause); /* caution: is_opclause accepts more than I do, so check it */ - if (!right) - return NULL; /* unary opclauses need not apply */ + if (! right) + return; /* unary opclauses need not apply */ if (!IsA(left, Var) || !IsA(right, Var)) - return NULL; + return; opno = ((Oper *) clause->oper)->opno; - sortable = op_mergejoinable(opno, - left->vartype, - right->vartype, - &leftOp, - &rightOp); - - if (sortable) + if (op_mergejoinable(opno, + left->vartype, + right->vartype, + &leftOp, + &rightOp)) { - MergeOrder *morder = makeNode(MergeOrder); - - morder->join_operator = opno; - morder->left_operator = leftOp; - morder->right_operator = rightOp; - morder->left_type = left->vartype; - morder->right_type = right->vartype; - return morder; + restrictinfo->mergejoinoperator = opno; + restrictinfo->left_sortop = leftOp; + restrictinfo->right_sortop = rightOp; } - else - return NULL; } /* - * hashjoinop - * Returns the hashjoin operator iff 'clause' is hashjoinable, - * i.e., both operands are single vars and the operator is - * a hashjoinable operator. + * check_hashjoinable + * If the restrictinfo's clause is hashjoinable, set the hashjoin + * info fields in the restrictinfo. + * + * Currently, we support hashjoin for binary opclauses where + * both operands are simple Vars and the operator is a hashjoinable + * operator. (Note: since we are only examining clauses that were + * classified as joins, it is certain that the two Vars belong to + * different relations... if we accepted more general clause structures + * we might need to check that the two sides refer to different rels...) */ -static Oid -hashjoinop(Expr *clause) +static void +check_hashjoinable(RestrictInfo *restrictinfo) { + Expr *clause = restrictinfo->clause; Var *left, *right; + Oid opno; - if (!is_opclause((Node *) clause)) - return InvalidOid; + if (! is_opclause((Node *) clause)) + return; left = get_leftop(clause); right = get_rightop(clause); /* caution: is_opclause accepts more than I do, so check it */ - if (!right) - return InvalidOid; /* unary opclauses need not apply */ + if (! right) + return; /* unary opclauses need not apply */ if (!IsA(left, Var) || !IsA(right, Var)) - return InvalidOid; + return; + + opno = ((Oper *) clause->oper)->opno; - return op_hashjoinable(((Oper *) clause->oper)->opno, - left->vartype, - right->vartype); + if (op_hashjoinable(opno, + left->vartype, + right->vartype)) + { + restrictinfo->hashjoinoperator = opno; + } } diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c index 931faabe13f..21afad92b82 100644 --- a/src/backend/optimizer/prep/prepunion.c +++ b/src/backend/optimizer/prep/prepunion.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepunion.c,v 1.37 1999/07/17 20:17:17 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepunion.c,v 1.38 1999/08/16 02:17:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -318,34 +318,29 @@ find_all_inheritors(Relids unexamined_relids, Relids examined_relids) { List *new_inheritors = NIL; - List *new_examined_relids = NIL; - List *new_unexamined_relids = NIL; + List *new_examined_relids; + List *new_unexamined_relids; + List *rels; /* * Find all relations which inherit from members of * 'unexamined_relids' and store them in 'new_inheritors'. */ - List *rels = NIL; - List *newrels = NIL; - foreach(rels, unexamined_relids) { - newrels = (List *) LispUnioni(find_inheritance_children(lfirsti(rels)), - newrels); + new_inheritors = LispUnioni(new_inheritors, + find_inheritance_children(lfirsti(rels))); } - new_inheritors = newrels; - new_examined_relids = (List *) LispUnioni(examined_relids, unexamined_relids); + new_examined_relids = LispUnioni(examined_relids, unexamined_relids); new_unexamined_relids = set_differencei(new_inheritors, new_examined_relids); - if (new_unexamined_relids == NULL) + if (new_unexamined_relids == NIL) return new_examined_relids; else - { - return (find_all_inheritors(new_unexamined_relids, - new_examined_relids)); - } + return find_all_inheritors(new_unexamined_relids, + new_examined_relids); } /* diff --git a/src/backend/optimizer/util/Makefile b/src/backend/optimizer/util/Makefile index f28457497f0..f221e87b013 100644 --- a/src/backend/optimizer/util/Makefile +++ b/src/backend/optimizer/util/Makefile @@ -4,7 +4,7 @@ # Makefile for optimizer/util # # IDENTIFICATION -# $Header: /cvsroot/pgsql/src/backend/optimizer/util/Makefile,v 1.8 1999/02/05 19:59:28 momjian Exp $ +# $Header: /cvsroot/pgsql/src/backend/optimizer/util/Makefile,v 1.9 1999/08/16 02:17:56 tgl Exp $ # #------------------------------------------------------------------------- @@ -14,7 +14,7 @@ include ../../../Makefile.global CFLAGS += -I../.. OBJS = restrictinfo.o clauses.o indexnode.o plancat.o \ - joininfo.o keys.o ordering.o pathnode.o relnode.o tlist.o var.o + joininfo.o pathnode.o relnode.o tlist.o var.o # not ready yet: predmig.o xfunc.o diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c index f9906cffc04..ca4353f6085 100644 --- a/src/backend/optimizer/util/clauses.c +++ b/src/backend/optimizer/util/clauses.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.46 1999/08/12 04:32:54 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.47 1999/08/16 02:17:56 tgl Exp $ * * HISTORY * AUTHOR DATE MAJOR EVENT @@ -164,7 +164,7 @@ make_funcclause(Func *func, List *funcargs) { Expr *expr = makeNode(Expr); - expr->typeOid = InvalidOid; /* assume type checking done */ + expr->typeOid = func->functype; expr->opType = FUNC_EXPR; expr->oper = (Node *) func; expr->args = funcargs; @@ -417,43 +417,6 @@ NumRelids(Node *clause) } /* - * is_joinable - * - * Returns t iff 'clause' is a valid join clause. - * - */ -bool -is_joinable(Node *clause) -{ - Node *leftop, - *rightop; - - if (!is_opclause(clause)) - return false; - - leftop = (Node *) get_leftop((Expr *) clause); - rightop = (Node *) get_rightop((Expr *) clause); - - if (!rightop) - return false; /* unary opclauses need not apply */ - - /* - * One side of the clause (i.e. left or right operands) must either be - * a var node ... - */ - if (IsA(leftop, Var) || IsA(rightop, Var)) - return true; - - /* - * ... or a func node. - */ - if (is_funcclause(leftop) || is_funcclause(rightop)) - return true; - - return false; -} - -/* * fix_opids * Calculate opid field from opno for each Oper node in given tree. * (The given tree can be anything expression_tree_walker handles.) diff --git a/src/backend/optimizer/util/indexnode.c b/src/backend/optimizer/util/indexnode.c index 6d175d6c036..4817232f2fb 100644 --- a/src/backend/optimizer/util/indexnode.c +++ b/src/backend/optimizer/util/indexnode.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/indexnode.c,v 1.19 1999/07/16 04:59:24 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/indexnode.c,v 1.20 1999/08/16 02:17:57 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -39,21 +39,20 @@ find_relation_indices(Query *root, RelOptInfo *rel) /* * find_secondary_index - * Creates a list of index path nodes containing information for each + * Creates a list of RelOptInfo nodes containing information for each * secondary index defined on a relation by searching through the index * catalog. * * 'relid' is the OID of the relation for which indices are being located * - * Returns a list of new index nodes. - * + * Returns a list of new index RelOptInfo nodes. */ static List * find_secondary_index(Query *root, Oid relid) { IdxInfoRetval indexinfo; List *indexes = NIL; - bool first = TRUE; + bool first = true; while (index_info(root, first, relid, &indexinfo)) { @@ -63,9 +62,9 @@ find_secondary_index(Query *root, Oid relid) indexnode->relam = indexinfo.relam; indexnode->pages = indexinfo.pages; indexnode->tuples = indexinfo.tuples; + indexnode->classlist = indexinfo.classlist; indexnode->indexkeys = indexinfo.indexkeys; indexnode->ordering = indexinfo.orderOprs; - indexnode->classlist = indexinfo.classlist; indexnode->indproc = indexinfo.indproc; indexnode->indpred = (List *) indexinfo.indpred; @@ -81,7 +80,7 @@ find_secondary_index(Query *root, Oid relid) indexnode->innerjoin = NIL; indexes = lcons(indexnode, indexes); - first = FALSE; + first = false; } return indexes; diff --git a/src/backend/optimizer/util/joininfo.c b/src/backend/optimizer/util/joininfo.c index 3420313c98c..13d1f6b9fb2 100644 --- a/src/backend/optimizer/util/joininfo.c +++ b/src/backend/optimizer/util/joininfo.c @@ -7,14 +7,13 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/joininfo.c,v 1.23 1999/07/16 04:59:25 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/joininfo.c,v 1.24 1999/08/16 02:17:57 tgl Exp $ * *------------------------------------------------------------------------- */ #include "postgres.h" -#include "optimizer/clauses.h" #include "optimizer/joininfo.h" @@ -51,8 +50,8 @@ joininfo_member(List *join_relids, List *joininfo_list) /* * find_joininfo_node * Find the joininfo node within a relation entry corresponding - * to a join between 'this_rel' and the relations in 'join_relids'. A - * new node is created and added to the relation entry's joininfo + * to a join between 'this_rel' and the relations in 'join_relids'. + * A new node is created and added to the relation entry's joininfo * field if the desired one can't be found. * * Returns a joininfo node. @@ -69,40 +68,7 @@ find_joininfo_node(RelOptInfo *this_rel, Relids join_relids) joininfo = makeNode(JoinInfo); joininfo->unjoined_relids = join_relids; joininfo->jinfo_restrictinfo = NIL; - joininfo->mergejoinable = false; - joininfo->hashjoinable = false; this_rel->joininfo = lcons(joininfo, this_rel->joininfo); } return joininfo; } - -/* - * other_join_clause_var - * Determines whether a var node is contained within a joinclause - * of the form(op var var). - * - * Returns the other var node in the joinclause if it is, nil if not. - * - */ -Var * -other_join_clause_var(Var *var, Expr *clause) -{ - Var *retval; - Var *l, - *r; - - retval = (Var *) NULL; - - if (var != NULL && is_joinable((Node *) clause)) - { - l = (Var *) get_leftop(clause); - r = (Var *) get_rightop(clause); - - if (equal(var, l)) - retval = r; - else if (equal(var, r)) - retval = l; - } - - return retval; -} diff --git a/src/backend/optimizer/util/keys.c b/src/backend/optimizer/util/keys.c deleted file mode 100644 index c9a5a9b5ea9..00000000000 --- a/src/backend/optimizer/util/keys.c +++ /dev/null @@ -1,237 +0,0 @@ -/*------------------------------------------------------------------------- - * - * keys.c - * Key manipulation routines - * - * Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/keys.c,v 1.23 1999/07/15 22:39:31 momjian Exp $ - * - *------------------------------------------------------------------------- - */ -#include "postgres.h" - -#include "optimizer/keys.h" - - -static Expr *matching2_tlvar(int var, List *tlist, bool (*test) ()); -static bool equal_indexkey_var(int index_key, Var *var); - -/* - * 1. index key - * one of: - * attnum - * (attnum arrayindex) - * 2. path key - * (subkey1 ... subkeyN) - * where subkeyI is a var node - * note that the 'Keys field is a list of these - * 3. join key - * (outer_subkey inner_subkey) - * where each subkey is a var node - * 4. sort key - * one of: - * SortKey node - * number - * nil - * (may also refer to the 'SortKey field of a SortKey node, - * which looks exactly like an index key) - * - */ - -/* - * match_indexkey_operand - * Returns t iff an index key 'index_key' matches the given clause - * operand. - * - */ -bool -match_indexkey_operand(int indexkey, Var *operand, RelOptInfo *rel) -{ - if (IsA(operand, Var) && - (lfirsti(rel->relids) == operand->varno) && - equal_indexkey_var(indexkey, operand)) - return true; - else - return false; -} - -/* - * equal_indexkey_var - * Returns t iff an index key 'index_key' matches the corresponding - * fields of var node 'var'. - * - */ -static bool -equal_indexkey_var(int index_key, Var *var) -{ - if (index_key == var->varattno) - return true; - else - return false; -} - -/* - * extract_join_key - * Returns the subkey in a join key corresponding to the outer or inner - * relation. - * - */ -Var * -extract_join_key(JoinKey *jk, int outer_or_inner) -{ - Var *retval; - - switch (outer_or_inner) - { - case OUTER: - retval = jk->outer; - break; - case INNER: - retval = jk->inner; - break; - default: /* do nothing */ - elog(DEBUG, "extract_join_key with neither INNER or OUTER"); - retval = NULL; - } - return retval; -} - -/* - * pathkeys_match - * Returns t iff two sets of path keys are equivalent. They are - * equivalent if the first Var nodes match the second Var nodes. - * - * See the top of optimizer/path/pathkeys.c for a description of pathkeys. - * Each pathkey is ordered by its join order, so they not pre-ordered to - * match. We must search them ourselves. - * - * This gets called a lot, so it is optimized. - */ -bool -pathkeys_match(List *keys1, List *keys2, int *better_key) -{ - List *key1, - *key2; - bool key1_subsetof_key2 = true, - key2_subsetof_key1 = true; - - for (key1 = keys1, key2 = keys2; - key1 != NIL && key2 != NIL; - key1 = lnext(key1), key2 = lnext(key2)) - { - List *i; - - if (key1_subsetof_key2) - foreach(i, lfirst(key1)) - { - Var *subkey = lfirst(i); - - if (!member(subkey, lfirst(key2))) - { - key1_subsetof_key2 = false; - break; - } - } - - if (key2_subsetof_key1) - foreach(i, lfirst(key2)) - { - Var *subkey = lfirst(i); - - if (!member(subkey, lfirst(key1))) - { - key2_subsetof_key1 = false; - break; - } - } - if (!key1_subsetof_key2 && !key2_subsetof_key1) - break; /* no need to continue comparisons. */ - } - - if (!key1_subsetof_key2 && !key2_subsetof_key1) - { - *better_key = 0; - return false; - } - if (key1_subsetof_key2 && !key2_subsetof_key1) - { - *better_key = 2; - return true; - } - if (!key1_subsetof_key2 && key2_subsetof_key1) - { - *better_key = 1; - return true; - } - - *better_key = 0; - return true; - -} - -/* - * collect_index_pathkeys - * Creates a list of subkeys by retrieving var nodes corresponding to - * each index key in 'index_keys' from the relation's target list - * 'tlist'. If the key is not in the target list, the key is irrelevant - * and is thrown away. The returned subkey list is of the form: - * ((var1) (var2) ... (varn)) - * - * 'index_keys' is a list of index keys - * 'tlist' is a relation target list - * - * Returns the list of cons'd subkeys. - * - */ -/* This function is identical to matching_tlvar and tlistentry_member. - * They should be merged. - */ -static Expr * -matching2_tlvar(int var, List *tlist, bool (*test) ()) -{ - TargetEntry *tlentry = NULL; - - if (var) - { - List *temp; - - foreach(temp, tlist) - { - if ((*test) (var, get_expr(lfirst(temp)))) - { - tlentry = lfirst(temp); - break; - } - } - } - - if (tlentry) - return (Expr *) get_expr(tlentry); - else - return (Expr *) NULL; -} - - -List * -collect_index_pathkeys(int *index_keys, List *tlist) -{ - List *retval = NIL; - - Assert(index_keys != NULL); - - while (index_keys[0] != 0) - { - Expr *mvar; - - mvar = matching2_tlvar(index_keys[0], - tlist, - equal_indexkey_var); - if (mvar) - retval = lappend(retval, lcons(mvar, NIL)); - index_keys++; - } - return retval; -} diff --git a/src/backend/optimizer/util/ordering.c b/src/backend/optimizer/util/ordering.c deleted file mode 100644 index 19d9b594537..00000000000 --- a/src/backend/optimizer/util/ordering.c +++ /dev/null @@ -1,169 +0,0 @@ -/*------------------------------------------------------------------------- - * - * ordering.c - * Routines to manipulate and compare merge and path orderings - * - * Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/ordering.c,v 1.17 1999/07/15 22:39:31 momjian Exp $ - * - *------------------------------------------------------------------------- - */ -#include <sys/types.h> - -#include "postgres.h" - -#include "optimizer/ordering.h" - -static bool sortops_order_match(Oid *ordering1, Oid *ordering2, - int *better_sort); - -/* - * equal_path_ordering - * Returns t iff two path orderings are equal. - * - */ -bool -pathorder_match(PathOrder *path_ordering1, - PathOrder *path_ordering2, - int *better_sort) -{ - - *better_sort = 0; - - if (path_ordering1 == path_ordering2) - return true; - - if (!path_ordering2) - { - *better_sort = 1; - return true; - } - - if (!path_ordering1) - { - *better_sort = 2; - return true; - } - - if (path_ordering1->ordtype == MERGE_ORDER && - path_ordering2->ordtype == MERGE_ORDER) - return equal(path_ordering1->ord.merge, path_ordering2->ord.merge); - else if (path_ordering1->ordtype == SORTOP_ORDER && - path_ordering2->ordtype == SORTOP_ORDER) - { - return sortops_order_match(path_ordering1->ord.sortop, - path_ordering2->ord.sortop, - better_sort); - } - else if (path_ordering1->ordtype == MERGE_ORDER && - path_ordering2->ordtype == SORTOP_ORDER) - { - if (!path_ordering2->ord.sortop) - { - *better_sort = 1; - return true; - } - return path_ordering1->ord.merge->left_operator == path_ordering2->ord.sortop[0]; - } - else - { - if (!path_ordering1->ord.sortop) - { - *better_sort = 2; - return true; - } - return path_ordering1->ord.sortop[0] == path_ordering2->ord.merge->left_operator; - } -} - -/* - * equal_path_merge_ordering - * Returns t iff a path ordering is usable for ordering a merge join. - * - * XXX Presently, this means that the first sortop of the path matches - * either of the merge sortops. Is there a "right" and "wrong" - * sortop to match? - * - */ -bool -equal_path_merge_ordering(Oid *path_ordering, - MergeOrder *merge_ordering) -{ - if (path_ordering == NULL || merge_ordering == NULL) - return false; - - if (path_ordering[0] == merge_ordering->left_operator || - path_ordering[0] == merge_ordering->right_operator) - return true; - else - return false; -} - -/* - * equal_merge_ordering - * Returns t iff two merge orderings are equal. - * - */ -bool -equal_merge_ordering(MergeOrder *merge_ordering1, - MergeOrder *merge_ordering2) -{ - return equal(merge_ordering1, merge_ordering2); -} - - -/* - * sortops - * - */ - -/* - * equal_sort_ops_order - - * Returns true iff the sort operators are in the same order. - */ -static bool -sortops_order_match(Oid *ordering1, Oid *ordering2, int *better_sort) -{ - int i = 0; - - *better_sort = 0; - - if (ordering1 == ordering2) - return true; - - if (!ordering2) - { - *better_sort = 1; - return true; - } - - if (!ordering1) - { - *better_sort = 2; - return true; - } - - while (ordering1[i] != 0 && ordering2[i] != 0) - { - if (ordering1[i] != ordering2[i]) - break; - i++; - } - - if (ordering1[i] != 0 && ordering2[i] == 0) - { - *better_sort = 1; - return true; - } - - if (ordering1[i] == 0 && ordering2[i] != 0) - { - *better_sort = 2; - return true; - } - - return ordering1[i] == 0 && ordering2[i] == 0; -} diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index f1e0f5e3ae3..f3b99f88929 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.53 1999/08/06 04:00:17 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.54 1999/08/16 02:17:58 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -18,16 +18,12 @@ #include "optimizer/cost.h" -#include "optimizer/keys.h" -#include "optimizer/ordering.h" #include "optimizer/pathnode.h" #include "optimizer/paths.h" #include "optimizer/plancat.h" #include "optimizer/restrictinfo.h" #include "parser/parsetree.h" -static Path *better_path(Path *new_path, List *unique_paths, bool *is_new); - /***************************************************************************** * MISC. PATH UTILITIES @@ -84,186 +80,104 @@ set_cheapest(RelOptInfo *parent_rel, List *pathlist) /* * add_pathlist - * For each path in the list 'new_paths', add to the list 'unique_paths' - * only those paths that are unique (i.e., unique ordering and ordering - * keys). Should a conflict arise, the more expensive path is thrown out, - * thereby pruning the plan space. But we don't prune if xfunc - * told us not to. + * Construct an output path list by adding to old_paths each path in + * new_paths that is worth considering --- that is, it has either a + * better sort order (better pathkeys) or cheaper cost than any of the + * existing old paths. * - * 'parent_rel' is the relation entry to which these paths correspond. + * Unless parent_rel->pruneable is false, we also remove from the output + * pathlist any old paths that are dominated by added path(s) --- that is, + * some new path is both cheaper and at least as well ordered. * - * Returns the list of unique pathnodes. + * Note: the list old_paths is destructively modified, and in fact is + * turned into the output list. * + * 'parent_rel' is the relation entry to which these paths correspond. + * 'old_paths' is the list of previously accepted paths for parent_rel. + * 'new_paths' is a list of potential new paths. + * + * Returns the updated list of interesting pathnodes. */ List * -add_pathlist(RelOptInfo *parent_rel, List *unique_paths, List *new_paths) +add_pathlist(RelOptInfo *parent_rel, List *old_paths, List *new_paths) { List *p1; foreach(p1, new_paths) { Path *new_path = (Path *) lfirst(p1); - Path *old_path; - bool is_new; - - /* Is this new path already in unique_paths? */ - if (member(new_path, unique_paths)) - continue; - - /* Find best matching path */ - old_path = better_path(new_path, unique_paths, &is_new); - - if (is_new) - { - /* This is a brand new path. */ - new_path->parent = parent_rel; - unique_paths = lcons(new_path, unique_paths); - } - else if (old_path == NULL) - { - ; /* do nothing if path is not cheaper */ - } - else if (old_path != NULL) - { /* (IsA(old_path,Path)) { */ - new_path->parent = parent_rel; - if (!parent_rel->pruneable) - unique_paths = lcons(new_path, unique_paths); - else - unique_paths = lcons(new_path, - LispRemove(old_path, unique_paths)); - } - } - return unique_paths; -} + bool accept_new = true; /* unless we find a superior old path */ + List *p2_prev = NIL; + List *p2; -/* - * better_path - * Determines whether 'new_path' has the same ordering and keys as some - * path in the list 'unique_paths'. If there is a redundant path, - * eliminate the more expensive path. - * - * Returns: - * The old path - if 'new_path' matches some path in 'unique_paths' and is - * cheaper - * nil - if 'new_path' matches but isn't cheaper - * t - if there is no path in the list with the same ordering and keys - * - */ -static Path * -better_path(Path *new_path, List *unique_paths, bool *is_new) -{ - Path *path = (Path *) NULL; - List *temp = NIL; - int better_key; - int better_sort; - -#ifdef OPTDUP_DEBUG - printf("better_path entry\n"); - printf("new\n"); - pprint(new_path); - printf("unique_paths\n"); - pprint(unique_paths); -#endif - - foreach(temp, unique_paths) - { - path = (Path *) lfirst(temp); - -#ifdef OPTDUP_DEBUG - if (!pathkeys_match(new_path->pathkeys, path->pathkeys, &better_key) || - better_key != 0) - { - printf("betterkey = %d\n", better_key); - printf("newpath\n"); - pprint(new_path->pathkeys); - printf("oldpath\n"); - pprint(path->pathkeys); - if (path->pathkeys && new_path->pathkeys && - length(lfirst(path->pathkeys)) >= 2 /* && - * length(lfirst(path->pa - * thkeys)) < - * length(lfirst(new_path - ->pathkeys)) */ ) - sleep(0); /* set breakpoint here */ - } - if (!pathorder_match(new_path->pathorder, path->pathorder, - &better_sort) || - better_sort != 0) + /* + * Loop to check proposed new path against old paths. Note it is + * possible for more than one old path to be tossed out because + * new_path dominates it. + */ + foreach(p2, old_paths) { - printf("neword\n"); - pprint(new_path->pathorder); - printf("oldord\n"); - pprint(path->pathorder); - } -#endif + Path *old_path = (Path *) lfirst(p2); + bool remove_old = false; /* unless new proves superior */ - if (pathkeys_match(new_path->pathkeys, path->pathkeys, - &better_key) && - pathorder_match(new_path->pathorder, path->pathorder, - &better_sort)) - { + switch (compare_pathkeys(new_path->pathkeys, old_path->pathkeys)) + { + case PATHKEYS_EQUAL: + if (new_path->path_cost < old_path->path_cost) + remove_old = true; /* new dominates old */ + else + accept_new = false; /* old equals or dominates new */ + break; + case PATHKEYS_BETTER1: + if (new_path->path_cost <= old_path->path_cost) + remove_old = true; /* new dominates old */ + break; + case PATHKEYS_BETTER2: + if (new_path->path_cost >= old_path->path_cost) + accept_new = false; /* old dominates new */ + break; + case PATHKEYS_DIFFERENT: + /* keep both paths, since they have different ordering */ + break; + } /* - * Replace pathkeys that match exactly, {{1,2}}, {{1,2}} - * Replace pathkeys {{1,2}} with {{1,2,3}}} if the latter is - * not more expensive and replace unordered path with ordered - * path if it is not more expensive. Favor sorted keys over - * unsorted keys in the same way. + * Remove current element from old_list if dominated by new, + * unless xfunc told us not to remove any paths. */ - /* same keys, and new is cheaper, use it */ - if ((better_key == 0 && better_sort == 0 && - new_path->path_cost < path->path_cost) || - - /* new is better, and cheaper, use it */ - (((better_key == 1 && better_sort != 2) || - (better_key != 2 && better_sort == 1)) && - new_path->path_cost <= path->path_cost)) + if (remove_old && parent_rel->pruneable) { -#ifdef OPTDUP_DEBUG - printf("replace with new %p old %p better key %d better sort %d\n", &new_path, &path, better_key, better_sort); - printf("new\n"); - pprint(new_path); - printf("old\n"); - pprint(path); -#endif - *is_new = false; - return path; + if (p2_prev) + lnext(p2_prev) = lnext(p2); + else + old_paths = lnext(p2); } + else + p2_prev = p2; - /* same keys, new is more expensive, stop */ - if ((better_key == 0 && better_sort == 0 && - new_path->path_cost >= path->path_cost) || + /* + * If we found an old path that dominates new_path, we can quit + * scanning old_paths; we will not add new_path, and we assume + * new_path cannot dominate any other elements of old_paths. + */ + if (! accept_new) + break; + } - /* old is better, and less expensive, stop */ - (((better_key == 2 && better_sort != 1) || - (better_key != 1 && better_sort == 2)) && - new_path->path_cost >= path->path_cost)) - { -#ifdef OPTDUP_DEBUG - printf("skip new %p old %p better key %d better sort %d\n", &new_path, &path, better_key, better_sort); - printf("new\n"); - pprint(new_path); - printf("old\n"); - pprint(path); -#endif - *is_new = false; - return NULL; - } + if (accept_new) + { + /* Accept the path. Note that it will now be eligible to be + * compared against the additional elements of new_paths... + */ + new_path->parent = parent_rel; /* not redundant, see prune.c */ + old_paths = lcons(new_path, old_paths); } } -#ifdef OPTDUP_DEBUG - printf("add new %p old %p better key %d better sort %d\n", &new_path, &path, better_key, better_sort); - printf("new\n"); - pprint(new_path); -#endif - - *is_new = true; - return NULL; + return old_paths; } - /***************************************************************************** * PATH NODE CREATION ROUTINES *****************************************************************************/ @@ -277,19 +191,15 @@ better_path(Path *new_path, List *unique_paths, bool *is_new) Path * create_seqscan_path(RelOptInfo *rel) { - int relid = 0; - Path *pathnode = makeNode(Path); + int relid = 0; pathnode->pathtype = T_SeqScan; pathnode->parent = rel; pathnode->path_cost = 0.0; - pathnode->pathorder = makeNode(PathOrder); - pathnode->pathorder->ordtype = SORTOP_ORDER; - pathnode->pathorder->ord.sortop = NULL; - pathnode->pathkeys = NIL; + pathnode->pathkeys = NIL; /* seqscan has unordered result */ - if (rel->relids != NULL) + if (rel->relids != NIL) /* can this happen? */ relid = lfirsti(rel->relids); pathnode->path_cost = cost_seqscan(relid, @@ -319,12 +229,10 @@ create_index_path(Query *root, pathnode->path.pathtype = T_IndexScan; pathnode->path.parent = rel; - pathnode->path.pathorder = makeNode(PathOrder); - pathnode->path.pathorder->ordtype = SORTOP_ORDER; - pathnode->path.pathorder->ord.sortop = index->ordering; - pathnode->path.pathkeys = NIL; + pathnode->path.pathkeys = build_index_pathkeys(root, rel, index); - /* Note that we are making a pathnode for a single-scan indexscan; + /* + * Note that we are making a pathnode for a single-scan indexscan; * therefore, both indexid and indexqual should be single-element * lists. We initialize indexqual to contain one empty sublist, * representing a single index traversal with no index restriction @@ -334,29 +242,7 @@ create_index_path(Query *root, Assert(length(index->relids) == 1); pathnode->indexid = index->relids; pathnode->indexqual = lcons(NIL, NIL); - - pathnode->indexkeys = index->indexkeys; - - /* - * The index must have an ordering for the path to have (ordering) - * keys, and vice versa. - */ - if (pathnode->path.pathorder->ord.sortop) - { - pathnode->path.pathkeys = collect_index_pathkeys(index->indexkeys, - rel->targetlist); - - /* - * Check that the keys haven't 'disappeared', since they may no - * longer be in the target list (i.e., index keys that are not - * relevant to the scan are not applied to the scan path node, so - * if no index keys were found, we can't order the path). - */ - if (pathnode->path.pathkeys == NULL) - pathnode->path.pathorder->ord.sortop = NULL; - } - else - pathnode->path.pathkeys = NULL; + pathnode->joinrelids = NIL; /* no join clauses here */ if (restriction_clauses == NIL) { @@ -377,7 +263,7 @@ create_index_path(Query *root, { /* * Compute scan cost for the case when 'index' is used with - * restriction clause(s). + * restriction clause(s). Also, place indexqual in path node. */ List *indexquals; float npages; @@ -439,9 +325,9 @@ create_index_path(Query *root, * * 'joinrel' is the join relation. * 'outer_rel' is the outer join relation - * 'outer_path' is the outer join path. - * 'inner_path' is the inner join path. - * 'pathkeys' are the keys of the path + * 'outer_path' is the outer path + * 'inner_path' is the inner path + * 'pathkeys' are the path keys of the new join path * * Returns the resulting path node. * @@ -461,23 +347,6 @@ create_nestloop_path(RelOptInfo *joinrel, pathnode->innerjoinpath = inner_path; pathnode->pathinfo = joinrel->restrictinfo; pathnode->path.pathkeys = pathkeys; - pathnode->path.joinid = NIL; - pathnode->path.outerjoincost = (Cost) 0.0; - pathnode->path.pathorder = makeNode(PathOrder); - - if (pathkeys) - { - pathnode->path.pathorder->ordtype = outer_path->pathorder->ordtype; - if (outer_path->pathorder->ordtype == SORTOP_ORDER) - pathnode->path.pathorder->ord.sortop = outer_path->pathorder->ord.sortop; - else - pathnode->path.pathorder->ord.merge = outer_path->pathorder->ord.merge; - } - else - { - pathnode->path.pathorder->ordtype = SORTOP_ORDER; - pathnode->path.pathorder->ord.sortop = NULL; - } pathnode->path.path_cost = cost_nestloop(outer_path->path_cost, inner_path->path_cost, @@ -502,8 +371,7 @@ create_nestloop_path(RelOptInfo *joinrel, * '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 new keys of the join relation - * 'order' is the sort order required for the merge + * 'pathkeys' are the path keys of the new join path * 'mergeclauses' are the applicable join/restriction clauses * 'outersortkeys' are the sort varkeys for the outer relation * 'innersortkeys' are the sort varkeys for the inner relation @@ -518,22 +386,29 @@ create_mergejoin_path(RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, - MergeOrder *order, List *mergeclauses, List *outersortkeys, List *innersortkeys) { MergePath *pathnode = makeNode(MergePath); + /* + * If the given paths are already well enough ordered, we can skip + * doing an explicit sort. + */ + if (outersortkeys && + pathkeys_contained_in(outersortkeys, outer_path->pathkeys)) + outersortkeys = NIL; + if (innersortkeys && + pathkeys_contained_in(innersortkeys, inner_path->pathkeys)) + innersortkeys = NIL; + pathnode->jpath.path.pathtype = T_MergeJoin; 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->jpath.path.pathorder = makeNode(PathOrder); - pathnode->jpath.path.pathorder->ordtype = MERGE_ORDER; - pathnode->jpath.path.pathorder->ord.merge = order; pathnode->path_mergeclauses = mergeclauses; pathnode->outersortkeys = outersortkeys; pathnode->innersortkeys = innersortkeys; @@ -560,15 +435,11 @@ create_mergejoin_path(RelOptInfo *joinrel, * '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 - * 'pathkeys' are the path keys of the new join path - * 'operator' is the hashjoin operator * 'hashclauses' is a list of the hash join clause (always a 1-element list) - * 'outerkeys' are the sort varkeys for the outer relation - * 'innerkeys' are the sort varkeys for the inner relation * 'innerdisbursion' is an estimate of the disbursion of the inner hash key * */ -HashPath * +HashPath * create_hashjoin_path(RelOptInfo *joinrel, int outersize, int innersize, @@ -576,11 +447,7 @@ create_hashjoin_path(RelOptInfo *joinrel, int innerwidth, Path *outer_path, Path *inner_path, - List *pathkeys, - Oid operator, List *hashclauses, - List *outerkeys, - List *innerkeys, Cost innerdisbursion) { HashPath *pathnode = makeNode(HashPath); @@ -590,16 +457,9 @@ create_hashjoin_path(RelOptInfo *joinrel, pathnode->jpath.outerjoinpath = outer_path; pathnode->jpath.innerjoinpath = inner_path; pathnode->jpath.pathinfo = joinrel->restrictinfo; - pathnode->jpath.path.pathkeys = pathkeys; - pathnode->jpath.path.pathorder = makeNode(PathOrder); - pathnode->jpath.path.pathorder->ordtype = SORTOP_ORDER; - pathnode->jpath.path.pathorder->ord.sortop = NULL; - pathnode->jpath.path.outerjoincost = (Cost) 0.0; - pathnode->jpath.path.joinid = (Relids) NULL; - /* pathnode->hashjoinoperator = operator; */ + /* A hashjoin never has pathkeys, since its ordering is unpredictable */ + pathnode->jpath.path.pathkeys = NIL; pathnode->path_hashclauses = hashclauses; - pathnode->outerhashkeys = outerkeys; - pathnode->innerhashkeys = innerkeys; pathnode->jpath.path.path_cost = cost_hashjoin(outer_path->path_cost, inner_path->path_cost, outersize, innersize, diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index 2a1b4cc73bd..885d0f0715c 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.18 1999/07/16 03:13:05 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.19 1999/08/16 02:17:58 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -29,10 +29,9 @@ RelOptInfo * get_base_rel(Query *root, int relid) { - Relids relids; + Relids relids = lconsi(relid, NIL); RelOptInfo *rel; - relids = lconsi(relid, NIL); rel = rel_member(relids, root->base_rel_list); if (rel == NULL) { @@ -41,28 +40,26 @@ get_base_rel(Query *root, int relid) rel->indexed = false; rel->pages = 0; rel->tuples = 0; + rel->size = 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->restrictinfo = NIL; rel->joininfo = NIL; rel->innerjoin = NIL; root->base_rel_list = lcons(rel, root->base_rel_list); - /* - * ??? the old lispy C code (get_rel) do a listp(relid) here but - * that can never happen since we already established relid is not - * a list. -ay 10/94 - */ if (relid < 0) { - /* * If the relation is a materialized relation, assume * constants for sizes. @@ -72,18 +69,12 @@ get_base_rel(Query *root, int relid) } else { - bool hasindex; - int pages, - tuples; - /* - * Otherwise, retrieve relation characteristics from the + * Otherwise, retrieve relation statistics from the * system catalogs. */ - relation_info(root, relid, &hasindex, &pages, &tuples); - rel->indexed = hasindex; - rel->pages = pages; - rel->tuples = tuples; + relation_info(root, relid, + &rel->indexed, &rel->pages, &rel->tuples); } } return rel; @@ -111,16 +102,16 @@ get_join_rel(Query *root, Relids relid) RelOptInfo * rel_member(Relids relids, List *rels) { - List *temp = NIL; - List *temprelid = NIL; - if (relids != NIL && rels != NIL) { + List *temp; + foreach(temp, rels) { - temprelid = ((RelOptInfo *) lfirst(temp))->relids; - if (same(temprelid, relids)) - return (RelOptInfo *) (lfirst(temp)); + RelOptInfo *rel = (RelOptInfo *) lfirst(temp); + + if (same(rel->relids, relids)) + return rel; } } return NULL; diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index 322987c447c..37f47c53062 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.50 1999/07/15 15:21:17 momjian Exp $ + * $Id: nodes.h,v 1.51 1999/08/16 02:17:39 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -64,27 +64,21 @@ typedef enum NodeTag T_Func, T_Array, T_ArrayRef, + T_Iter, /*--------------------- - * TAGS FOR INNER PLAN NODES (relation.h) + * TAGS FOR PLANNER NODES (relation.h) *--------------------- */ T_RelOptInfo = 200, - T_PathOrder, T_Path, T_IndexPath, T_NestPath, T_MergePath, T_HashPath, - T_OrderKey, - T_JoinKey, - T_MergeOrder, + T_PathKeyItem, T_RestrictInfo, - T_JoinMethod, - T_HashInfo, - T_MergeInfo, T_JoinInfo, - T_Iter, T_Stream, /*--------------------- @@ -229,28 +223,27 @@ typedef struct Node NodeTag type; } Node; -#define nodeTag(_node_) ((Node*)_node_)->type +#define nodeTag(nodeptr) (((Node*)(nodeptr))->type) -#define makeNode(_node_) (_node_*)newNode(sizeof(_node_),T_##_node_) -#define NodeSetTag(n, t) ((Node *)n)->type = t +#define makeNode(_type_) ((_type_ *) newNode(sizeof(_type_),T_##_type_)) +#define NodeSetTag(nodeptr,t) (((Node*)(nodeptr))->type = (t)) -#define IsA(_node_,_tag_) (nodeTag(_node_) == T_##_tag_) +#define IsA(nodeptr,_type_) (nodeTag(nodeptr) == T_##_type_) /* ---------------------------------------------------------------- - * IsA functions (no inheritence any more) + * IsA functions (no inheritance any more) * ---------------------------------------------------------------- */ #define IsA_JoinPath(jp) \ - (nodeTag(jp)==T_NestPath || nodeTag(jp)==T_MergePath || \ - nodeTag(jp)==T_HashPath) + (IsA(jp, NestPath) || IsA(jp, MergePath) || IsA(jp, HashPath)) -#define IsA_Join(j) \ - (nodeTag(j)==T_Join || nodeTag(j)==T_NestLoop || \ - nodeTag(j)==T_MergeJoin || nodeTag(j)==T_HashJoin) +#define IsA_Join(jp) \ + (IsA(jp, Join) || IsA(jp, NestLoop) || \ + IsA(jp, MergeJoin) || IsA(jp, HashJoin)) #define IsA_Noname(t) \ - (nodeTag(t)==T_Noname || nodeTag(t)==T_Material || nodeTag(t)==T_Sort || \ - nodeTag(t)==T_Unique) + (IsA(t, Noname) || IsA(t, Material) || IsA(t, Sort) || \ + IsA(t, Unique)) /* ---------------------------------------------------------------- * extern declarations follow @@ -262,6 +255,9 @@ typedef struct Node */ extern Node *newNode(Size size, NodeTag tag); +/* + * nodes/{outfuncs.c,print.c} + */ extern char *nodeToString(void *obj); /* diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h index 3e20012b087..f3a7432adca 100644 --- a/src/include/nodes/pg_list.h +++ b/src/include/nodes/pg_list.h @@ -6,7 +6,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: pg_list.h,v 1.12 1999/07/15 23:03:55 momjian Exp $ + * $Id: pg_list.h,v 1.13 1999/08/16 02:17:39 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -35,9 +35,9 @@ typedef struct Value } val; } Value; -#define intVal(v) (((Value *)v)->val.ival) -#define floatVal(v) (((Value *)v)->val.dval) -#define strVal(v) (((Value *)v)->val.str) +#define intVal(v) (((Value *)(v))->val.ival) +#define floatVal(v) (((Value *)(v))->val.dval) +#define strVal(v) (((Value *)(v))->val.str) /*---------------------- @@ -66,7 +66,7 @@ typedef struct List /* pointer version of the list (where it makes a difference) */ #define lfirst(l) ((l)->elem.ptr_value) #define lnext(l) ((l)->next) -#define lsecond(l) (lfirst(lnext(l))) +#define lsecond(l) lfirst(lnext(l)) #define lfirsti(l) ((l)->elem.int_value) @@ -75,7 +75,7 @@ typedef struct List * a convenience macro which loops through the list */ #define foreach(_elt_,_list_) \ - for(_elt_=_list_; _elt_!=NIL;_elt_=lnext(_elt_)) + for(_elt_=(_list_); _elt_!=NIL; _elt_=lnext(_elt_)) /* @@ -84,34 +84,34 @@ typedef struct List extern int length(List *list); extern List *nconc(List *list1, List *list2); extern List *lcons(void *datum, List *list); -extern bool member(void *foo, List *bar); +extern List *lconsi(int datum, List *list); +extern bool member(void *datum, List *list); +extern bool intMember(int datum, List *list); extern Value *makeInteger(long i); extern Value *makeFloat(double d); extern Value *makeString(char *str); extern List *makeList(void *elem,...); -extern List *lappend(List *list, void *obj); +extern List *lappend(List *list, void *datum); +extern List *lappendi(List *list, int datum); extern List *lremove(void *elem, List *list); -extern void freeList(List *list); extern List *LispRemove(void *elem, List *list); +extern List *ltruncate(int n, List *list); extern void *nth(int n, List *l); +extern int nthi(int n, List *l); extern void set_nth(List *l, int n, void *elem); -List *lconsi(int datum, List *list); -List *lappendi(List *list, int datum); -extern bool intMember(int, List *); +extern List *set_difference(List *list1, List *list2); +extern List *set_differencei(List *list1, List *list2); +extern List *LispUnion(List *list1, List *list2); +extern List *LispUnioni(List *list1, List *list2); +extern bool same(List *list1, List *list2); -extern int nthi(int n, List *l); - -extern List *set_difference(List *, List *); -extern List *set_differencei(List *, List *); -extern List *LispUnion(List *foo, List *bar); -extern List *LispUnioni(List *foo, List *bar); -extern bool same(List *foo, List *bar); +extern void freeList(List *list); /* should be in nodes.h but needs List */ /* in copyfuncs.c */ -extern List *listCopy(List *); +extern List *listCopy(List *list); #endif /* PG_LIST_H */ diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h index a4128a8d38a..2c4d0ffaa72 100644 --- a/src/include/nodes/primnodes.h +++ b/src/include/nodes/primnodes.h @@ -6,7 +6,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: primnodes.h,v 1.32 1999/07/18 03:45:01 tgl Exp $ + * $Id: primnodes.h,v 1.33 1999/08/16 02:17:39 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -256,6 +256,20 @@ typedef struct Func } Func; /* ---------------- + * Iter + * can anyone explain what this is for? Seems to have something to do + * with evaluation of functions that return sets... + * ---------------- + */ +typedef struct Iter +{ + NodeTag type; + Node *iterexpr; + Oid itertype; /* type of the iter expr (use for type + * checking) */ +} Iter; + +/* ---------------- * Aggref * aggname - name of the aggregate * basetype - base type Oid of the aggregate diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h index 4db2e9cea44..91fa85dd25e 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.37 1999/07/27 03:51:09 tgl Exp $ + * $Id: relation.h,v 1.38 1999/08/16 02:17:40 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -18,65 +18,75 @@ /* * Relids * List of relation identifiers (indexes into the rangetable). + * + * Note: these are lists of integers, not Nodes. */ typedef List *Relids; /* * RelOptInfo - * Per-base-relation information + * Per-relation information for planning/optimization * * Parts of this data structure are specific to various scan and join * mechanisms. It didn't seem worth creating new node types for them. * - * relids - List of relation indentifiers + * 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 - number of tuples in the relation after restrictions clauses - * have been applied - * width - number of bytes per tuple in the relation after the + * size - estimated number of tuples in the relation after restriction + * clauses have been applied + * width - avg. number of bytes per tuple in the relation after the * appropriate projections have been done * targetlist - List of TargetList nodes - * pathlist - List of Path nodes, one for each possible method of - * generating the relation - * cheapestpath - least expensive Path (regardless of final order) - * pruneable - flag to let the planner know whether it can prune the plan - * space of this RelOptInfo or not. + * pathlist - List of Path nodes, one for each potentially useful + * method of generating the relation + * cheapestpath - least expensive Path (regardless of ordering) + * 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 - * three fields: + * 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. + * + * 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. + * * * The presence of the remaining fields depends on the restrictions - * and joins which the relation participates in: + * and joins that the relation participates in: * * restrictinfo - List of RestrictInfo nodes, containing info about each * qualification clause in which this relation participates * joininfo - List of JoinInfo nodes, containing info about each join * clause in which this relation participates * innerjoin - List of Path nodes that represent indices that may be used - * as inner paths of nestloop joins - * - * NB. the last element of the arrays classlist, indexkeys and ordering - * is always 0. 2/95 - ay + * as inner paths of nestloop joins. This field is non-null + * only for base rels, since join rels have no indices. */ typedef struct RelOptInfo { NodeTag type; - /* all relations: */ - Relids relids; /* integer list of base relids involved */ + /* all relations included in this RelOptInfo */ + Relids relids; /* integer list of base relids */ /* catalog statistics information */ bool indexed; int pages; int tuples; + + /* estimates generated by planner. XXX int is probably too small... */ int size; int width; @@ -89,65 +99,66 @@ typedef struct RelOptInfo /* 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; - List *indpred; + Oid indproc; /* if a functional index */ + List *indpred; /* if a partial index */ /* used by various scans and joins: */ - Oid *ordering; /* OID of operators in sort order */ List *restrictinfo; /* RestrictInfo structures */ List *joininfo; /* JoinInfo structures */ - List *innerjoin; + List *innerjoin; /* potential indexscans for nestloop joins */ + /* innerjoin indexscans are not in the main pathlist because they are + * not usable except in specific join contexts; we have to test before + * seeing whether they can be used. + */ } RelOptInfo; -extern Var *get_expr(TargetEntry *foo); -extern Var *get_groupclause_expr(GroupClause *groupClause, List *targetList); +/* + * PathKeys + * + * The sort ordering of a path is represented by a list of sublists of + * PathKeyItem nodes. An empty list implies no known ordering. Otherwise + * the first sublist represents the primary sort key, the second the + * first secondary sort key, etc. Each sublist contains one or more + * PathKeyItem nodes, each of which can be taken as the attribute that + * appears at that sort position. (See the top of optimizer/path/pathkeys.c + * for more information.) + */ -typedef struct MergeOrder +typedef struct PathKeyItem { NodeTag type; - Oid join_operator; - Oid left_operator; - Oid right_operator; - Oid left_type; - Oid right_type; -} MergeOrder; - -typedef enum OrderType -{ - MERGE_ORDER, SORTOP_ORDER -} OrderType; -typedef struct PathOrder -{ - NodeTag type; + Node *key; /* the item that is ordered */ + Oid sortop; /* the ordering operator ('<' op) */ + /* + * key typically points to a Var node, ie a relation attribute, + * but it can also point to a Func clause representing the value + * indexed by a functional index. Someday we might allow arbitrary + * expressions as path keys, so don't assume more than you must. + */ +} PathKeyItem; - OrderType ordtype; - union - { - Oid *sortop; - MergeOrder *merge; - } ord; -} PathOrder; +/* + * Type "Path" is used as-is for sequential-scan paths. For other + * path types it is the first component of a larger struct. + */ typedef struct Path { NodeTag type; - RelOptInfo *parent; - Cost path_cost; + RelOptInfo *parent; /* the relation this path can build */ - NodeTag pathtype; + Cost path_cost; /* estimated execution cost of path */ - PathOrder *pathorder; + NodeTag pathtype; /* tag identifying scan/join method */ + /* XXX why is pathtype separate from the NodeTag? */ - List *pathkeys; /* This is a List of List of Var nodes. - * See the top of - * optimizer/path/pathkeys.c for more - * information. */ - Cost outerjoincost; - Relids joinid; + List *pathkeys; /* sort ordering of path's output */ + /* pathkeys is a List of Lists of PathKeyItem nodes; see above */ } Path; /*---------- @@ -156,129 +167,163 @@ typedef struct Path * different index during each scan. The result is the union (OR) of all the * tuples matched during any scan. (The executor is smart enough not to return * the same tuple more than once, even if it is matched in multiple scans.) + * * 'indexid' is a list of index relation OIDs, one per scan to be performed. * 'indexqual' is a list of index qualifications, also one per scan. * Each entry in 'indexqual' is a sublist of qualification expressions with - * implicit AND semantics across the sublist items. Each one of the sublist - * items must be an operator expression of the form (var op something) or - * (something op var), where the var is a field the associated index keys on - * and the op is a member of the operator class of the index. + * implicit AND semantics across the sublist items. Only expressions that + * are usable as indexquals (as determined by indxpath.c) may appear here. + * * NOTE that the semantics of the top-level list in 'indexqual' is OR * combination, while the sublists are implicitly AND combinations! *---------- */ + typedef struct IndexPath { Path path; List *indexid; List *indexqual; - int *indexkeys; /* to transform heap attnos into index - * ones */ + /* + * joinrelids is only used in IndexPaths that are constructed for use + * as the inner path of a nestloop join. These paths have indexquals + * that refer to values of other rels, so those other rels must be + * included in the outer joinrel in order to make a usable join. + */ + Relids joinrelids; /* other rels mentioned in indexqual */ } IndexPath; -typedef struct NestPath +/* + * All join-type paths share these fields. + */ + +typedef struct JoinPath { Path path; - List *pathinfo; - Path *outerjoinpath; - Path *innerjoinpath; -} NestPath; -typedef NestPath JoinPath; + 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; + +/* + * A nested-loop path needs no special fields. + */ + +typedef JoinPath NestPath; + +/* + * A mergejoin path has these fields. + * + * Note that the mergeclauses are a subset of the parent relation's + * restriction-clause list. Any join clauses that are not mergejoinable + * appear only in the parent's restrict list, and must be checked by a + * qpqual at execution time. + */ typedef struct MergePath { JoinPath jpath; - List *path_mergeclauses; + List *path_mergeclauses; /* join clauses used for merge */ + /* + * outersortkeys (resp. innersortkeys) is NIL if the outer path + * (resp. inner path) is already ordered appropriately for the + * mergejoin. If it is not NIL then it is a PathKeys list describing + * the ordering that must be created by an explicit sort step. + */ List *outersortkeys; List *innersortkeys; } MergePath; -typedef struct HashPath -{ - JoinPath jpath; - List *path_hashclauses; - List *outerhashkeys; - List *innerhashkeys; -} HashPath; - /* - * Keys + * A hashjoin path has these fields. + * + * The remarks above for mergeclauses apply for hashclauses as well. + * However, hashjoin does not care what order its inputs appear in, + * so we have no need for sortkeys. */ -typedef struct OrderKey -{ - NodeTag type; - int attribute_number; - Index array_index; -} OrderKey; - -typedef struct JoinKey +typedef struct HashPath { - NodeTag type; - Var *outer; - Var *inner; -} JoinKey; + JoinPath jpath; + List *path_hashclauses; /* join clauses used for hashing */ +} HashPath; /* * Restriction clause info. + * * We create one of these for each AND sub-clause of a restriction condition * (WHERE clause). Since the restriction clauses are logically ANDed, we * can use any one of them or any subset of them to filter out tuples, * without having to evaluate the rest. The RestrictInfo node itself stores * data used by the optimizer while choosing the best query plan. + * + * A restriction clause will appear in the restrictinfo list of a RelOptInfo + * that describes exactly the set of base relations referenced by the + * restriction clause. It is not possible to apply the clause at any lower + * nesting level, and there is little point in delaying its evaluation to + * higher nesting levels. (The "predicate migration" code was once intended + * to push restriction clauses up and down the plan tree, but it's dead code + * and is unlikely to be resurrected in the foreseeable future.) + * + * If a restriction clause references more than one base rel, it will also + * appear in the JoinInfo list of every RelOptInfo that describes a strict + * subset of the base rels mentioned in the clause. The JoinInfo lists are + * used to drive join tree building by selecting plausible join candidates. + * + * In general, the referenced clause might be arbitrarily complex. The + * kinds of clauses we can handle as indexscan quals, mergejoin clauses, + * or hashjoin clauses are fairly limited --- the code for each kind of + * path is responsible for identifying the restrict clauses it can use + * and ignoring the rest. Clauses not implemented by an indexscan, + * mergejoin, or hashjoin will be placed in the qpqual field of the + * final Plan node, where they will be enforced by general-purpose + * qual-expression-evaluation code. (But we are still entitled to count + * their selectivity when estimating the result tuple count, if we + * can guess what it is...) */ typedef struct RestrictInfo { NodeTag type; - Expr *clause; /* the represented subclause of WHERE cond */ - Cost selectivity; /* estimated selectivity */ - List *indexids; /* subclause index IDs if clause is an OR */ - /* mergejoin only */ - MergeOrder *mergejoinorder; + Expr *clause; /* the represented clause of WHERE cond */ + Cost selectivity; /* estimated selectivity */ - /* hashjoin only */ - Oid hashjoinoperator; -} RestrictInfo; + /* only used if clause is an OR clause: */ + List *subclauseindices; /* lists of indexes matching subclauses */ -typedef struct JoinMethod -{ - NodeTag type; - List *jmkeys; - List *clauses; -} JoinMethod; + /* valid if clause is mergejoinable, else InvalidOid: */ + Oid mergejoinoperator; /* copy of clause operator */ + Oid left_sortop; /* leftside sortop needed for mergejoin */ + Oid right_sortop; /* rightside sortop needed for mergejoin */ -typedef struct HashInfo -{ - JoinMethod jmethod; - Oid hashop; -} HashInfo; + /* valid if clause is hashjoinable, else InvalidOid: */ + Oid hashjoinoperator; /* copy of clause operator */ +} RestrictInfo; -typedef struct MergeInfo -{ - JoinMethod jmethod; - MergeOrder *m_ordering; -} MergeInfo; +/* + * Join clause info. + * + * We make a list of these for each RelOptInfo, containing info about + * all the join clauses this RelOptInfo participates in. (For this + * purpose, a "join clause" is a WHERE clause that mentions both vars + * belonging to this relation and vars belonging to relations not yet + * joined to it.) We group these clauses according to the set of + * other base relations (unjoined relations) mentioned in them. + * There is one JoinInfo for each distinct set of unjoined_relids, + * and its jinfo_restrictinfo lists the clause(s) that use that set + * of other relations. + */ typedef struct JoinInfo { NodeTag type; - Relids unjoined_relids; - List *jinfo_restrictinfo; - bool mergejoinable; - bool hashjoinable; + Relids unjoined_relids; /* some rels not yet part of my RelOptInfo */ + List *jinfo_restrictinfo; /* relevant RestrictInfos */ } JoinInfo; -typedef struct Iter -{ - NodeTag type; - Node *iterexpr; - Oid itertype; /* type of the iter expr (use for type - * checking) */ -} Iter; - /* * Stream: * A stream represents a root-to-leaf path in a plan tree (i.e. a tree of @@ -287,6 +332,9 @@ typedef struct Iter * is used to make Path nodes and clauses look similar, so that Predicate * Migration can run. * + * XXX currently, Predicate Migration is dead code, and so is this node type. + * Probably should remove support for it. + * * pathptr -- pointer to the current path node * cinfo -- if NULL, this stream node referes to the path node. * Otherwise this is a pointer to the current clause. @@ -306,8 +354,8 @@ typedef struct Stream Path *pathptr; RestrictInfo *cinfo; int *clausetype; - struct Stream *upstream; - struct Stream *downstream; + StreamPtr upstream; + StreamPtr downstream; bool groupup; Cost groupcost; Cost groupsel; diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h index 381da4adaeb..ec2dce883fc 100644 --- a/src/include/optimizer/clauses.h +++ b/src/include/optimizer/clauses.h @@ -6,7 +6,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: clauses.h,v 1.27 1999/08/12 04:32:49 tgl Exp $ + * $Id: clauses.h,v 1.28 1999/08/16 02:17:44 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -40,7 +40,6 @@ extern List *make_ands_implicit(Expr *clause); extern List *pull_constant_clauses(List *quals, List **constantQual); extern void clause_get_relids_vars(Node *clause, Relids *relids, List **vars); extern int NumRelids(Node *clause); -extern bool is_joinable(Node *clause); extern List *fix_opids(List *clauses); extern void get_relattval(Node *clause, int targetrelid, int *relid, AttrNumber *attno, diff --git a/src/include/optimizer/joininfo.h b/src/include/optimizer/joininfo.h index ac723261849..4c1aedfba3f 100644 --- a/src/include/optimizer/joininfo.h +++ b/src/include/optimizer/joininfo.h @@ -6,7 +6,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: joininfo.h,v 1.13 1999/07/15 15:21:22 momjian Exp $ + * $Id: joininfo.h,v 1.14 1999/08/16 02:17:44 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -17,6 +17,5 @@ extern JoinInfo *joininfo_member(List *join_relids, List *joininfo_list); extern JoinInfo *find_joininfo_node(RelOptInfo *this_rel, List *join_relids); -extern Var *other_join_clause_var(Var *var, Expr *clause); #endif /* JOININFO_H */ diff --git a/src/include/optimizer/keys.h b/src/include/optimizer/keys.h deleted file mode 100644 index 67910c283fd..00000000000 --- a/src/include/optimizer/keys.h +++ /dev/null @@ -1,23 +0,0 @@ -/*------------------------------------------------------------------------- - * - * keys.h - * prototypes for keys.c. - * - * - * Copyright (c) 1994, Regents of the University of California - * - * $Id: keys.h,v 1.16 1999/07/15 15:21:22 momjian Exp $ - * - *------------------------------------------------------------------------- - */ -#ifndef KEYS_H -#define KEYS_H - -#include "nodes/relation.h" - -extern bool match_indexkey_operand(int indexkey, Var *operand, RelOptInfo *rel); -extern Var *extract_join_key(JoinKey *jk, int outer_or_inner); -extern bool pathkeys_match(List *keys1, List *keys2, int *better_key); -extern List *collect_index_pathkeys(int *index_keys, List *tlist); - -#endif /* KEYS_H */ diff --git a/src/include/optimizer/ordering.h b/src/include/optimizer/ordering.h deleted file mode 100644 index 61dc0a43366..00000000000 --- a/src/include/optimizer/ordering.h +++ /dev/null @@ -1,25 +0,0 @@ -/*------------------------------------------------------------------------- - * - * ordering.h - * prototypes for ordering.c. - * - * - * Copyright (c) 1994, Regents of the University of California - * - * $Id: ordering.h,v 1.15 1999/07/15 23:03:58 momjian Exp $ - * - *------------------------------------------------------------------------- - */ -#ifndef ORDERING_H -#define ORDERING_H - -#include "nodes/relation.h" - -extern bool pathorder_match(PathOrder *path_ordering1, - PathOrder *path_ordering2, int *better_sort); -extern bool equal_path_merge_ordering(Oid *path_ordering, - MergeOrder *merge_ordering); -extern bool equal_merge_ordering(MergeOrder *merge_ordering1, - MergeOrder *merge_ordering2); - -#endif /* ORDERING_H */ diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index aa5be0661e3..65ece63c575 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.20 1999/08/06 04:00:13 tgl Exp $ + * $Id: pathnode.h,v 1.21 1999/08/16 02:17:45 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -20,22 +20,26 @@ */ 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 *unique_paths, - List *new_paths); +extern List *add_pathlist(RelOptInfo *parent_rel, List *old_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); -extern NestPath *create_nestloop_path(RelOptInfo *joinrel, RelOptInfo *outer_rel, - Path *outer_path, Path *inner_path, List *pathkeys); + +extern IndexPath *create_index_path(Query *root, RelOptInfo *rel, + RelOptInfo *index, List *restriction_clauses); + +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, MergeOrder *order, - List *mergeclauses, List *outersortkeys, List *innersortkeys); + 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 *pathkeys, Oid operator, List *hashclauses, - List *outerkeys, List *innerkeys, Cost innerdisbursion); + Path *inner_path, List *hashclauses, Cost innerdisbursion); /* * prototypes for rel.c diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index f074f1eee1f..b0ec64c3e32 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.33 1999/07/27 06:23:11 tgl Exp $ + * $Id: paths.h,v 1.34 1999/08/16 02:17:45 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -43,35 +43,28 @@ extern void update_rels_pathlist_for_joins(Query *root, List *joinrels); extern List *create_or_index_paths(Query *root, RelOptInfo *rel, List *clauses); /* - * hashutils.c - * routines to deal with hash keys and clauses + * pathkeys.c + * utilities for matching and building path keys */ -extern List *group_clauses_by_hashop(List *restrictinfo_list, - Relids inner_relids); +typedef enum +{ + PATHKEYS_EQUAL, /* pathkeys are identical */ + PATHKEYS_BETTER1, /* pathkey 1 is a superset of pathkey 2 */ + PATHKEYS_BETTER2, /* vice versa */ + PATHKEYS_DIFFERENT /* neither pathkey includes the other */ +} PathKeysComparison; -/* - * joinutils.c - * generic join method key/clause routines - */ -extern bool order_joinkeys_by_pathkeys(List *pathkeys, - List *joinkeys, List *joinclauses, int outer_or_inner, - List **matchedJoinKeysPtr, - List **matchedJoinClausesPtr); -extern List *make_pathkeys_from_joinkeys(List *joinkeys, List *tlist, - int outer_or_inner); -extern Path *get_cheapest_path_for_joinkeys(List *joinkeys, - PathOrder *ordering, List *paths, int outer_or_inner); -extern List *new_join_pathkeys(List *outer_pathkeys, - List *join_rel_tlist, List *joinclauses); - -/* - * mergeutils.c - * routines to deal with merge keys and clauses - */ -extern List *group_clauses_by_order(List *restrictinfo_list, - Relids inner_relids); -extern MergeInfo *match_order_mergeinfo(PathOrder *ordering, - List *mergeinfo_list); +extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2); +extern bool pathkeys_contained_in(List *keys1, List *keys2); +extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys); +extern List *build_index_pathkeys(Query *root, RelOptInfo *rel, + RelOptInfo *index); +extern List *build_join_pathkeys(List *outer_pathkeys, + List *join_rel_tlist, List *joinclauses); +extern List *find_mergeclauses_for_pathkeys(List *pathkeys, + List *restrictinfos); +extern List *make_pathkeys_for_mergeclauses(List *mergeclauses, + List *tlist); /* * joinrels.c diff --git a/src/include/optimizer/tlist.h b/src/include/optimizer/tlist.h index 860b077de21..fb08b708352 100644 --- a/src/include/optimizer/tlist.h +++ b/src/include/optimizer/tlist.h @@ -6,7 +6,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: tlist.h,v 1.19 1999/07/15 15:21:23 momjian Exp $ + * $Id: tlist.h,v 1.20 1999/08/16 02:17:45 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -30,4 +30,7 @@ extern List *flatten_tlist(List *tlist); extern List *flatten_tlist_vars(List *full_tlist, List *flat_tlist); +extern Var *get_expr(TargetEntry *tle); +extern Var *get_groupclause_expr(GroupClause *groupClause, List *targetList); + #endif /* TLIST_H */ |