From 8ab72a38df82a863f787c65a4b8998893a946377 Mon Sep 17 00:00:00 2001 From: Bruce Momjian Date: Fri, 19 Feb 1999 02:05:20 +0000 Subject: [PATCH] optimizer cleanup --- src/backend/optimizer/README | 16 ++--- src/backend/optimizer/path/pathkey.c | 115 +++++++++++++++++------------------ src/backend/optimizer/util/keys.c | 10 +-- src/include/optimizer/keys.h | 4 +- src/include/optimizer/paths.h | 8 +-- 5 files changed, 76 insertions(+), 77 deletions(-) diff --git a/src/backend/optimizer/README b/src/backend/optimizer/README index e7aa29295f..2b6ff52c5f 100644 --- a/src/backend/optimizer/README +++ b/src/backend/optimizer/README @@ -5,12 +5,14 @@ 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. +sequential and index scans, and add it to RelOptInfo.pathlist. Also +create RelOptInfo.joininfo that lists all the joins that involve this +relation. -2) Join each RelOptInfo to each other RelOptInfo as specified in the -WHERE clause. At this point each RelOptInfo is a single relation, so -you are joining every relation to every relation as joined in the WHERE -clause. +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 @@ -137,8 +139,8 @@ Optimizer Structures RelOptInfo - a relation or joined relations - RestrictInfo - restriction clauses - JoinInfo - join clauses + RestrictInfo - restriction clauses, like "x = 3" + JoinInfo - join clauses, including the relids needed for the join Path - every way to generate a RelOptInfo(sequential,index,joins) IndexPath - index scans diff --git a/src/backend/optimizer/path/pathkey.c b/src/backend/optimizer/path/pathkey.c index 50196f0379..92b27a774b 100644 --- a/src/backend/optimizer/path/pathkey.c +++ b/src/backend/optimizer/path/pathkey.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/pathkey.c,v 1.1 1999/02/18 19:58:52 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/pathkey.c,v 1.2 1999/02/19 02:05:15 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -27,9 +27,9 @@ static int match_pathkey_joinkeys(List *pathkey, List *joinkeys, - int which_subkey); + int outer_or_inner); static bool every_func(List *joinkeys, List *pathkey, - int which_subkey); + int outer_or_inner); static List *new_join_pathkey(List *subkeys, List *considered_subkeys, List *join_rel_tlist, List *joinclauses); static List *new_matching_subkeys(Var *subkey, List *considered_subkeys, @@ -54,7 +54,7 @@ static List *new_matching_subkeys(Var *subkey, List *considered_subkeys, * ( (outer inner) (outer inner) ... ) * 'joinclauses' is a list of clauses corresponding to the join keys in * 'joinkeys' - * 'which_subkey' is a flag that selects the desired subkey of a join key + * 'outer_or_inner' is a flag that selects the desired subkey of a join key * in 'joinkeys' * * Returns the join keys and corresponding join clauses in a list if all @@ -72,7 +72,7 @@ List * match_pathkeys_joinkeys(List *pathkeys, List *joinkeys, List *joinclauses, - int which_subkey, + int outer_or_inner, List **matchedJoinClausesPtr) { List *matched_joinkeys = NIL; @@ -84,19 +84,17 @@ match_pathkeys_joinkeys(List *pathkeys, foreach(i, pathkeys) { pathkey = lfirst(i); - matched_joinkey_index = match_pathkey_joinkeys(pathkey, joinkeys, which_subkey); + matched_joinkey_index = match_pathkey_joinkeys(pathkey, joinkeys, + outer_or_inner); if (matched_joinkey_index != -1) { List *xjoinkey = nth(matched_joinkey_index, joinkeys); List *joinclause = nth(matched_joinkey_index, joinclauses); - /* XXX was "push" function */ - matched_joinkeys = lappend(matched_joinkeys, xjoinkey); - matched_joinkeys = nreverse(matched_joinkeys); + matched_joinkeys = lcons(xjoinkey, matched_joinkeys); + matched_joinclauses = lcons(joinclause, matched_joinclauses); - matched_joinclauses = lappend(matched_joinclauses, joinclause); - matched_joinclauses = nreverse(matched_joinclauses); joinkeys = LispRemove(xjoinkey, joinkeys); } else @@ -111,6 +109,7 @@ match_pathkeys_joinkeys(List *pathkeys, return nreverse(matched_joinkeys); } + /* * match_pathkey_joinkeys * Returns the 0-based index into 'joinkeys' of the first joinkey whose @@ -119,7 +118,7 @@ match_pathkeys_joinkeys(List *pathkeys, static int match_pathkey_joinkeys(List *pathkey, List *joinkeys, - int which_subkey) + int outer_or_inner) { Var *path_subkey; int pos; @@ -135,7 +134,7 @@ match_pathkey_joinkeys(List *pathkey, { jk = (JoinKey *) lfirst(x); if (var_equal(path_subkey, - extract_join_subkey(jk, which_subkey))) + extract_join_key(jk, outer_or_inner))) return pos; pos++; } @@ -143,6 +142,7 @@ match_pathkey_joinkeys(List *pathkey, return -1; /* no index found */ } + /* * match_paths_joinkeys * Attempts to find a path in 'paths' whose keys match a set of join @@ -159,53 +159,16 @@ match_pathkey_joinkeys(List *pathkey, * must correspond * 'paths' is a list of(inner) paths which are to be matched against * each join key in 'joinkeys' - * 'which_subkey' is a flag that selects the desired subkey of a join key + * 'outer_or_inner' is a flag that selects the desired subkey of a join key * in 'joinkeys' * - * Returns the matching path node if one exists, nil otherwise. - */ -static bool -every_func(List *joinkeys, List *pathkey, int which_subkey) -{ - JoinKey *xjoinkey; - Var *temp; - Var *tempkey = NULL; - bool found = false; - List *i = NIL; - List *j = NIL; - - foreach(i, joinkeys) - { - xjoinkey = (JoinKey *) lfirst(i); - found = false; - foreach(j, pathkey) - { - temp = (Var *) lfirst((List *) lfirst(j)); - if (temp == NULL) - continue; - tempkey = extract_join_subkey(xjoinkey, which_subkey); - if (var_equal(tempkey, temp)) - { - found = true; - break; - } - } - if (found == false) - return false; - } - return found; -} - - -/* - * match_paths_joinkeys - - * find the cheapest path that matches the join keys + * Find the cheapest path that matches the join keys */ Path * match_paths_joinkeys(List *joinkeys, PathOrder *ordering, List *paths, - int which_subkey) + int outer_or_inner) { Path *matched_path = NULL; bool key_match = false; @@ -216,13 +179,12 @@ match_paths_joinkeys(List *joinkeys, Path *path = (Path *) lfirst(i); int better_sort; - key_match = every_func(joinkeys, path->pathkeys, which_subkey); + key_match = every_func(joinkeys, path->pathkeys, outer_or_inner); if (pathorder_match(ordering, path->pathorder, &better_sort) && better_sort == 0 && length(joinkeys) == length(path->pathkeys) && key_match) { - if (matched_path) { if (path->path_cost < matched_path->path_cost) @@ -236,7 +198,6 @@ match_paths_joinkeys(List *joinkeys, } - /* * extract_path_keys * Builds a subkey list for a path by pulling one of the subkeys from @@ -245,7 +206,7 @@ match_paths_joinkeys(List *joinkeys, * * 'joinkeys' is a list of join key pairs * 'tlist' is a relation target list - * 'which_subkey' is a flag that selects the desired subkey of a join key + * 'outer_or_inner' is a flag that selects the desired subkey of a join key * in 'joinkeys' * * Returns a list of pathkeys: ((tlvar1)(tlvar2)...(tlvarN)). @@ -254,7 +215,7 @@ match_paths_joinkeys(List *joinkeys, List * extract_path_keys(List *joinkeys, List *tlist, - int which_subkey) + int outer_or_inner) { List *pathkeys = NIL; List *jk; @@ -269,7 +230,7 @@ extract_path_keys(List *joinkeys, /* * find the right Var in the target list for this key */ - var = (Var *) extract_join_subkey(jkey, which_subkey); + var = (Var *) extract_join_key(jkey, outer_or_inner); key = (Var *) matching_tlist_var(var, tlist); /* @@ -291,6 +252,42 @@ extract_path_keys(List *joinkeys, } +/* + * every_func + */ +static bool +every_func(List *joinkeys, List *pathkey, int outer_or_inner) +{ + JoinKey *xjoinkey; + Var *temp; + Var *tempkey = NULL; + bool found = false; + List *i = NIL; + List *j = NIL; + + foreach(i, joinkeys) + { + xjoinkey = (JoinKey *) lfirst(i); + found = false; + foreach(j, pathkey) + { + temp = (Var *) lfirst((List *) lfirst(j)); + if (temp == NULL) + continue; + tempkey = extract_join_key(xjoinkey, outer_or_inner); + if (var_equal(tempkey, temp)) + { + found = true; + break; + } + } + if (found == false) + return false; + } + return found; +} + + /**************************************************************************** * NEW PATHKEY FORMATION ****************************************************************************/ diff --git a/src/backend/optimizer/util/keys.c b/src/backend/optimizer/util/keys.c index cfd2f26d26..123b6dc4cb 100644 --- a/src/backend/optimizer/util/keys.c +++ b/src/backend/optimizer/util/keys.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/keys.c,v 1.17 1999/02/13 23:16:45 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/keys.c,v 1.18 1999/02/19 02:05:16 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -80,17 +80,17 @@ equal_indexkey_var(int index_key, Var *var) } /* - * extract_join_subkey + * extract_join_key * Returns the subkey in a join key corresponding to the outer or inner * relation. * */ Var * -extract_join_subkey(JoinKey *jk, int which_subkey) +extract_join_key(JoinKey *jk, int outer_or_inner) { Var *retval; - switch (which_subkey) + switch (outer_or_inner) { case OUTER: retval = jk->outer; @@ -99,7 +99,7 @@ extract_join_subkey(JoinKey *jk, int which_subkey) retval = jk->inner; break; default: /* do nothing */ - elog(DEBUG, "extract_join_subkey with neither INNER or OUTER"); + elog(DEBUG, "extract_join_key with neither INNER or OUTER"); retval = NULL; } return retval; diff --git a/src/include/optimizer/keys.h b/src/include/optimizer/keys.h index 4a23680b75..fad0117c3a 100644 --- a/src/include/optimizer/keys.h +++ b/src/include/optimizer/keys.h @@ -6,7 +6,7 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: keys.h,v 1.12 1999/02/13 23:21:49 momjian Exp $ + * $Id: keys.h,v 1.13 1999/02/19 02:05:18 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -17,7 +17,7 @@ #include "nodes/relation.h" extern bool match_indexkey_operand(int indexkey, Var *operand, RelOptInfo *rel); -extern Var *extract_join_subkey(JoinKey *jk, int which_subkey); +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); diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index ca84268b1d..413d536807 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.22 1999/02/18 04:45:36 momjian Exp $ + * $Id: paths.h,v 1.23 1999/02/19 02:05:20 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -55,12 +55,12 @@ extern List *group_clauses_by_hashop(List *restrictinfo_list, * generic join method key/clause routines */ extern List *match_pathkeys_joinkeys(List *pathkeys, - List *joinkeys, List *joinclauses, int which_subkey, + List *joinkeys, List *joinclauses, int outer_or_inner, List **matchedJoinClausesPtr); extern List *extract_path_keys(List *joinkeys, List *tlist, - int which_subkey); + int outer_or_inner); extern Path *match_paths_joinkeys(List *joinkeys, PathOrder *ordering, - List *paths, int which_subkey); + List *paths, int outer_or_inner); extern List *new_join_pathkeys(List *outer_pathkeys, List *join_rel_tlist, List *joinclauses); -- 2.11.0