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