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

   1 /*-------------------------------------------------------------------------
   2  *
   3  * predmig.c
   4  *
   5  *
   6  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/predmig.c,v 1.18 1999/02/13 23:16:22 momjian Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 /*
  15 ** DESCRIPTION
  16 ** Main Routines to handle Predicate Migration (i.e. correct optimization
  17 ** of queries with expensive functions.)
  18 **
  19 **        The reasoning behind some of these algorithms is rather detailed.
  20 ** Have a look at Sequoia Tech Report 92/13 for more info.      Also
  21 ** see Monma and Sidney's paper "Sequencing with Series-Parallel
  22 ** Precedence Constraints", in "Mathematics of Operations Research",
  23 ** volume 4 (1979),  pp. 215-224.
  24 **
  25 **        The main thing that this code does that wasn't handled in xfunc.c is
  26 ** it considers the possibility that two joins in a stream may not
  27 ** be ordered by ascending rank -- in such a scenario, it may be optimal
  28 ** to pullup more restrictions than we did via xfunc_try_pullup.
  29 **
  30 **        This code in some sense generalizes xfunc_try_pullup; if you
  31 ** run postgres -x noprune, you'll turn off xfunc_try_pullup, and this
  32 ** code will do everything that xfunc_try_pullup would have, and maybe
  33 ** more.  However, this results in no pruning, which may slow down the
  34 ** optimizer and/or cause the system to run out of memory.
  35 **                                                                                 -- JMH, 11/13/92
  36 */
  37
  38 #include "nodes/pg_list.h"
  39 #include "nodes/nodes.h"
  40 #include "nodes/primnodes.h"
  41 #include "nodes/relation.h"
  42 #include "utils/palloc.h"
  43 #include "utils/elog.h"
  44 #include "optimizer/xfunc.h"
  45 #include "optimizer/pathnode.h"
  46 #include "optimizer/internal.h"
  47 #include "optimizer/cost.h"
  48 #include "optimizer/keys.h"
  49 #include "optimizer/tlist.h"
  50
  51 #define is_clause(node) (get_cinfo(node))               /* a stream node
  52                                                                                                  * represents a clause
  53                                                                                                  * (not a join) iff it has
  54                                                                                                  * a non-NULL cinfo field */
  55
  56 static void xfunc_predmig(JoinPath pathnode, Stream streamroot,
  57                           Stream laststream, bool *progressp);
  58 static bool xfunc_series_llel(Stream stream);
  59 static bool xfunc_llel_chains(Stream root, Stream bottom);
  60 static Stream xfunc_complete_stream(Stream stream);
  61 static bool xfunc_prdmig_pullup(Stream origstream, Stream pullme,
  62                                         JoinPath joinpath);
  63 static void xfunc_form_groups(Stream root, Stream bottom);
  64 static void xfunc_free_stream(Stream root);
  65 static Stream xfunc_add_clauses(Stream current);
  66 static void xfunc_setup_group(Stream node, Stream bottom);
  67 static Stream xfunc_streaminsert(RestrictInfo restrictinfo, Stream current,
  68                                    int clausetype);
  69 static int      xfunc_num_relids(Stream node);
  70 static StreamPtr xfunc_get_downjoin(Stream node);
  71 static StreamPtr xfunc_get_upjoin(Stream node);
  72 static Stream xfunc_stream_qsort(Stream root, Stream bottom);
  73 static int      xfunc_stream_compare(void *arg1, void *arg2);
  74 static bool xfunc_check_stream(Stream node);
  75 static bool xfunc_in_stream(Stream node, Stream stream);
  76
  77 /* -----------------   MAIN FUNCTIONS ------------------------ */
  78 /*
  79 ** xfunc_do_predmig
  80 **        wrapper for Predicate Migration.      It calls xfunc_predmig until no
  81 ** more progress is made.
  82 **        return value says if any changes were ever made.
  83 */
  84 bool
  85 xfunc_do_predmig(Path root)
  86 {
  87         bool            progress,
  88                                 changed = false;
  89
  90         if (is_join(root))
  91                 do
  92                 {
  93                         progress = false;
  94                         Assert(IsA(root, JoinPath));
  95                         xfunc_predmig((JoinPath) root, (Stream) NULL, (Stream) NULL,
  96                                                   &progress);
  97                         if (changed && progress)
  98                                 elog(DEBUG, "Needed to do a second round of predmig!\n");
  99                         if (progress)
 100                                 changed = true;
 101                 } while (progress);
 102         return changed;
 103 }
 104
 105
 106 /*
 107  ** xfunc_predmig
 108  **  The main routine for Predicate Migration.  It traverses a join tree,
 109  ** and for each root-to-leaf path in the plan tree it constructs a
 110  ** "Stream", which it passes to xfunc_series_llel for optimization.
 111  ** Destructively modifies the join tree (via predicate pullup).
 112  */
 113 static void
 114 xfunc_predmig(JoinPath pathnode,/* root of the join tree */
 115                           Stream streamroot,
 116                           Stream laststream,/* for recursive calls -- these are the
 117                                                                  * root of the stream under construction,
 118                                                                  * and the lowest node created so far */
 119                           bool *progressp)
 120 {
 121         Stream          newstream;
 122
 123         /*
 124          * * traverse the join tree dfs-style, constructing a stream as you
 125          * go. * When you hit a scan node, pass the stream off to
 126          * xfunc_series_llel.
 127          */
 128
 129         /* sanity check */
 130         if ((!streamroot && laststream) ||
 131                 (streamroot && !laststream))
 132                 elog(ERROR, "called xfunc_predmig with bad inputs");
 133         if (streamroot)
 134                 Assert(xfunc_check_stream(streamroot));
 135
 136         /* add path node to stream */
 137         newstream = RMakeStream();
 138         if (!streamroot)
 139                 streamroot = newstream;
 140         set_upstream(newstream, (StreamPtr) laststream);
 141         if (laststream)
 142                 set_downstream(laststream, (StreamPtr) newstream);
 143         set_downstream(newstream, (StreamPtr) NULL);
 144         set_pathptr(newstream, (pathPtr) pathnode);
 145         set_cinfo(newstream, (RestrictInfo) NULL);
 146         set_clausetype(newstream, XFUNC_UNKNOWN);
 147
 148         /* base case: we're at a leaf, call xfunc_series_llel */
 149         if (!is_join(pathnode))
 150         {
 151                 /* form a fleshed-out copy of the stream */
 152                 Stream          fullstream = xfunc_complete_stream(streamroot);
 153
 154                 /* sort it via series-llel */
 155                 if (xfunc_series_llel(fullstream))
 156                         *progressp = true;
 157
 158                 /* free up the copy */
 159                 xfunc_free_stream(fullstream);
 160         }
 161         else
 162         {
 163                 /* visit left child */
 164                 xfunc_predmig((JoinPath) get_outerjoinpath(pathnode),
 165                                           streamroot, newstream, progressp);
 166
 167                 /* visit right child */
 168                 xfunc_predmig((JoinPath) get_innerjoinpath(pathnode),
 169                                           streamroot, newstream, progressp);
 170         }
 171
 172         /* remove this node */
 173         if (get_upstream(newstream))
 174                 set_downstream((Stream) get_upstream(newstream), (StreamPtr) NULL);
 175         pfree(newstream);
 176 }
 177
 178 /*
 179  ** xfunc_series_llel
 180  **    A flavor of Monma and Sidney's Series-Parallel algorithm.
 181  ** Traverse stream downwards.  When you find a node with restrictions on it,
 182  ** call xfunc_llel_chains on the substream from root to that node.
 183  */
 184 static bool
 185 xfunc_series_llel(Stream stream)
 186 {
 187         Stream          temp,
 188                                 next;
 189         bool            progress = false;
 190
 191         for (temp = stream; temp != (Stream) NULL; temp = next)
 192         {
 193                 next = (Stream) xfunc_get_downjoin(temp);
 194
 195                 /*
 196                  * * if there are restrictions/secondary join clauses above this *
 197                  * node, call xfunc_llel_chains
 198                  */
 199                 if (get_upstream(temp) && is_clause((Stream) get_upstream(temp)))
 200                         if (xfunc_llel_chains(stream, temp))
 201                                 progress = true;
 202         }
 203         return progress;
 204 }
 205
 206 /*
 207  ** xfunc_llel_chains
 208  **    A flavor of Monma and Sidney's Parallel Chains algorithm.
 209  ** Given a stream which has been well-ordered except for its lowermost
 210  ** restrictions/2-ary joins, pull up the restrictions/2-arys as appropriate.
 211  ** What that means here is to form groups in the chain above the lowest
 212  ** join node above bottom inclusive, and then take all the restrictions
 213  ** following bottom, and try to pull them up as far as possible.
 214  */
 215 static bool
 216 xfunc_llel_chains(Stream root, Stream bottom)
 217 {
 218         bool            progress = false;
 219         Stream          origstream;
 220         Stream          tmpstream,
 221                                 pathstream;
 222         Stream          rootcopy = root;
 223
 224         Assert(xfunc_check_stream(root));
 225
 226         /* xfunc_prdmig_pullup will need an unmodified copy of the stream */
 227         origstream = (Stream) copyObject((Node) root);
 228
 229         /* form groups among ill-ordered nodes */
 230         xfunc_form_groups(root, bottom);
 231
 232         /* sort chain by rank */
 233         Assert(xfunc_in_stream(bottom, root));
 234         rootcopy = xfunc_stream_qsort(root, bottom);
 235
 236         /*
 237          * * traverse sorted stream -- if any restriction has moved above a
 238          * join, * we must pull it up in the plan.      That is, make plan tree *
 239          * reflect order of sorted stream.
 240          */
 241         for (tmpstream = rootcopy,
 242                  pathstream = (Stream) xfunc_get_downjoin(rootcopy);
 243                  tmpstream != (Stream) NULL && pathstream != (Stream) NULL;
 244                  tmpstream = (Stream) get_downstream(tmpstream))
 245         {
 246                 if (is_clause(tmpstream)
 247                         && get_pathptr(pathstream) != get_pathptr(tmpstream))
 248                 {
 249
 250                         /*
 251                          * * If restriction moved above a Join after sort, we pull it *
 252                          * up in the join plan. *        If restriction moved down, we
 253                          * ignore it. * This is because Joey's Sequoia paper proves
 254                          * that * restrictions should never move down.  If this * one
 255                          * were moved down, it would violate "semantic correctness", *
 256                          * i.e. it would be lower than the attributes it references.
 257                          */
 258                         Assert(xfunc_num_relids(pathstream) > xfunc_num_relids(tmpstream));
 259                         progress = xfunc_prdmig_pullup(origstream, tmpstream,
 260                                                                         (JoinPath) get_pathptr(pathstream));
 261                 }
 262                 if (get_downstream(tmpstream))
 263                         pathstream = (Stream) xfunc_get_downjoin((Stream) get_downstream(tmpstream));
 264         }
 265
 266         /* free up origstream */
 267         xfunc_free_stream(origstream);
 268         return progress;
 269 }
 270
 271 /*
 272  ** xfunc_complete_stream
 273  **   Given a stream composed of join nodes only, make a copy containing the
 274  ** join nodes along with the associated restriction nodes.
 275  */
 276 static Stream
 277 xfunc_complete_stream(Stream stream)
 278 {
 279         Stream          tmpstream,
 280                                 copystream,
 281                                 curstream = (Stream) NULL;
 282
 283         copystream = (Stream) copyObject((Node) stream);
 284         Assert(xfunc_check_stream(copystream));
 285
 286         curstream = copystream;
 287         Assert(!is_clause(curstream));
 288
 289         /* curstream = (Stream)xfunc_get_downjoin(curstream); */
 290
 291         while (curstream != (Stream) NULL)
 292         {
 293                 xfunc_add_clauses(curstream);
 294                 curstream = (Stream) xfunc_get_downjoin(curstream);
 295         }
 296
 297         /* find top of stream and return it */
 298         for (tmpstream = copystream; get_upstream(tmpstream) != (StreamPtr) NULL;
 299                  tmpstream = (Stream) get_upstream(tmpstream))
 300                  /* no body in for loop */ ;
 301
 302         return tmpstream;
 303 }
 304
 305 /*
 306  ** xfunc_prdmig_pullup
 307  **    pullup a clause in a path above joinpath.  Since the JoinPath tree
 308  ** doesn't have upward pointers, it's difficult to deal with.  Thus we
 309  ** require the original stream, which maintains pointers to all the path
 310  ** nodes.      We use the original stream to find out what joins are
 311  ** above the clause.
 312  */
 313 static bool
 314 xfunc_prdmig_pullup(Stream origstream, Stream pullme, JoinPath joinpath)
 315 {
 316         RestrictInfo    restrictinfo = get_cinfo(pullme);
 317         bool            progress = false;
 318         Stream          upjoin,
 319                                 orignode,
 320                                 temp;
 321         int                     whichchild;
 322
 323         /* find node in origstream that contains clause */
 324         for (orignode = origstream;
 325                  orignode != (Stream) NULL
 326                  && get_cinfo(orignode) != restrictinfo;
 327                  orignode = (Stream) get_downstream(orignode))
 328                  /* empty body in for loop */ ;
 329         if (!orignode)
 330                 elog(ERROR, "Didn't find matching node in original stream");
 331
 332
 333         /* pull up this node as far as it should go */
 334         for (upjoin = (Stream) xfunc_get_upjoin(orignode);
 335                  upjoin != (Stream) NULL
 336                  && (JoinPath) get_pathptr((Stream) xfunc_get_downjoin(upjoin))
 337                  != joinpath;
 338                  upjoin = (Stream) xfunc_get_upjoin(upjoin))
 339         {
 340 #ifdef DEBUG
 341                 elog(DEBUG, "pulling up in xfunc_predmig_pullup!");
 342 #endif
 343                 /* move clause up in path */
 344                 if (get_pathptr((Stream) get_downstream(upjoin))
 345                   == (pathPtr) get_outerjoinpath((JoinPath) get_pathptr(upjoin)))
 346                         whichchild = OUTER;
 347                 else
 348                         whichchild = INNER;
 349                 restrictinfo = xfunc_pullup((Path) get_pathptr((Stream) get_downstream(upjoin)),
 350                                                                   (JoinPath) get_pathptr(upjoin),
 351                                                                   restrictinfo,
 352                                                                   whichchild,
 353                                                                   get_clausetype(orignode));
 354                 set_pathptr(pullme, get_pathptr(upjoin));
 355                 /* pullme has been moved into locrestrictinfo */
 356                 set_clausetype(pullme, XFUNC_LOCPRD);
 357
 358                 /*
 359                  * * xfunc_pullup makes new path nodes for children of *
 360                  * get_pathptr(current). We must modify the stream nodes to point *
 361                  * to these path nodes
 362                  */
 363                 if (whichchild == OUTER)
 364                 {
 365                         for (temp = (Stream) get_downstream(upjoin); is_clause(temp);
 366                                  temp = (Stream) get_downstream(temp))
 367                                 set_pathptr
 368                                         (temp, (pathPtr)
 369                                          get_outerjoinpath((JoinPath) get_pathptr(upjoin)));
 370                         set_pathptr
 371                                 (temp,
 372                         (pathPtr) get_outerjoinpath((JoinPath) get_pathptr(upjoin)));
 373                 }
 374                 else
 375                 {
 376                         for (temp = (Stream) get_downstream(upjoin); is_clause(temp);
 377                                  temp = (Stream) get_downstream(temp))
 378                                 set_pathptr
 379                                         (temp, (pathPtr)
 380                                          get_innerjoinpath((JoinPath) get_pathptr(upjoin)));
 381                         set_pathptr
 382                                 (temp, (pathPtr)
 383                                  get_innerjoinpath((JoinPath) get_pathptr(upjoin)));
 384                 }
 385                 progress = true;
 386         }
 387         if (!progress)
 388                 elog(DEBUG, "didn't succeed in pulling up in xfunc_prdmig_pullup");
 389         return progress;
 390 }
 391
 392 /*
 393  ** xfunc_form_groups
 394  **    A group is a pair of stream nodes a,b such that a is constrained to
 395  ** precede b (for instance if a and b are both joins), but rank(a) > rank(b).
 396  ** In such a situation, Monma and Sidney prove that no clauses should end
 397  ** up between a and b, and therefore we may treat them as a group, with
 398  ** selectivity equal to the product of their selectivities, and cost
 399  ** equal to the cost of the first plus the selectivity of the first times the
 400  ** cost of the second.  We define each node to be in a group by itself,
 401  ** and then repeatedly find adjacent groups which are ordered by descending
 402  ** rank, and make larger groups.  You know that two adjacent nodes are in a
 403  ** group together if the lower has groupup set to true.  They will both have
 404  ** the same groupcost and groupsel (since they're in the same group!)
 405  */
 406 static void
 407 xfunc_form_groups(Query *queryInfo, Stream root, Stream bottom)
 408 {
 409         Stream          temp,
 410                                 parent;
 411         int                     lowest = xfunc_num_relids((Stream) xfunc_get_upjoin(bottom));
 412         bool            progress;
 413         LispValue       primjoin;
 414         int                     whichchild;
 415
 416         if (!lowest)
 417                 return;                                 /* no joins in stream, so no groups */
 418
 419         /* initialize groups to be single nodes */
 420         for (temp = root;
 421                  temp != (Stream) NULL && temp != bottom;
 422                  temp = (Stream) get_downstream(temp))
 423         {
 424                 /* if a Join node */
 425                 if (!is_clause(temp))
 426                 {
 427                         if (get_pathptr((Stream) get_downstream(temp))
 428                         == (pathPtr) get_outerjoinpath((JoinPath) get_pathptr(temp)))
 429                                 whichchild = OUTER;
 430                         else
 431                                 whichchild = INNER;
 432                         set_groupcost(temp,
 433                                                   xfunc_join_expense((JoinPath) get_pathptr(temp),
 434                                                                                          whichchild));
 435                         if (primjoin = xfunc_primary_join((JoinPath) get_pathptr(temp)))
 436                         {
 437                                 set_groupsel(temp,
 438                                                          compute_clause_selec(queryInfo,
 439                                                                                                   primjoin, NIL));
 440                         }
 441                         else
 442                                 set_groupsel(temp, 1.0);
 443                 }
 444                 else
 445 /* a restriction, or 2-ary join pred */
 446                 {
 447                         set_groupcost(temp,
 448                                                   xfunc_expense(queryInfo,
 449                                                                                 get_clause(get_cinfo(temp))));
 450                         set_groupsel(temp,
 451                                                  compute_clause_selec(queryInfo,
 452                                                                                           get_clause(get_cinfo(temp)),
 453                                                                                           NIL));
 454                 }
 455                 set_groupup(temp, false);
 456         }
 457
 458         /* make passes upwards, forming groups */
 459         do
 460         {
 461                 progress = false;
 462                 for (temp = (Stream) get_upstream(bottom);
 463                          temp != (Stream) NULL;
 464                          temp = (Stream) get_upstream(temp))
 465                 {
 466                         /* check for grouping with node upstream */
 467                         if (!get_groupup(temp) &&       /* not already grouped */
 468                                 (parent = (Stream) get_upstream(temp)) != (Stream) NULL &&
 469                         /* temp is a join or temp is the top of a group */
 470                                 (is_join((Path) get_pathptr(temp)) ||
 471                                  get_downstream(temp) &&
 472                                  get_groupup((Stream) get_downstream(temp))) &&
 473                                 get_grouprank(parent) < get_grouprank(temp))
 474                         {
 475                                 progress = true;/* we formed a new group */
 476                                 set_groupup(temp, true);
 477                                 set_groupcost(temp,
 478                                                           get_groupcost(temp) +
 479                                                           get_groupsel(temp) * get_groupcost(parent));
 480                                 set_groupsel(temp, get_groupsel(temp) * get_groupsel(parent));
 481
 482                                 /* fix costs and sels of all members of group */
 483                                 xfunc_setup_group(temp, bottom);
 484                         }
 485                 }
 486         } while (progress);
 487 }
 488
 489
 490 /* -------------------                     UTILITY FUNCTIONS     ------------------------- */
 491
 492 /*
 493  ** xfunc_free_stream
 494  **   walk down a stream and pfree it
 495  */
 496 static void
 497 xfunc_free_stream(Stream root)
 498 {
 499         Stream          cur,
 500                                 next;
 501
 502         Assert(xfunc_check_stream(root));
 503
 504         if (root != (Stream) NULL)
 505                 for (cur = root; cur != (Stream) NULL; cur = next)
 506                 {
 507                         next = (Stream) get_downstream(cur);
 508                         pfree(cur);
 509                 }
 510 }
 511
 512 /*
 513  ** xfunc_add<_clauses
 514  **    find any clauses above current, and insert them into stream as
 515  ** appropriate.  Return uppermost clause inserted, or current if none.
 516  */
 517 static Stream
 518 xfunc_add_clauses(Stream current)
 519 {
 520         Stream          topnode = current;
 521         LispValue       temp;
 522         LispValue       primjoin;
 523
 524         /* first add in the local clauses */
 525         foreach(temp, get_loc_restrictinfo((Path) get_pathptr(current)))
 526         {
 527                 topnode = xfunc_streaminsert((RestrictInfo) lfirst(temp), topnode,
 528                                                            XFUNC_LOCPRD);
 529         }
 530
 531         /* and add in the join clauses */
 532         if (IsA(get_pathptr(current), JoinPath))
 533         {
 534                 primjoin = xfunc_primary_join((JoinPath) get_pathptr(current));
 535                 foreach(temp, get_pathrestrictinfo((JoinPath) get_pathptr(current)))
 536                 {
 537                         if (!equal(get_clause((RestrictInfo) lfirst(temp)), primjoin))
 538                                 topnode = xfunc_streaminsert((RestrictInfo) lfirst(temp), topnode,
 539                                                                            XFUNC_JOINPRD);
 540                 }
 541         }
 542         return topnode;
 543 }
 544
 545
 546 /*
 547  ** xfunc_setup_group
 548  **   find all elements of stream that are grouped with node and are above
 549  ** bottom, and set their groupcost and groupsel to be the same as node's.
 550  */
 551 static void
 552 xfunc_setup_group(Stream node, Stream bottom)
 553 {
 554         Stream          temp;
 555
 556         if (node != bottom)
 557                 /* traverse downwards */
 558                 for (temp = (Stream) get_downstream(node);
 559                          temp != (Stream) NULL && temp != bottom;
 560                          temp = (Stream) get_downstream(temp))
 561                 {
 562                         if (!get_groupup(temp))
 563                                 break;
 564                         else
 565                         {
 566                                 set_groupcost(temp, get_groupcost(node));
 567                                 set_groupsel(temp, get_groupsel(node));
 568                         }
 569                 }
 570
 571         /* traverse upwards */
 572         for (temp = (Stream) get_upstream(node); temp != (Stream) NULL;
 573                  temp = (Stream) get_upstream(temp))
 574         {
 575                 if (!get_groupup((Stream) get_downstream(temp)))
 576                         break;
 577                 else
 578                 {
 579                         set_groupcost(temp, get_groupcost(node));
 580                         set_groupsel(temp, get_groupsel(node));
 581                 }
 582         }
 583 }
 584
 585
 586 /*
 587  ** xfunc_streaminsert
 588  **    Make a new Stream node to hold clause, and insert it above current.
 589  ** Return new node.
 590  */
 591 static Stream
 592 xfunc_streaminsert(RestrictInfo restrictinfo,
 593                                    Stream current,
 594                                    int clausetype)              /* XFUNC_LOCPRD or XFUNC_JOINPRD */
 595 {
 596         Stream          newstream = RMakeStream();
 597
 598         set_upstream(newstream, get_upstream(current));
 599         if (get_upstream(current))
 600                 set_downstream((Stream) (get_upstream(current)), (StreamPtr) newstream);
 601         set_upstream(current, (StreamPtr) newstream);
 602         set_downstream(newstream, (StreamPtr) current);
 603         set_pathptr(newstream, get_pathptr(current));
 604         set_cinfo(newstream, restrictinfo);
 605         set_clausetype(newstream, clausetype);
 606         return newstream;
 607 }
 608
 609 /*
 610  ** Given a Stream node, find the number of relids referenced in the pathnode
 611  ** associated with the stream node.  The number of relids gives a unique
 612  ** ordering on the joins in a stream, which we use to compare the height of
 613  ** join nodes.
 614  */
 615 static int
 616 xfunc_num_relids(Stream node)
 617 {
 618         if (!node || !IsA(get_pathptr(node), JoinPath))
 619                 return 0;
 620         else
 621                 return (length
 622                                 (get_relids(get_parent((JoinPath) get_pathptr(node)))));
 623 }
 624
 625 /*
 626  ** xfunc_get_downjoin
 627  **    Given a stream node, find the next lowest node which points to a
 628  ** join predicate or a scan node.
 629  */
 630 static StreamPtr
 631 xfunc_get_downjoin(Stream node)
 632 {
 633         Stream          temp;
 634
 635         if (!is_clause(node))           /* if this is a join */
 636                 node = (Stream) get_downstream(node);
 637         for (temp = node; temp && is_clause(temp);
 638                  temp = (Stream) get_downstream(temp))
 639                  /* empty body in for loop */ ;
 640
 641         return (StreamPtr) temp;
 642 }
 643
 644 /*
 645  ** xfunc_get_upjoin
 646  **   same as above, but upwards.
 647  */
 648 static StreamPtr
 649 xfunc_get_upjoin(Stream node)
 650 {
 651         Stream          temp;
 652
 653         if (!is_clause(node))           /* if this is a join */
 654                 node = (Stream) get_upstream(node);
 655         for (temp = node; temp && is_clause(temp);
 656                  temp = (Stream) get_upstream(temp))
 657                  /* empty body in for loop */ ;
 658
 659         return (StreamPtr) temp;
 660 }
 661
 662 /*
 663  ** xfunc_stream_qsort
 664  **   Given a stream, sort by group rank the elements in the stream from the
 665  ** node "bottom" up.  DESTRUCTIVELY MODIFIES STREAM!  Returns new root.
 666  */
 667 static Stream
 668 xfunc_stream_qsort(Stream root, Stream bottom)
 669 {
 670         int                     i;
 671         size_t          num;
 672         Stream     *nodearray,
 673                                 output;
 674         Stream          tmp;
 675
 676         /* find size of list */
 677         for (num = 0, tmp = root; tmp != bottom;
 678                  tmp = (Stream) get_downstream(tmp))
 679                 num++;
 680         if (num <= 1)
 681                 return root;
 682
 683         /* copy elements of the list into an array */
 684         nodearray = (Stream *) palloc(num * sizeof(Stream));
 685
 686         for (tmp = root, i = 0; tmp != bottom;
 687                  tmp = (Stream) get_downstream(tmp), i++)
 688                 nodearray[i] = tmp;
 689
 690         /* sort the array */
 691         qsort(nodearray, num, sizeof(LispValue), xfunc_stream_compare);
 692
 693         /* paste together the array elements */
 694         output = nodearray[num - 1];
 695         set_upstream(output, (StreamPtr) NULL);
 696         for (i = num - 2; i >= 0; i--)
 697         {
 698                 set_downstream(nodearray[i + 1], (StreamPtr) nodearray[i]);
 699                 set_upstream(nodearray[i], (StreamPtr) nodearray[i + 1]);
 700         }
 701         set_downstream(nodearray[0], (StreamPtr) bottom);
 702         if (bottom)
 703                 set_upstream(bottom, (StreamPtr) nodearray[0]);
 704
 705         Assert(xfunc_check_stream(output));
 706         return output;
 707 }
 708
 709 /*
 710  ** xfunc_stream_compare
 711  **    comparison function for xfunc_stream_qsort.
 712  ** Compare nodes by group rank.  If group ranks are equal, ensure that
 713  ** join nodes appear in same order as in plan tree.
 714  */
 715 static int
 716 xfunc_stream_compare(void *arg1, void *arg2)
 717 {
 718         Stream          stream1 = *(Stream *) arg1;
 719         Stream          stream2 = *(Stream *) arg2;
 720         Cost            rank1,
 721                                 rank2;
 722
 723         rank1 = get_grouprank(stream1);
 724         rank2 = get_grouprank(stream2);
 725
 726         if (rank1 > rank2)
 727                 return 1;
 728         else if (rank1 < rank2)
 729                 return -1;
 730         else
 731         {
 732                 if (is_clause(stream1) && is_clause(stream2))
 733                         return 0;                       /* doesn't matter what order if both are
 734                                                                  * restrictions */
 735                 else if (!is_clause(stream1) && !is_clause(stream2))
 736                 {
 737                         if (xfunc_num_relids(stream1) < xfunc_num_relids(stream2))
 738                                 return -1;
 739                         else
 740                                 return 1;
 741                 }
 742                 else if (is_clause(stream1) && !is_clause(stream2))
 743                 {
 744                         if (xfunc_num_relids(stream1) == xfunc_num_relids(stream2))
 745                                 /* stream1 is a restriction over stream2 */
 746                                 return 1;
 747                         else
 748                                 return -1;
 749                 }
 750                 else if (!is_clause(stream1) && is_clause(stream2))
 751                 {
 752                         /* stream2 is a restriction over stream1: never push down */
 753                         return -1;
 754                 }
 755         }
 756 }
 757
 758 /* ------------------  DEBUGGING ROUTINES ---------------------------- */
 759
 760 /*
 761  ** Make sure all pointers in stream make sense.  Make sure no joins are
 762  ** out of order.
 763  */
 764 static bool
 765 xfunc_check_stream(Stream node)
 766 {
 767         Stream          temp;
 768         int                     numrelids,
 769                                 tmp;
 770
 771         /* set numrelids higher than max */
 772         if (!is_clause(node))
 773                 numrelids = xfunc_num_relids(node) + 1;
 774         else if (xfunc_get_downjoin(node))
 775                 numrelids = xfunc_num_relids((Stream) xfunc_get_downjoin(node)) + 1;
 776         else
 777                 numrelids = 1;
 778
 779         for (temp = node; get_downstream(temp); temp = (Stream) get_downstream(temp))
 780         {
 781                 if ((Stream) get_upstream((Stream) get_downstream(temp)) != temp)
 782                 {
 783                         elog(ERROR, "bad pointers in stream");
 784                         return false;
 785                 }
 786                 if (!is_clause(temp))
 787                 {
 788                         if ((tmp = xfunc_num_relids(temp)) >= numrelids)
 789                         {
 790                                 elog(ERROR, "Joins got reordered!");
 791                                 return false;
 792                         }
 793                         numrelids = tmp;
 794                 }
 795         }
 796
 797         return true;
 798 }
 799
 800 /*
 801  ** xfunc_in_stream
 802  **   check if node is in stream
 803  */
 804 static bool
 805 xfunc_in_stream(Stream node, Stream stream)
 806 {
 807         Stream          temp;
 808
 809         for (temp = stream; temp; temp = (Stream) get_downstream(temp))
 810                 if (temp == node)
 811                         return 1;
 812         return 0;
 813 }