granicus.if.org Git - postgresql/blob - src/backend/optimizer/path/pathkey.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * joinutils.c
   4  *        Utilities for matching and building join and path keys
   5  *
   6  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/pathkey.c,v 1.1 1999/02/18 19:58:52 momjian Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include "postgres.h"
  15
  16 #include "nodes/pg_list.h"
  17 #include "nodes/relation.h"
  18 #include "nodes/plannodes.h"
  19
  20 #include "optimizer/internal.h"
  21 #include "optimizer/paths.h"
  22 #include "optimizer/var.h"
  23 #include "optimizer/keys.h"
  24 #include "optimizer/tlist.h"
  25 #include "optimizer/joininfo.h"
  26 #include "optimizer/ordering.h"
  27
  28
  29 static int match_pathkey_joinkeys(List *pathkey, List *joinkeys,
  30                                                 int which_subkey);
  31 static bool every_func(List *joinkeys, List *pathkey,
  32                                                 int which_subkey);
  33 static List *new_join_pathkey(List *subkeys, List *considered_subkeys,
  34                                                 List *join_rel_tlist, List *joinclauses);
  35 static List *new_matching_subkeys(Var *subkey, List *considered_subkeys,
  36                                                 List *join_rel_tlist, List *joinclauses);
  37
  38 /****************************************************************************
  39  *              KEY COMPARISONS
  40  ****************************************************************************/
  41
  42 /*
  43  * match_pathkeys_joinkeys
  44  *        Attempts to match the keys of a path against the keys of join clauses.
  45  *        This is done by looking for a matching join key in 'joinkeys' for
  46  *        every path key in the list 'path.keys'. If there is a matching join key
  47  *        (not necessarily unique) for every path key, then the list of
  48  *        corresponding join keys and join clauses are returned in the order in
  49  *        which the keys matched the path keys.
  50  *
  51  * 'pathkeys' is a list of path keys:
  52  *              ( ( (var) (var) ... ) ( (var) ... ) )
  53  * 'joinkeys' is a list of join keys:
  54  *              ( (outer inner) (outer inner) ... )
  55  * 'joinclauses' is a list of clauses corresponding to the join keys in
  56  *              'joinkeys'
  57  * 'which_subkey' is a flag that selects the desired subkey of a join key
  58  *              in 'joinkeys'
  59  *
  60  * Returns the join keys and corresponding join clauses in a list if all
  61  * of the path keys were matched:
  62  *              (
  63  *               ( (outerkey0 innerkey0) ... (outerkeyN innerkeyN) )
  64  *               ( clause0 ... clauseN )
  65  *              )
  66  * and nil otherwise.
  67  *
  68  * Returns a list of matched join keys and a list of matched join clauses
  69  * in matchedJoinClausesPtr.  - ay 11/94
  70  */
  71 List *
  72 match_pathkeys_joinkeys(List *pathkeys,
  73                                                 List *joinkeys,
  74                                                 List *joinclauses,
  75                                                 int which_subkey,
  76                                                 List **matchedJoinClausesPtr)
  77 {
  78         List       *matched_joinkeys = NIL;
  79         List       *matched_joinclauses = NIL;
  80         List       *pathkey = NIL;
  81         List       *i = NIL;
  82         int                     matched_joinkey_index = -1;
  83
  84         foreach(i, pathkeys)
  85         {
  86                 pathkey = lfirst(i);
  87                 matched_joinkey_index = match_pathkey_joinkeys(pathkey, joinkeys, which_subkey);
  88
  89                 if (matched_joinkey_index != -1)
  90                 {
  91                         List       *xjoinkey = nth(matched_joinkey_index, joinkeys);
  92                         List       *joinclause = nth(matched_joinkey_index, joinclauses);
  93
  94                         /* XXX was "push" function */
  95                         matched_joinkeys = lappend(matched_joinkeys, xjoinkey);
  96                         matched_joinkeys = nreverse(matched_joinkeys);
  97
  98                         matched_joinclauses = lappend(matched_joinclauses, joinclause);
  99                         matched_joinclauses = nreverse(matched_joinclauses);
 100                         joinkeys = LispRemove(xjoinkey, joinkeys);
 101                 }
 102                 else
 103                         return NIL;
 104
 105         }
 106         if (matched_joinkeys == NULL ||
 107                 length(matched_joinkeys) != length(pathkeys))
 108                 return NIL;
 109
 110         *matchedJoinClausesPtr = nreverse(matched_joinclauses);
 111         return nreverse(matched_joinkeys);
 112 }
 113
 114 /*
 115  * match_pathkey_joinkeys
 116  *        Returns the 0-based index into 'joinkeys' of the first joinkey whose
 117  *        outer or inner subkey matches any subkey of 'pathkey'.
 118  */
 119 static int
 120 match_pathkey_joinkeys(List *pathkey,
 121                                            List *joinkeys,
 122                                            int which_subkey)
 123 {
 124         Var                *path_subkey;
 125         int                     pos;
 126         List       *i = NIL;
 127         List       *x = NIL;
 128         JoinKey    *jk;
 129
 130         foreach(i, pathkey)
 131         {
 132                 path_subkey = (Var *) lfirst(i);
 133                 pos = 0;
 134                 foreach(x, joinkeys)
 135                 {
 136                         jk = (JoinKey *) lfirst(x);
 137                         if (var_equal(path_subkey,
 138                                                   extract_join_subkey(jk, which_subkey)))
 139                                 return pos;
 140                         pos++;
 141                 }
 142         }
 143         return -1;                                      /* no index found       */
 144 }
 145
 146 /*
 147  * match_paths_joinkeys
 148  *        Attempts to find a path in 'paths' whose keys match a set of join
 149  *        keys 'joinkeys'.      To match,
 150  *        1. the path node ordering must equal 'ordering'.
 151  *        2. each subkey of a given path must match(i.e., be(var_equal) to) the
 152  *               appropriate subkey of the corresponding join key in 'joinkeys',
 153  *               i.e., the Nth path key must match its subkeys against the subkey of
 154  *               the Nth join key in 'joinkeys'.
 155  *
 156  * 'joinkeys' is the list of key pairs to which the path keys must be
 157  *              matched
 158  * 'ordering' is the ordering of the(outer) path to which 'joinkeys'
 159  *              must correspond
 160  * 'paths' is a list of(inner) paths which are to be matched against
 161  *              each join key in 'joinkeys'
 162  * 'which_subkey' is a flag that selects the desired subkey of a join key
 163  *              in 'joinkeys'
 164  *
 165  * Returns the matching path node if one exists, nil otherwise.
 166  */
 167 static bool
 168 every_func(List *joinkeys, List *pathkey, int which_subkey)
 169 {
 170         JoinKey    *xjoinkey;
 171         Var                *temp;
 172         Var                *tempkey = NULL;
 173         bool            found = false;
 174         List       *i = NIL;
 175         List       *j = NIL;
 176
 177         foreach(i, joinkeys)
 178         {
 179                 xjoinkey = (JoinKey *) lfirst(i);
 180                 found = false;
 181                 foreach(j, pathkey)
 182                 {
 183                         temp = (Var *) lfirst((List *) lfirst(j));
 184                         if (temp == NULL)
 185                                 continue;
 186                         tempkey = extract_join_subkey(xjoinkey, which_subkey);
 187                         if (var_equal(tempkey, temp))
 188                         {
 189                                 found = true;
 190                                 break;
 191                         }
 192                 }
 193                 if (found == false)
 194                         return false;
 195         }
 196         return found;
 197 }
 198
 199
 200 /*
 201  * match_paths_joinkeys -
 202  *        find the cheapest path that matches the join keys
 203  */
 204 Path *
 205 match_paths_joinkeys(List *joinkeys,
 206                                          PathOrder *ordering,
 207                                          List *paths,
 208                                          int which_subkey)
 209 {
 210         Path       *matched_path = NULL;
 211         bool            key_match = false;
 212         List       *i = NIL;
 213
 214         foreach(i, paths)
 215         {
 216                 Path       *path = (Path *) lfirst(i);
 217                 int                     better_sort;
 218
 219                 key_match = every_func(joinkeys, path->pathkeys, which_subkey);
 220
 221                 if (pathorder_match(ordering, path->pathorder, &better_sort) &&
 222                         better_sort == 0 &&
 223                         length(joinkeys) == length(path->pathkeys) && key_match)
 224                 {
 225
 226                         if (matched_path)
 227                         {
 228                                 if (path->path_cost < matched_path->path_cost)
 229                                         matched_path = path;
 230                         }
 231                         else
 232                                 matched_path = path;
 233                 }
 234         }
 235         return matched_path;
 236 }
 237
 238
 239
 240 /*
 241  * extract_path_keys
 242  *        Builds a subkey list for a path by pulling one of the subkeys from
 243  *        a list of join keys 'joinkeys' and then finding the var node in the
 244  *        target list 'tlist' that corresponds to that subkey.
 245  *
 246  * 'joinkeys' is a list of join key pairs
 247  * 'tlist' is a relation target list
 248  * 'which_subkey' is a flag that selects the desired subkey of a join key
 249  *              in 'joinkeys'
 250  *
 251  * Returns a list of pathkeys: ((tlvar1)(tlvar2)...(tlvarN)).
 252  * It is a list of lists because of multi-key indexes.
 253  */
 254 List *
 255 extract_path_keys(List *joinkeys,
 256                                   List *tlist,
 257                                   int which_subkey)
 258 {
 259         List       *pathkeys = NIL;
 260         List       *jk;
 261
 262         foreach(jk, joinkeys)
 263         {
 264                 JoinKey    *jkey = (JoinKey *) lfirst(jk);
 265                 Var                *var,
 266                                    *key;
 267                 List       *p;
 268
 269                 /*
 270                  * find the right Var in the target list for this key
 271                  */
 272                 var = (Var *) extract_join_subkey(jkey, which_subkey);
 273                 key = (Var *) matching_tlist_var(var, tlist);
 274
 275                 /*
 276                  * Include it in the pathkeys list if we haven't already done so
 277                  */
 278                 foreach(p, pathkeys)
 279                 {
 280                         Var                *pkey = lfirst((List *) lfirst(p));          /* XXX fix me */
 281
 282                         if (key == pkey)
 283                                 break;
 284                 }
 285                 if (p != NIL)
 286                         continue;                       /* key already in pathkeys */
 287
 288                 pathkeys = lappend(pathkeys, lcons(key, NIL));
 289         }
 290         return pathkeys;
 291 }
 292
 293
 294 /****************************************************************************
 295  *              NEW PATHKEY FORMATION
 296  ****************************************************************************/
 297
 298 /*
 299  * new_join_pathkeys
 300  *        Find the path keys for a join relation by finding all vars in the list
 301  *        of join clauses 'joinclauses' such that:
 302  *              (1) the var corresponding to the outer join relation is a
 303  *                      key on the outer path
 304  *              (2) the var appears in the target list of the join relation
 305  *        In other words, add to each outer path key the inner path keys that
 306  *        are required for qualification.
 307  *
 308  * 'outer_pathkeys' is the list of the outer path's path keys
 309  * 'join_rel_tlist' is the target list of the join relation
 310  * 'joinclauses' is the list of restricting join clauses
 311  *
 312  * Returns the list of new path keys.
 313  *
 314  */
 315 List *
 316 new_join_pathkeys(List *outer_pathkeys,
 317                                   List *join_rel_tlist,
 318                                   List *joinclauses)
 319 {
 320         List       *outer_pathkey = NIL;
 321         List       *t_list = NIL;
 322         List       *x;
 323         List       *i = NIL;
 324
 325         foreach(i, outer_pathkeys)
 326         {
 327                 outer_pathkey = lfirst(i);
 328                 x = new_join_pathkey(outer_pathkey, NIL, join_rel_tlist, joinclauses);
 329                 if (x != NIL)
 330                         t_list = lappend(t_list, x);
 331         }
 332         return t_list;
 333 }
 334
 335 /*
 336  * new_join_pathkey
 337  *        Finds new vars that become subkeys due to qualification clauses that
 338  *        contain any previously considered subkeys.  These new subkeys plus the
 339  *        subkeys from 'subkeys' form a new pathkey for the join relation.
 340  *
 341  *        Note that each returned subkey is the var node found in
 342  *        'join_rel_tlist' rather than the joinclause var node.
 343  *
 344  * 'subkeys' is a list of subkeys for which matching subkeys are to be
 345  *              found
 346  * 'considered_subkeys' is the current list of all subkeys corresponding
 347  *              to a given pathkey
 348  *
 349  * Returns a new pathkey(list of subkeys).
 350  *
 351  */
 352 static List *
 353 new_join_pathkey(List *subkeys,
 354                                  List *considered_subkeys,
 355                                  List *join_rel_tlist,
 356                                  List *joinclauses)
 357 {
 358         List       *t_list = NIL;
 359         Var                *subkey;
 360         List       *i = NIL;
 361         List       *matched_subkeys = NIL;
 362         Expr       *tlist_key = (Expr *) NULL;
 363         List       *newly_considered_subkeys = NIL;
 364
 365         foreach(i, subkeys)
 366         {
 367                 subkey = (Var *) lfirst(i);
 368                 if (subkey == NULL)
 369                         break;                          /* XXX something is wrong */
 370                 matched_subkeys = new_matching_subkeys(subkey, considered_subkeys,
 371                                                                  join_rel_tlist, joinclauses);
 372                 tlist_key = matching_tlist_var(subkey, join_rel_tlist);
 373                 newly_considered_subkeys = NIL;
 374
 375                 if (tlist_key)
 376                 {
 377                         if (!member(tlist_key, matched_subkeys))
 378                                 newly_considered_subkeys = lcons(tlist_key, matched_subkeys);
 379                 }
 380                 else
 381                         newly_considered_subkeys = matched_subkeys;
 382
 383                 considered_subkeys =  append(considered_subkeys, newly_considered_subkeys);
 384
 385                 t_list = nconc(t_list, newly_considered_subkeys);
 386         }
 387         return t_list;
 388 }
 389
 390 /*
 391  * new_matching_subkeys
 392  *        Returns a list of new subkeys:
 393  *        (1) which are not listed in 'considered_subkeys'
 394  *        (2) for which the "other" variable in some clause in 'joinclauses' is
 395  *                'subkey'
 396  *        (3) which are mentioned in 'join_rel_tlist'
 397  *
 398  *        Note that each returned subkey is the var node found in
 399  *        'join_rel_tlist' rather than the joinclause var node.
 400  *
 401  * 'subkey' is the var node for which we are trying to find matching
 402  *              clauses
 403  *
 404  * Returns a list of new subkeys.
 405  *
 406  */
 407 static List *
 408 new_matching_subkeys(Var *subkey,
 409                                          List *considered_subkeys,
 410                                          List *join_rel_tlist,
 411                                          List *joinclauses)
 412 {
 413         List       *t_list = NIL;
 414         Expr       *joinclause;
 415         List       *i;
 416         Expr       *tlist_other_var;
 417
 418         foreach(i, joinclauses)
 419         {
 420                 joinclause = lfirst(i);
 421                 tlist_other_var = matching_tlist_var(
 422                                                                         other_join_clause_var(subkey, joinclause),
 423                                                                         join_rel_tlist);
 424
 425                 if (tlist_other_var &&
 426                         !(member(tlist_other_var, considered_subkeys)))
 427                 {
 428
 429                         /* XXX was "push" function      */
 430                         considered_subkeys = lappend(considered_subkeys,
 431                                                                                  tlist_other_var);
 432
 433                         /*
 434                          * considered_subkeys = nreverse(considered_subkeys); XXX -- I
 435                          * am not sure of this.
 436                          */
 437
 438                         t_list = lappend(t_list, tlist_other_var);
 439                 }
 440         }
 441         return t_list;
 442 }