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

   1 /*-------------------------------------------------------------------------
   2  *
   3  * prepqual.c--
   4  *        Routines for preprocessing the parse tree qualification
   5  *
   6  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepqual.c,v 1.10 1998/09/01 03:23:43 momjian Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include <sys/types.h>
  15
  16 #include "postgres.h"
  17
  18 #include "nodes/pg_list.h"
  19 #include "nodes/makefuncs.h"
  20
  21 #include "optimizer/internal.h"
  22 #include "optimizer/clauses.h"
  23 #include "optimizer/prep.h"
  24
  25 #include "utils/lsyscache.h"
  26
  27 static Expr *pull_args(Expr *qual);
  28 static List *pull_ors(List *orlist);
  29 static List *pull_ands(List *andlist);
  30 static Expr *find_nots(Expr *qual);
  31 static Expr *push_nots(Expr *qual);
  32 static Expr *normalize(Expr *qual);
  33 static List *or_normalize(List *orlist);
  34 static List *distribute_args(List *item, List *args);
  35 static List *qualcleanup(Expr *qual);
  36 static List *remove_ands(Expr *qual);
  37 static List *remove_duplicates(List *list);
  38
  39 /*****************************************************************************
  40  *
  41  *              CNF CONVERSION ROUTINES
  42  *
  43  *              NOTES:
  44  *              The basic algorithms for normalizing the qualification are taken
  45  *              from ingres/source/qrymod/norml.c
  46  *
  47  *              Remember that the initial qualification may consist of ARBITRARY
  48  *              combinations of clauses.  In addition, before this routine is called,
  49  *              the qualification will contain explicit "AND"s.
  50  *
  51  *****************************************************************************/
  52
  53
  54 /*
  55  * cnfify--
  56  *        Convert a qualification to conjunctive normal form by applying
  57  *        successive normalizations.
  58  *
  59  * Returns the modified qualification with an extra level of nesting.
  60  *
  61  * If 'removeAndFlag' is true then it removes the explicit ANDs.
  62  *
  63  * NOTE: this routine is called by the planner (removeAndFlag = true)
  64  *              and from the rule manager (removeAndFlag = false).
  65  *
  66  */
  67 List *
  68 cnfify(Expr *qual, bool removeAndFlag)
  69 {
  70         Expr       *newqual = NULL;
  71
  72         if (qual != NULL)
  73         {
  74                 newqual = find_nots(pull_args(qual));
  75                 newqual = normalize(pull_args(newqual));
  76                 newqual = (Expr *) qualcleanup(pull_args(newqual));
  77                 newqual = pull_args(newqual);;
  78
  79                 if (removeAndFlag)
  80                 {
  81                         if (and_clause((Node *) newqual))
  82                                 newqual = (Expr *) remove_ands(newqual);
  83                         else
  84                                 newqual = (Expr *) remove_ands(make_andclause(lcons(newqual, NIL)));
  85                 }
  86         }
  87         else if (qual != NULL)
  88                 newqual = (Expr *) lcons(qual, NIL);
  89
  90         return (List *) (newqual);
  91 }
  92
  93 /*
  94  * pull-args--
  95  *        Given a qualification, eliminate nested 'and' and 'or' clauses.
  96  *
  97  * Returns the modified qualification.
  98  *
  99  */
 100 static Expr *
 101 pull_args(Expr *qual)
 102 {
 103         if (qual == NULL)
 104                 return NULL;
 105
 106         if (is_opclause((Node *) qual))
 107         {
 108                 return (make_clause(qual->opType, qual->oper,
 109                                                         lcons(pull_args((Expr *) get_leftop(qual)),
 110                                                          lcons(pull_args((Expr *) get_rightop(qual)),
 111                                                                    NIL))));
 112         }
 113         else if (and_clause((Node *) qual))
 114         {
 115                 List       *temp = NIL;
 116                 List       *t_list = NIL;
 117
 118                 foreach(temp, qual->args)
 119                         t_list = lappend(t_list, pull_args(lfirst(temp)));
 120                 return make_andclause(pull_ands(t_list));
 121         }
 122         else if (or_clause((Node *) qual))
 123         {
 124                 List       *temp = NIL;
 125                 List       *t_list = NIL;
 126
 127                 foreach(temp, qual->args)
 128                         t_list = lappend(t_list, pull_args(lfirst(temp)));
 129                 return make_orclause(pull_ors(t_list));
 130         }
 131         else if (not_clause((Node *) qual))
 132                 return make_notclause(pull_args(get_notclausearg(qual)));
 133         else
 134                 return qual;
 135 }
 136
 137 /*
 138  * pull-ors--
 139  *        Pull the arguments of an 'or' clause nested within another 'or'
 140  *        clause up into the argument list of the parent.
 141  *
 142  * Returns the modified list.
 143  */
 144 static List *
 145 pull_ors(List *orlist)
 146 {
 147         if (orlist == NIL)
 148                 return NIL;
 149
 150         if (or_clause(lfirst(orlist)))
 151         {
 152                 List       *args = ((Expr *) lfirst(orlist))->args;
 153
 154                 return (pull_ors(nconc(copyObject((Node *) args),
 155                                                            copyObject((Node *) lnext(orlist)))));
 156         }
 157         else
 158                 return lcons(lfirst(orlist), pull_ors(lnext(orlist)));
 159 }
 160
 161 /*
 162  * pull-ands--
 163  *        Pull the arguments of an 'and' clause nested within another 'and'
 164  *        clause up into the argument list of the parent.
 165  *
 166  * Returns the modified list.
 167  */
 168 static List *
 169 pull_ands(List *andlist)
 170 {
 171         if (andlist == NIL)
 172                 return NIL;
 173
 174         if (and_clause(lfirst(andlist)))
 175         {
 176                 List       *args = ((Expr *) lfirst(andlist))->args;
 177
 178                 return (pull_ands(nconc(copyObject((Node *) args),
 179                                                                 copyObject((Node *) lnext(andlist)))));
 180         }
 181         else
 182                 return lcons(lfirst(andlist), pull_ands(lnext(andlist)));
 183 }
 184
 185 /*
 186  * find-nots--
 187  *        Traverse the qualification, looking for 'not's to take care of.
 188  *        For 'not' clauses, remove the 'not' and push it down to the clauses'
 189  *        descendants.
 190  *        For all other clause types, simply recurse.
 191  *
 192  * Returns the modified qualification.
 193  *
 194  */
 195 static Expr *
 196 find_nots(Expr *qual)
 197 {
 198         if (qual == NULL)
 199                 return NULL;
 200
 201         if (is_opclause((Node *) qual))
 202         {
 203                 return (make_clause(qual->opType, qual->oper,
 204                                                         lcons(find_nots((Expr *) get_leftop(qual)),
 205                                                          lcons(find_nots((Expr *) get_rightop(qual)),
 206                                                                    NIL))));
 207         }
 208         else if (and_clause((Node *) qual))
 209         {
 210                 List       *temp = NIL;
 211                 List       *t_list = NIL;
 212
 213                 foreach(temp, qual->args)
 214                         t_list = lappend(t_list, find_nots(lfirst(temp)));
 215
 216                 return make_andclause(t_list);
 217         }
 218         else if (or_clause((Node *) qual))
 219         {
 220                 List       *temp = NIL;
 221                 List       *t_list = NIL;
 222
 223                 foreach(temp, qual->args)
 224                         t_list = lappend(t_list, find_nots(lfirst(temp)));
 225                 return make_orclause(t_list);
 226         }
 227         else if (not_clause((Node *) qual))
 228                 return push_nots(get_notclausearg(qual));
 229         else
 230                 return qual;
 231 }
 232
 233 /*
 234  * push-nots--
 235  *        Negate the descendants of a 'not' clause.
 236  *
 237  * Returns the modified qualification.
 238  *
 239  */
 240 static Expr *
 241 push_nots(Expr *qual)
 242 {
 243         if (qual == NULL)
 244                 return NULL;
 245
 246         /*
 247          * Negate an operator clause if possible: ("NOT" (< A B)) => (> A B)
 248          * Otherwise, retain the clause as it is (the 'not' can't be pushed
 249          * down any farther).
 250          */
 251         if (is_opclause((Node *) qual))
 252         {
 253                 Oper       *oper = (Oper *) ((Expr *) qual)->oper;
 254                 Oid                     negator = get_negator(oper->opno);
 255
 256                 if (negator)
 257                 {
 258                         Oper       *op = (Oper *) makeOper(negator,
 259                                                                                            InvalidOid,
 260                                                                                            oper->opresulttype,
 261                                                                                            0, NULL);
 262
 263                         op->op_fcache = (FunctionCache *) NULL;
 264                         return
 265                                 (make_opclause(op, get_leftop(qual), get_rightop(qual)));
 266                 }
 267                 else
 268                         return make_notclause(qual);
 269         }
 270         else if (and_clause((Node *) qual))
 271         {
 272
 273                 /*
 274                  * Apply DeMorgan's Laws: ("NOT" ("AND" A B)) => ("OR" ("NOT" A)
 275                  * ("NOT" B)) ("NOT" ("OR" A B)) => ("AND" ("NOT" A) ("NOT" B))
 276                  * i.e., continue negating down through the clause's descendants.
 277                  */
 278                 List       *temp = NIL;
 279                 List       *t_list = NIL;
 280
 281                 foreach(temp, qual->args)
 282                         t_list = lappend(t_list, push_nots(lfirst(temp)));
 283                 return make_orclause(t_list);
 284         }
 285         else if (or_clause((Node *) qual))
 286         {
 287                 List       *temp = NIL;
 288                 List       *t_list = NIL;
 289
 290                 foreach(temp, qual->args)
 291                         t_list = lappend(t_list, push_nots(lfirst(temp)));
 292                 return make_andclause(t_list);
 293         }
 294         else if (not_clause((Node *) qual))
 295
 296                 /*
 297                  * Another 'not' cancels this 'not', so eliminate the 'not' and
 298                  * stop negating this branch.
 299                  */
 300                 return find_nots(get_notclausearg(qual));
 301         else
 302
 303                 /*
 304                  * We don't know how to negate anything else, place a 'not' at
 305                  * this level.
 306                  */
 307                 return make_notclause(qual);
 308 }
 309
 310 /*
 311  * normalize--
 312  *        Given a qualification tree with the 'not's pushed down, convert it
 313  *        to a tree in CNF by repeatedly applying the rule:
 314  *                              ("OR" A ("AND" B C))  => ("AND" ("OR" A B) ("OR" A C))
 315  *        bottom-up.
 316  *        Note that 'or' clauses will always be turned into 'and' clauses.
 317  *
 318  * Returns the modified qualification.
 319  *
 320  */
 321 static Expr *
 322 normalize(Expr *qual)
 323 {
 324         if (qual == NULL)
 325                 return NULL;
 326
 327         if (is_opclause((Node *) qual))
 328         {
 329                 Expr       *expr = (Expr *) qual;
 330
 331                 return (make_clause(expr->opType, expr->oper,
 332                                                         lcons(normalize((Expr *) get_leftop(qual)),
 333                                                          lcons(normalize((Expr *) get_rightop(qual)),
 334                                                                    NIL))));
 335         }
 336         else if (and_clause((Node *) qual))
 337         {
 338                 List       *temp = NIL;
 339                 List       *t_list = NIL;
 340
 341                 foreach(temp, qual->args)
 342                         t_list = lappend(t_list, normalize(lfirst(temp)));
 343                 return make_andclause(t_list);
 344         }
 345         else if (or_clause((Node *) qual))
 346         {
 347                 /* XXX - let form, maybe incorrect */
 348                 List       *orlist = NIL;
 349                 List       *temp = NIL;
 350                 bool            has_andclause = FALSE;
 351
 352                 foreach(temp, qual->args)
 353                         orlist = lappend(orlist, normalize(lfirst(temp)));
 354                 foreach(temp, orlist)
 355                 {
 356                         if (and_clause(lfirst(temp)))
 357                         {
 358                                 has_andclause = TRUE;
 359                                 break;
 360                         }
 361                 }
 362                 if (has_andclause == TRUE)
 363                         return make_andclause(or_normalize(orlist));
 364                 else
 365                         return make_orclause(orlist);
 366
 367         }
 368         else if (not_clause((Node *) qual))
 369                 return make_notclause(normalize(get_notclausearg(qual)));
 370         else
 371                 return qual;
 372 }
 373
 374 /*
 375  * or-normalize--
 376  *        Given a list of exprs which are 'or'ed together, distribute any
 377  *        'and' clauses.
 378  *
 379  * Returns the modified list.
 380  *
 381  */
 382 static List *
 383 or_normalize(List *orlist)
 384 {
 385         List       *distributable = NIL;
 386         List       *new_orlist = NIL;
 387         List       *temp = NIL;
 388
 389         if (orlist == NIL)
 390                 return NIL;
 391
 392         foreach(temp, orlist)
 393         {
 394                 if (and_clause(lfirst(temp)))
 395                         distributable = lfirst(temp);
 396         }
 397         if (distributable)
 398                 new_orlist = LispRemove(distributable, orlist);
 399
 400         if (new_orlist)
 401         {
 402                 return
 403                         (or_normalize(lcons(distribute_args(lfirst(new_orlist),
 404                                                                                  ((Expr *) distributable)->args),
 405                                                                 lnext(new_orlist))));
 406         }
 407         else
 408                 return orlist;
 409 }
 410
 411 /*
 412  * distribute-args--
 413  *        Create new 'or' clauses by or'ing 'item' with each element of 'args'.
 414  *        E.g.: (distribute-args A ("AND" B C)) => ("AND" ("OR" A B) ("OR" A C))
 415  *
 416  * Returns an 'and' clause.
 417  *
 418  */
 419 static List *
 420 distribute_args(List *item, List *args)
 421 {
 422         List       *or_list = NIL;
 423         List       *n_list = NIL;
 424         List       *temp = NIL;
 425         List       *t_list = NIL;
 426
 427         if (args == NULL)
 428                 return item;
 429
 430         foreach(temp, args)
 431         {
 432                 n_list = or_normalize(pull_ors(lcons(item,
 433                                                                                          lcons(lfirst(temp), NIL))));
 434                 or_list = (List *) make_orclause(n_list);
 435                 t_list = lappend(t_list, or_list);
 436         }
 437         return (List *) make_andclause(t_list);
 438 }
 439
 440 /*
 441  * qualcleanup--
 442  *        Fix up a qualification by removing duplicate entries (left over from
 443  *        normalization), and by removing 'and' and 'or' clauses which have only
 444  *        one valid expr (e.g., ("AND" A) => A).
 445  *
 446  * Returns the modified qualfication.
 447  *
 448  */
 449 static List *
 450 qualcleanup(Expr *qual)
 451 {
 452         if (qual == NULL)
 453                 return NIL;
 454
 455         if (is_opclause((Node *) qual))
 456         {
 457                 return ((List *) make_clause(qual->opType, qual->oper,
 458                                                         lcons(qualcleanup((Expr *) get_leftop(qual)),
 459                                                    lcons(qualcleanup((Expr *) get_rightop(qual)),
 460                                                                  NIL))));
 461         }
 462         else if (and_clause((Node *) qual))
 463         {
 464                 List       *temp = NIL;
 465                 List       *t_list = NIL;
 466                 List       *new_and_args = NIL;
 467
 468                 foreach(temp, qual->args)
 469                         t_list = lappend(t_list, qualcleanup(lfirst(temp)));
 470
 471                 new_and_args = remove_duplicates(t_list);
 472
 473                 if (length(new_and_args) > 1)
 474                         return (List *) make_andclause(new_and_args);
 475                 else
 476                         return lfirst(new_and_args);
 477         }
 478         else if (or_clause((Node *) qual))
 479         {
 480                 List       *temp = NIL;
 481                 List       *t_list = NIL;
 482                 List       *new_or_args = NIL;
 483
 484                 foreach(temp, qual->args)
 485                         t_list = lappend(t_list, qualcleanup(lfirst(temp)));
 486
 487                 new_or_args = remove_duplicates(t_list);
 488
 489
 490                 if (length(new_or_args) > 1)
 491                         return (List *) make_orclause(new_or_args);
 492                 else
 493                         return lfirst(new_or_args);
 494         }
 495         else if (not_clause((Node *) qual))
 496                 return (List *) make_notclause((Expr *) qualcleanup((Expr *) get_notclausearg(qual)));
 497
 498         else
 499                 return (List *) qual;
 500 }
 501
 502 /*
 503  * remove-ands--
 504  *        Remove the explicit "AND"s from the qualification:
 505  *                              ("AND" A B) => (A B)
 506  *
 507  * RETURNS : qual
 508  * MODIFIES: qual
 509  */
 510 static List *
 511 remove_ands(Expr *qual)
 512 {
 513         List       *t_list = NIL;
 514
 515         if (qual == NULL)
 516                 return NIL;
 517         if (is_opclause((Node *) qual))
 518         {
 519                 return ((List *) make_clause(qual->opType, qual->oper,
 520                                                         lcons(remove_ands((Expr *) get_leftop(qual)),
 521                                                    lcons(remove_ands((Expr *) get_rightop(qual)),
 522                                                                  NIL))));
 523         }
 524         else if (and_clause((Node *) qual))
 525         {
 526                 List       *temp = NIL;
 527
 528                 foreach(temp, qual->args)
 529                         t_list = lappend(t_list, remove_ands(lfirst(temp)));
 530                 return t_list;
 531         }
 532         else if (or_clause((Node *) qual))
 533         {
 534                 List       *temp = NIL;
 535
 536                 foreach(temp, qual->args)
 537                         t_list = lappend(t_list, remove_ands(lfirst(temp)));
 538                 return (List *) make_orclause((List *) t_list);
 539         }
 540         else if (not_clause((Node *) qual))
 541                 return (List *) make_notclause((Expr *) remove_ands((Expr *) get_notclausearg(qual)));
 542         else
 543                 return (List *) qual;
 544 }
 545
 546 /*****************************************************************************
 547  *
 548  *
 549  *
 550  *****************************************************************************/
 551
 552 static List *
 553 remove_duplicates(List *list)
 554 {
 555         List       *i;
 556         List       *j;
 557         List       *result = NIL;
 558         bool            there_exists_duplicate = false;
 559
 560         if (length(list) == 1)
 561                 return list;
 562
 563         foreach(i, list)
 564         {
 565                 if (i != NIL)
 566                 {
 567                         foreach(j, lnext(i))
 568                         {
 569                                 if (equal(lfirst(i), lfirst(j)))
 570                                         there_exists_duplicate = true;
 571                         }
 572                         if (!there_exists_duplicate)
 573                                 result = lappend(result, lfirst(i));
 574
 575                         there_exists_duplicate = false;
 576                 }
 577         }
 578         return result;
 579 }