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