granicus.if.org Git - postgresql/blob - src/backend/optimizer/prep/prepqual.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * prepqual.c
   4  *        Routines for preprocessing qualification expressions
   5  *
   6  * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $PostgreSQL: pgsql/src/backend/optimizer/prep/prepqual.c,v 1.41 2003/12/30 21:49:19 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #include "nodes/makefuncs.h"
  19 #include "optimizer/clauses.h"
  20 #include "optimizer/prep.h"
  21 #include "utils/lsyscache.h"
  22
  23
  24 static Node *flatten_andors_mutator(Node *node, void *context);
  25 static void flatten_andors_and_walker(FastList *out_list, List *andlist);
  26 static void flatten_andors_or_walker(FastList *out_list, List *orlist);
  27 static List *pull_ands(List *andlist);
  28 static void pull_ands_walker(FastList *out_list, List *andlist);
  29 static List *pull_ors(List *orlist);
  30 static void pull_ors_walker(FastList *out_list, List *orlist);
  31 static Expr *find_nots(Expr *qual);
  32 static Expr *push_nots(Expr *qual);
  33 static Expr *find_duplicate_ors(Expr *qual);
  34 static Expr *process_duplicate_ors(List *orlist);
  35
  36
  37 /*
  38  * canonicalize_qual
  39  *        Convert a qualification expression to the most useful form.
  40  *
  41  * The name of this routine is a holdover from a time when it would try to
  42  * force the expression into canonical AND-of-ORs or OR-of-ANDs form.
  43  * Eventually, we recognized that that had more theoretical purity than
  44  * actual usefulness, and so now the transformation doesn't involve any
  45  * notion of reaching a canonical form.
  46  *
  47  * Returns the modified qualification.
  48  */
  49 Expr *
  50 canonicalize_qual(Expr *qual)
  51 {
  52         Expr       *newqual;
  53
  54         /* Quick exit for empty qual */
  55         if (qual == NULL)
  56                 return NULL;
  57
  58         /*
  59          * Flatten AND and OR groups throughout the expression tree.
  60          */
  61         newqual = (Expr *) flatten_andors((Node *) qual);
  62
  63         /*
  64          * Push down NOTs.      We do this only in the top-level boolean
  65          * expression, without examining arguments of operators/functions.
  66          * The main reason for doing this is to expose as much top-level AND/OR
  67          * structure as we can, so there's no point in descending further.
  68          */
  69         newqual = find_nots(newqual);
  70
  71         /*
  72          * Pull up redundant subclauses in OR-of-AND trees.  Again, we do this
  73          * only within the top-level AND/OR structure.
  74          */
  75         newqual = find_duplicate_ors(newqual);
  76
  77         return newqual;
  78 }
  79
  80
  81 /*--------------------
  82  * The parser regards AND and OR as purely binary operators, so a qual like
  83  *              (A = 1) OR (A = 2) OR (A = 3) ...
  84  * will produce a nested parsetree
  85  *              (OR (A = 1) (OR (A = 2) (OR (A = 3) ...)))
  86  * In reality, the optimizer and executor regard AND and OR as n-argument
  87  * operators, so this tree can be flattened to
  88  *              (OR (A = 1) (A = 2) (A = 3) ...)
  89  * which is the responsibility of the routines below.
  90  *
  91  * flatten_andors() does the basic transformation with no initial assumptions.
  92  * pull_ands() and pull_ors() are used to maintain flatness of the AND/OR
  93  * tree after local transformations that might introduce nested AND/ORs.
  94  *--------------------
  95  */
  96
  97 /*
  98  * flatten_andors
  99  *        Given an expression tree, simplify nested AND/OR clauses into flat
 100  *        AND/OR clauses with more arguments.  The entire tree is processed.
 101  *
 102  * Returns the rebuilt expr (note original structure is not touched).
 103  *
 104  * This is exported so that other modules can perform the part of
 105  * canonicalize_qual processing that applies to entire trees, rather
 106  * than just the top-level boolean expressions.
 107  */
 108 Node *
 109 flatten_andors(Node *node)
 110 {
 111         return flatten_andors_mutator(node, NULL);
 112 }
 113
 114 static Node *
 115 flatten_andors_mutator(Node *node, void *context)
 116 {
 117         if (node == NULL)
 118                 return NULL;
 119         if (IsA(node, BoolExpr))
 120         {
 121                 BoolExpr   *bexpr = (BoolExpr *) node;
 122
 123                 if (bexpr->boolop == AND_EXPR)
 124                 {
 125                         FastList        out_list;
 126
 127                         FastListInit(&out_list);
 128                         flatten_andors_and_walker(&out_list, bexpr->args);
 129                         return (Node *) make_andclause(FastListValue(&out_list));
 130                 }
 131                 if (bexpr->boolop == OR_EXPR)
 132                 {
 133                         FastList        out_list;
 134
 135                         FastListInit(&out_list);
 136                         flatten_andors_or_walker(&out_list, bexpr->args);
 137                         return (Node *) make_orclause(FastListValue(&out_list));
 138                 }
 139                 /* else it's a NOT clause, fall through */
 140         }
 141         return expression_tree_mutator(node, flatten_andors_mutator, context);
 142 }
 143
 144 static void
 145 flatten_andors_and_walker(FastList *out_list, List *andlist)
 146 {
 147         List       *arg;
 148
 149         foreach(arg, andlist)
 150         {
 151                 Node       *subexpr = (Node *) lfirst(arg);
 152
 153                 if (and_clause(subexpr))
 154                         flatten_andors_and_walker(out_list, ((BoolExpr *) subexpr)->args);
 155                 else
 156                         FastAppend(out_list, flatten_andors(subexpr));
 157         }
 158 }
 159
 160 static void
 161 flatten_andors_or_walker(FastList *out_list, List *orlist)
 162 {
 163         List       *arg;
 164
 165         foreach(arg, orlist)
 166         {
 167                 Node       *subexpr = (Node *) lfirst(arg);
 168
 169                 if (or_clause(subexpr))
 170                         flatten_andors_or_walker(out_list, ((BoolExpr *) subexpr)->args);
 171                 else
 172                         FastAppend(out_list, flatten_andors(subexpr));
 173         }
 174 }
 175
 176 /*
 177  * pull_ands
 178  *        Recursively flatten nested AND clauses into a single and-clause list.
 179  *
 180  * Input is the arglist of an AND clause.
 181  * Returns the rebuilt arglist (note original list structure is not touched).
 182  */
 183 static List *
 184 pull_ands(List *andlist)
 185 {
 186         FastList        out_list;
 187
 188         FastListInit(&out_list);
 189         pull_ands_walker(&out_list, andlist);
 190         return FastListValue(&out_list);
 191 }
 192
 193 static void
 194 pull_ands_walker(FastList *out_list, List *andlist)
 195 {
 196         List       *arg;
 197
 198         foreach(arg, andlist)
 199         {
 200                 Node       *subexpr = (Node *) lfirst(arg);
 201
 202                 if (and_clause(subexpr))
 203                         pull_ands_walker(out_list, ((BoolExpr *) subexpr)->args);
 204                 else
 205                         FastAppend(out_list, subexpr);
 206         }
 207 }
 208
 209 /*
 210  * pull_ors
 211  *        Recursively flatten nested OR clauses into a single or-clause list.
 212  *
 213  * Input is the arglist of an OR clause.
 214  * Returns the rebuilt arglist (note original list structure is not touched).
 215  */
 216 static List *
 217 pull_ors(List *orlist)
 218 {
 219         FastList        out_list;
 220
 221         FastListInit(&out_list);
 222         pull_ors_walker(&out_list, orlist);
 223         return FastListValue(&out_list);
 224 }
 225
 226 static void
 227 pull_ors_walker(FastList *out_list, List *orlist)
 228 {
 229         List       *arg;
 230
 231         foreach(arg, orlist)
 232         {
 233                 Node       *subexpr = (Node *) lfirst(arg);
 234
 235                 if (or_clause(subexpr))
 236                         pull_ors_walker(out_list, ((BoolExpr *) subexpr)->args);
 237                 else
 238                         FastAppend(out_list, subexpr);
 239         }
 240 }
 241
 242
 243 /*
 244  * find_nots
 245  *        Traverse the qualification, looking for NOTs to take care of.
 246  *        For NOT clauses, apply push_nots() to try to push down the NOT.
 247  *        For AND and OR clause types, simply recurse.  Otherwise stop
 248  *        recursing (we do not worry about structure below the top AND/OR tree).
 249  *
 250  * Returns the modified qualification.  AND/OR flatness is preserved.
 251  */
 252 static Expr *
 253 find_nots(Expr *qual)
 254 {
 255         if (qual == NULL)
 256                 return NULL;
 257
 258         if (and_clause((Node *) qual))
 259         {
 260                 FastList        t_list;
 261                 List       *temp;
 262
 263                 FastListInit(&t_list);
 264                 foreach(temp, ((BoolExpr *) qual)->args)
 265                         FastAppend(&t_list, find_nots(lfirst(temp)));
 266                 return make_andclause(pull_ands(FastListValue(&t_list)));
 267         }
 268         else if (or_clause((Node *) qual))
 269         {
 270                 FastList        t_list;
 271                 List       *temp;
 272
 273                 FastListInit(&t_list);
 274                 foreach(temp, ((BoolExpr *) qual)->args)
 275                         FastAppend(&t_list, find_nots(lfirst(temp)));
 276                 return make_orclause(pull_ors(FastListValue(&t_list)));
 277         }
 278         else if (not_clause((Node *) qual))
 279                 return push_nots(get_notclausearg(qual));
 280         else
 281                 return qual;
 282 }
 283
 284 /*
 285  * push_nots
 286  *        Push down a NOT as far as possible.
 287  *
 288  * Input is an expression to be negated (e.g., the argument of a NOT clause).
 289  * Returns a new qual equivalent to the negation of the given qual.
 290  */
 291 static Expr *
 292 push_nots(Expr *qual)
 293 {
 294         if (qual == NULL)
 295                 return make_notclause(qual);    /* XXX is this right?  Or
 296                                                                                  * possible? */
 297
 298         /*
 299          * Negate an operator clause if possible: (NOT (< A B)) => (> A B)
 300          * Otherwise, retain the clause as it is (the NOT can't be pushed
 301          * down any farther).
 302          */
 303         if (is_opclause(qual))
 304         {
 305                 OpExpr     *opexpr = (OpExpr *) qual;
 306                 Oid                     negator = get_negator(opexpr->opno);
 307
 308                 if (negator)
 309                         return make_opclause(negator,
 310                                                                  opexpr->opresulttype,
 311                                                                  opexpr->opretset,
 312                                                                  (Expr *) get_leftop(qual),
 313                                                                  (Expr *) get_rightop(qual));
 314                 else
 315                         return make_notclause(qual);
 316         }
 317         else if (and_clause((Node *) qual))
 318         {
 319                 /*--------------------
 320                  * Apply DeMorgan's Laws:
 321                  *              (NOT (AND A B)) => (OR (NOT A) (NOT B))
 322                  *              (NOT (OR A B))  => (AND (NOT A) (NOT B))
 323                  * i.e., swap AND for OR and negate all the subclauses.
 324                  *--------------------
 325                  */
 326                 FastList        t_list;
 327                 List       *temp;
 328
 329                 FastListInit(&t_list);
 330                 foreach(temp, ((BoolExpr *) qual)->args)
 331                         FastAppend(&t_list, push_nots(lfirst(temp)));
 332                 return make_orclause(pull_ors(FastListValue(&t_list)));
 333         }
 334         else if (or_clause((Node *) qual))
 335         {
 336                 FastList        t_list;
 337                 List       *temp;
 338
 339                 FastListInit(&t_list);
 340                 foreach(temp, ((BoolExpr *) qual)->args)
 341                         FastAppend(&t_list, push_nots(lfirst(temp)));
 342                 return make_andclause(pull_ands(FastListValue(&t_list)));
 343         }
 344         else if (not_clause((Node *) qual))
 345         {
 346                 /*
 347                  * Another NOT cancels this NOT, so eliminate the NOT and
 348                  * stop negating this branch.
 349                  */
 350                 return get_notclausearg(qual);
 351         }
 352         else
 353         {
 354                 /*
 355                  * We don't know how to negate anything else, place a NOT at
 356                  * this level.
 357                  */
 358                 return make_notclause(qual);
 359         }
 360 }
 361
 362
 363 /*--------------------
 364  * The following code attempts to apply the inverse OR distributive law:
 365  *              ((A AND B) OR (A AND C))  =>  (A AND (B OR C))
 366  * That is, locate OR clauses in which every subclause contains an
 367  * identical term, and pull out the duplicated terms.
 368  *
 369  * This may seem like a fairly useless activity, but it turns out to be
 370  * applicable to many machine-generated queries, and there are also queries
 371  * in some of the TPC benchmarks that need it.  This was in fact almost the
 372  * sole useful side-effect of the old prepqual code that tried to force
 373  * the query into canonical AND-of-ORs form: the canonical equivalent of
 374  *              ((A AND B) OR (A AND C))
 375  * is
 376  *              ((A OR A) AND (A OR C) AND (B OR A) AND (B OR C))
 377  * which the code was able to simplify to
 378  *              (A AND (A OR C) AND (B OR A) AND (B OR C))
 379  * thus successfully extracting the common condition A --- but at the cost
 380  * of cluttering the qual with many redundant clauses.
 381  *--------------------
 382  */
 383
 384 /*
 385  * find_duplicate_ors
 386  *        Given a qualification tree with the NOTs pushed down, search for
 387  *        OR clauses to which the inverse OR distributive law might apply.
 388  *        Only the top-level AND/OR structure is searched.
 389  *
 390  * Returns the modified qualification.  AND/OR flatness is preserved.
 391  */
 392 static Expr *
 393 find_duplicate_ors(Expr *qual)
 394 {
 395         if (qual == NULL)
 396                 return NULL;
 397
 398         if (or_clause((Node *) qual))
 399         {
 400                 List       *orlist = NIL;
 401                 List       *temp;
 402
 403                 /* Recurse */
 404                 foreach(temp, ((BoolExpr *) qual)->args)
 405                         orlist = lappend(orlist, find_duplicate_ors(lfirst(temp)));
 406                 /*
 407                  * Don't need pull_ors() since this routine will never introduce
 408                  * an OR where there wasn't one before.
 409                  */
 410                 return process_duplicate_ors(orlist);
 411         }
 412         else if (and_clause((Node *) qual))
 413         {
 414                 List       *andlist = NIL;
 415                 List       *temp;
 416
 417                 /* Recurse */
 418                 foreach(temp, ((BoolExpr *) qual)->args)
 419                         andlist = lappend(andlist, find_duplicate_ors(lfirst(temp)));
 420                 /* Flatten any ANDs introduced just below here */
 421                 andlist = pull_ands(andlist);
 422                 /* The AND list can't get shorter, so result is always an AND */
 423                 return make_andclause(andlist);
 424         }
 425         else
 426                 return qual;
 427 }
 428
 429 /*
 430  * process_duplicate_ors
 431  *        Given a list of exprs which are ORed together, try to apply
 432  *        the inverse OR distributive law.
 433  *
 434  * Returns the resulting expression (could be an AND clause, an OR
 435  * clause, or maybe even a single subexpression).
 436  */
 437 static Expr *
 438 process_duplicate_ors(List *orlist)
 439 {
 440         List       *reference = NIL;
 441         int                     num_subclauses = 0;
 442         List       *winners;
 443         List       *neworlist;
 444         List       *temp;
 445         List       *temp2;
 446
 447         if (orlist == NIL)
 448                 return NULL;                    /* probably can't happen */
 449         if (lnext(orlist) == NIL)
 450                 return lfirst(orlist);  /* single-expression OR (can this happen?) */
 451
 452         /*
 453          * Choose the shortest AND clause as the reference list --- obviously,
 454          * any subclause not in this clause isn't in all the clauses.
 455          * If we find a clause that's not an AND, we can treat it as a
 456          * one-element AND clause, which necessarily wins as shortest.
 457          */
 458         foreach(temp, orlist)
 459         {
 460                 Expr       *clause = lfirst(temp);
 461
 462                 if (and_clause((Node *) clause))
 463                 {
 464                         List       *subclauses = ((BoolExpr *) clause)->args;
 465                         int                     nclauses = length(subclauses);
 466
 467                         if (reference == NIL || nclauses < num_subclauses)
 468                         {
 469                                 reference = subclauses;
 470                                 num_subclauses = nclauses;
 471                         }
 472                 }
 473                 else
 474                 {
 475                         reference = makeList1(clause);
 476                         break;
 477                 }
 478         }
 479
 480         /*
 481          * Just in case, eliminate any duplicates in the reference list.
 482          */
 483         reference = set_union(NIL, reference);
 484
 485         /*
 486          * Check each element of the reference list to see if it's in all the
 487          * OR clauses.  Build a new list of winning clauses.
 488          */
 489         winners = NIL;
 490         foreach(temp, reference)
 491         {
 492                 Expr       *refclause = lfirst(temp);
 493                 bool            win = true;
 494
 495                 foreach(temp2, orlist)
 496                 {
 497                         Expr       *clause = lfirst(temp2);
 498
 499                         if (and_clause((Node *) clause))
 500                         {
 501                                 if (!member(refclause, ((BoolExpr *) clause)->args))
 502                                 {
 503                                         win = false;
 504                                         break;
 505                                 }
 506                         }
 507                         else
 508                         {
 509                                 if (!equal(refclause, clause))
 510                                 {
 511                                         win = false;
 512                                         break;
 513                                 }
 514                         }
 515                 }
 516
 517                 if (win)
 518                         winners = lappend(winners, refclause);
 519         }
 520
 521         /*
 522          * If no winners, we can't transform the OR
 523          */
 524         if (winners == NIL)
 525                 return make_orclause(orlist);
 526
 527         /*
 528          * Generate new OR list consisting of the remaining sub-clauses.
 529          *
 530          * If any clause degenerates to empty, then we have a situation like
 531          * (A AND B) OR (A), which can be reduced to just A --- that is, the
 532          * additional conditions in other arms of the OR are irrelevant.
 533          *
 534          * Note that because we use set_difference, any multiple occurrences of
 535          * a winning clause in an AND sub-clause will be removed automatically.
 536          */
 537         neworlist = NIL;
 538         foreach(temp, orlist)
 539         {
 540                 Expr       *clause = lfirst(temp);
 541
 542                 if (and_clause((Node *) clause))
 543                 {
 544                         List       *subclauses = ((BoolExpr *) clause)->args;
 545
 546                         subclauses = set_difference(subclauses, winners);
 547                         if (subclauses != NIL)
 548                         {
 549                                 if (lnext(subclauses) == NIL)
 550                                         neworlist = lappend(neworlist, lfirst(subclauses));
 551                                 else
 552                                         neworlist = lappend(neworlist, make_andclause(subclauses));
 553                         }
 554                         else
 555                         {
 556                                 neworlist = NIL;                /* degenerate case, see above */
 557                                 break;
 558                         }
 559                 }
 560                 else
 561                 {
 562                         if (!member(clause, winners))
 563                                 neworlist = lappend(neworlist, clause);
 564                         else
 565                         {
 566                                 neworlist = NIL;                /* degenerate case, see above */
 567                                 break;
 568                         }
 569                 }
 570         }
 571
 572         /*
 573          * Append reduced OR to the winners list, if it's not degenerate, handling
 574          * the special case of one element correctly (can that really happen?).
 575          * Also be careful to maintain AND/OR flatness in case we pulled up a
 576          * sub-sub-OR-clause.
 577          */
 578         if (neworlist != NIL)
 579         {
 580                 if (lnext(neworlist) == NIL)
 581                         winners = lappend(winners, lfirst(neworlist));
 582                 else
 583                         winners = lappend(winners, make_orclause(pull_ors(neworlist)));
 584         }
 585
 586         /*
 587          * And return the constructed AND clause, again being wary of a single
 588          * element and AND/OR flatness.
 589          */
 590         if (lnext(winners) == NIL)
 591                 return (Expr *) lfirst(winners);
 592         else
 593                 return make_andclause(pull_ands(winners));
 594 }