src/backend/optimizer/plan/subselect.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * subselect.c
   4  *
   5  *-------------------------------------------------------------------------
   6  */
   7 #include "postgres.h"
   8
   9 #include "catalog/pg_type.h"
  10
  11 #include "nodes/pg_list.h"
  12 #include "nodes/plannodes.h"
  13 #include "nodes/parsenodes.h"
  14 #include "nodes/relation.h"
  15 #include "nodes/makefuncs.h"
  16 #include "nodes/nodeFuncs.h"
  17
  18 #include "optimizer/subselect.h"
  19 #include "optimizer/planner.h"
  20 #include "optimizer/planmain.h"
  21 #include "optimizer/internal.h"
  22 #include "optimizer/paths.h"
  23 #include "optimizer/clauses.h"
  24 #include "optimizer/keys.h"
  25 #include "optimizer/tlist.h"
  26 #include "optimizer/var.h"
  27 #include "optimizer/cost.h"
  28
  29 int                     PlannerQueryLevel;      /* level of current query */
  30 List       *PlannerVarParam;    /* correlation Vars to Param mapper */
  31 List       *PlannerParamVar;    /* to get Var from Param->paramid */
  32 List       *PlannerInitPlan;    /* init subplans for current query */
  33 int                     PlannerPlanId;
  34
  35
  36 static int
  37 _new_param(Var *var, int varlevel)
  38 {
  39         List       *last;
  40         int                     i = 0;
  41
  42         if (PlannerParamVar == NULL)
  43                 last = PlannerParamVar = makeNode(List);
  44         else
  45         {
  46                 for (last = PlannerParamVar;;)
  47                 {
  48                         i++;
  49                         if (lnext(last) == NULL)
  50                                 break;
  51                         last = lnext(last);
  52                 }
  53                 lnext(last) = makeNode(List);
  54                 last = lnext(last);
  55         }
  56
  57         lnext(last) = NULL;
  58         lfirst(last) = makeVar(var->varno, var->varattno, var->vartype,
  59                                 var->vartypmod, varlevel, var->varnoold, var->varoattno);
  60
  61         return i;
  62 }
  63
  64 static Param *
  65 _replace_var(Var *var)
  66 {
  67         List      **rt = (List **) nth(var->varlevelsup, PlannerVarParam);
  68         List       *vpe = rt[var->varno - 1];
  69         Param      *retval;
  70         int                     i;
  71
  72         if (vpe == NULL)
  73         {
  74                 vpe = rt[var->varno - 1] = makeNode(List);
  75                 lfirsti(vpe) = -1;
  76                 lnext(vpe) = NULL;
  77         }
  78
  79         for (i = ObjectIdAttributeNumber;; i++)
  80         {
  81                 if (i == var->varattno)
  82                         break;
  83                 if (lnext(vpe) == NULL)
  84                 {
  85                         lnext(vpe) = makeNode(List);
  86                         vpe = lnext(vpe);
  87                         lfirsti(vpe) = -1;
  88                         lnext(vpe) = NULL;
  89                 }
  90                 else
  91                         vpe = lnext(vpe);
  92         }
  93
  94         if ((i = lfirsti(vpe)) < 0) /* parameter is not assigned */
  95                 i = _new_param(var, PlannerQueryLevel - var->varlevelsup);
  96
  97         retval = makeNode(Param);
  98         retval->paramkind = PARAM_EXEC;
  99         retval->paramid = (AttrNumber) i;
 100         retval->paramtype = var->vartype;
 101
 102         return retval;
 103 }
 104
 105 static Node *
 106 _make_subplan(SubLink *slink)
 107 {
 108         SubPlan    *node = makeNode(SubPlan);
 109         Plan       *plan;
 110         List       *lst;
 111         Node       *result;
 112         List       *saved_ip = PlannerInitPlan;
 113
 114         PlannerInitPlan = NULL;
 115
 116         PlannerQueryLevel++;            /* we becomes child */
 117
 118         node->plan = plan = union_planner((Query *) slink->subselect);
 119
 120         /*
 121          * Assign subPlan, extParam and locParam to plan nodes. At the moment,
 122          * SS_finalize_plan doesn't handle initPlan-s and so we assigne them
 123          * to the topmost plan node and take care about its extParam too.
 124          */
 125         (void) SS_finalize_plan(plan);
 126         plan->initPlan = PlannerInitPlan;
 127
 128         /* Get extParam from InitPlan-s */
 129         foreach(lst, PlannerInitPlan)
 130         {
 131                 List       *lp;
 132
 133                 foreach(lp, ((SubPlan *) lfirst(lst))->plan->extParam)
 134                 {
 135                         if (!intMember(lfirsti(lp), plan->extParam))
 136                                 plan->extParam = lappendi(plan->extParam, lfirsti(lp));
 137                 }
 138         }
 139
 140         /* and now we are parent again */
 141         PlannerInitPlan = saved_ip;
 142         PlannerQueryLevel--;
 143
 144         node->plan_id = PlannerPlanId++;
 145         node->rtable = ((Query *) slink->subselect)->rtable;
 146         node->sublink = slink;
 147         slink->subselect = NULL;        /* cool ?! */
 148
 149         /* make parParam list */
 150         foreach(lst, plan->extParam)
 151         {
 152                 Var                *var = nth(lfirsti(lst), PlannerParamVar);
 153
 154                 if (var->varlevelsup == PlannerQueryLevel)
 155                         node->parParam = lappendi(node->parParam, lfirsti(lst));
 156         }
 157
 158         /*
 159          * Un-correlated or undirect correlated plans of EXISTS or EXPR types
 160          * can be used as initPlans...
 161          */
 162         if (node->parParam == NULL && slink->subLinkType == EXPR_SUBLINK)
 163         {
 164                 int                     i = 0;
 165
 166                 /* transform right side of all sublink Oper-s into Param */
 167                 foreach(lst, slink->oper)
 168                 {
 169                         List       *rside = lnext(((Expr *) lfirst(lst))->args);
 170                         TargetEntry *te = nth(i, plan->targetlist);
 171                         Var                *var = makeVar(0, 0, te->resdom->restype,
 172                                                                           te->resdom->restypmod,
 173                                                                           PlannerQueryLevel, 0, 0);
 174                         Param      *prm = makeNode(Param);
 175
 176                         prm->paramkind = PARAM_EXEC;
 177                         prm->paramid = (AttrNumber) _new_param(var, PlannerQueryLevel);
 178                         prm->paramtype = var->vartype;
 179                         lfirst(rside) = prm;
 180                         node->setParam = lappendi(node->setParam, prm->paramid);
 181                         pfree(var);
 182                         i++;
 183                 }
 184                 PlannerInitPlan = lappend(PlannerInitPlan, node);
 185                 if (i > 1)
 186                         result = (Node *) ((slink->useor) ? make_orclause(slink->oper) :
 187                                                            make_andclause(slink->oper));
 188                 else
 189                         result = (Node *) lfirst(slink->oper);
 190         }
 191         else if (node->parParam == NULL && slink->subLinkType == EXISTS_SUBLINK)
 192         {
 193                 Var                *var = makeVar(0, 0, BOOLOID, -1, PlannerQueryLevel, 0, 0);
 194                 Param      *prm = makeNode(Param);
 195
 196                 prm->paramkind = PARAM_EXEC;
 197                 prm->paramid = (AttrNumber) _new_param(var, PlannerQueryLevel);
 198                 prm->paramtype = var->vartype;
 199                 node->setParam = lappendi(node->setParam, prm->paramid);
 200                 pfree(var);
 201                 PlannerInitPlan = lappend(PlannerInitPlan, node);
 202                 result = (Node *) prm;
 203         }
 204         else
 205 /* make expression of SUBPLAN type */
 206         {
 207                 Expr       *expr = makeNode(Expr);
 208                 List       *args = NULL;
 209                 int                     i = 0;
 210
 211                 expr->typeOid = BOOLOID;
 212                 expr->opType = SUBPLAN_EXPR;
 213                 expr->oper = (Node *) node;
 214
 215                 /*
 216                  * Make expr->args from parParam. Left sides of sublink Oper-s are
 217                  * handled by optimizer directly... Also, transform right side of
 218                  * sublink Oper-s into Const.
 219                  */
 220                 foreach(lst, node->parParam)
 221                 {
 222                         Var                *var = nth(lfirsti(lst), PlannerParamVar);
 223
 224                         var = (Var *) copyObject(var);
 225                         var->varlevelsup = 0;
 226                         args = lappend(args, var);
 227                 }
 228                 foreach(lst, slink->oper)
 229                 {
 230                         List       *rside = lnext(((Expr *) lfirst(lst))->args);
 231                         TargetEntry *te = nth(i, plan->targetlist);
 232                         Const      *con = makeConst(te->resdom->restype,
 233                                                                                 0, 0, true, 0, 0, 0);
 234
 235                         lfirst(rside) = con;
 236                         i++;
 237                 }
 238                 expr->args = args;
 239                 result = (Node *) expr;
 240         }
 241
 242         return result;
 243
 244 }
 245
 246 static List *
 247 set_unioni(List *l1, List *l2)
 248 {
 249         if (l1 == NULL)
 250                 return l2;
 251         if (l2 == NULL)
 252                 return l1;
 253
 254         return nconc(l1, set_differencei(l2, l1));
 255 }
 256
 257 static List *
 258 _finalize_primnode(void *expr, List **subplan)
 259 {
 260         List       *result = NULL;
 261
 262         if (expr == NULL)
 263                 return NULL;
 264
 265         if (IsA(expr, Param))
 266         {
 267                 if (((Param *) expr)->paramkind == PARAM_EXEC)
 268                         return lconsi(((Param *) expr)->paramid, (List *) NULL);
 269         }
 270         else if (single_node(expr))
 271                 return NULL;
 272         else if (IsA(expr, List))
 273         {
 274                 List       *le;
 275
 276                 foreach(le, (List *) expr)
 277                         result = set_unioni(result,
 278                                                                 _finalize_primnode(lfirst(le), subplan));
 279         }
 280         else if (IsA(expr, Iter))
 281                 return _finalize_primnode(((Iter *) expr)->iterexpr, subplan);
 282         else if (or_clause(expr) || and_clause(expr) || is_opclause(expr) ||
 283                          not_clause(expr) || is_funcclause(expr))
 284                 return _finalize_primnode(((Expr *) expr)->args, subplan);
 285         else if (IsA(expr, Aggref))
 286                 return _finalize_primnode(((Aggref *) expr)->target, subplan);
 287         else if (IsA(expr, ArrayRef))
 288         {
 289                 result = _finalize_primnode(((ArrayRef *) expr)->refupperindexpr, subplan);
 290                 result = set_unioni(result,
 291                                                         _finalize_primnode(((ArrayRef *) expr)->reflowerindexpr, subplan));
 292                 result = set_unioni(result,
 293                           _finalize_primnode(((ArrayRef *) expr)->refexpr, subplan));
 294                 result = set_unioni(result,
 295                  _finalize_primnode(((ArrayRef *) expr)->refassgnexpr, subplan));
 296         }
 297         else if (IsA(expr, TargetEntry))
 298                 return _finalize_primnode(((TargetEntry *) expr)->expr, subplan);
 299         else if (is_subplan(expr))
 300         {
 301                 List       *lst;
 302
 303                 *subplan = lappend(*subplan, ((Expr *) expr)->oper);
 304                 foreach(lst, ((SubPlan *) ((Expr *) expr)->oper)->plan->extParam)
 305                 {
 306                         Var                *var = nth(lfirsti(lst), PlannerParamVar);
 307
 308                         if (var->varlevelsup < PlannerQueryLevel &&
 309                                 !intMember(lfirsti(lst), result))
 310                                 result = lappendi(result, lfirsti(lst));
 311                 }
 312         }
 313         else
 314                 elog(ERROR, "_finalize_primnode: can't handle node %d",
 315                          nodeTag(expr));
 316
 317         return result;
 318 }
 319
 320 Node *
 321 SS_replace_correlation_vars(Node *expr)
 322 {
 323
 324         if (expr == NULL)
 325                 return NULL;
 326         if (IsA(expr, List))
 327         {
 328                 List       *le;
 329
 330                 foreach(le, (List *) expr)
 331                         lfirst(le) = SS_replace_correlation_vars((Node *) lfirst(le));
 332         }
 333         else if (IsA(expr, Var))
 334         {
 335                 if (((Var *) expr)->varlevelsup > 0)
 336                 {
 337                         Assert(((Var *) expr)->varlevelsup < PlannerQueryLevel);
 338                         expr = (Node *) _replace_var((Var *) expr);
 339                 }
 340         }
 341         else if (IsA(expr, Iter))
 342         {
 343                 ((Iter *) expr)->iterexpr = SS_replace_correlation_vars(((Iter *) expr)->iterexpr);
 344         }
 345         else if (single_node(expr))
 346                 return expr;
 347         else if (or_clause(expr) || and_clause(expr) || is_opclause(expr) ||
 348                          not_clause(expr) || is_funcclause(expr))
 349                 ((Expr *) expr)->args = (List *)
 350                         SS_replace_correlation_vars((Node *) ((Expr *) expr)->args);
 351         else if (IsA(expr, Aggref))
 352                 ((Aggref *) expr)->target = SS_replace_correlation_vars((Node *) ((Aggref *) expr)->target);
 353         else if (IsA(expr, ArrayRef))
 354         {
 355                 ((ArrayRef *) expr)->refupperindexpr = (List *)
 356                         SS_replace_correlation_vars((Node *) ((ArrayRef *) expr)->refupperindexpr);
 357                 ((ArrayRef *) expr)->reflowerindexpr = (List *)
 358                         SS_replace_correlation_vars((Node *) ((ArrayRef *) expr)->reflowerindexpr);
 359                 ((ArrayRef *) expr)->refexpr = SS_replace_correlation_vars((Node *) ((ArrayRef *) expr)->refexpr);
 360                 ((ArrayRef *) expr)->refassgnexpr = SS_replace_correlation_vars(((ArrayRef *) expr)->refassgnexpr);
 361         }
 362         else if (IsA(expr, TargetEntry))
 363                 ((TargetEntry *) expr)->expr = SS_replace_correlation_vars((Node *) ((TargetEntry *) expr)->expr);
 364         else if (IsA(expr, SubLink))
 365         {
 366                 List       *le;
 367
 368                 foreach(le, ((SubLink *) expr)->oper)   /* left sides only */
 369                 {
 370                         List       *oparg = ((Expr *) lfirst(le))->args;
 371
 372                         lfirst(oparg) = (List *)
 373                                 SS_replace_correlation_vars((Node *) lfirst(oparg));
 374                 }
 375                 ((SubLink *) expr)->lefthand = (List *)
 376                         SS_replace_correlation_vars((Node *) ((SubLink *) expr)->lefthand);
 377         }
 378         else
 379                 elog(NOTICE, "SS_replace_correlation_vars: can't handle node %d",
 380                          nodeTag(expr));
 381
 382         return expr;
 383 }
 384
 385 Node *
 386 SS_process_sublinks(Node *expr)
 387 {
 388         if (expr == NULL)
 389                 return NULL;
 390         if (IsA(expr, List))
 391         {
 392                 List       *le;
 393
 394                 foreach(le, (List *) expr)
 395                         lfirst(le) = SS_process_sublinks((Node *) lfirst(le));
 396         }
 397         else if (or_clause(expr) || and_clause(expr) || is_opclause(expr) ||
 398                          not_clause(expr) || is_funcclause(expr))
 399                 ((Expr *) expr)->args = (List *)
 400                         SS_process_sublinks((Node *) ((Expr *) expr)->args);
 401         else if (IsA(expr, SubLink))/* got it! */
 402         {
 403                 expr = _make_subplan((SubLink *) expr);
 404         }
 405
 406         return expr;
 407 }
 408
 409 List *
 410 SS_finalize_plan(Plan *plan)
 411 {
 412         List       *extParam = NULL;
 413         List       *locParam = NULL;
 414         List       *subPlan = NULL;
 415         List       *param_list;
 416         List       *lst;
 417
 418         if (plan == NULL)
 419                 return NULL;
 420
 421         param_list = _finalize_primnode(plan->targetlist, &subPlan);
 422         Assert(subPlan == NULL);
 423
 424         switch (nodeTag(plan))
 425         {
 426                 case T_Result:
 427                         param_list = set_unioni(param_list,
 428                                                                         _finalize_primnode(((Result *) plan)->resconstantqual, &subPlan));
 429                         /* subPlan is NOT necessarily NULL here ... */
 430                         break;
 431
 432                 case T_Append:
 433                         foreach(lst, ((Append *) plan)->appendplans)
 434                                 param_list = set_unioni(param_list,
 435                                                                  SS_finalize_plan((Plan *) lfirst(lst)));
 436                         break;
 437
 438                 case T_IndexScan:
 439                         param_list = set_unioni(param_list,
 440                         _finalize_primnode(((IndexScan *) plan)->indxqual, &subPlan));
 441                         Assert(subPlan == NULL);
 442                         break;
 443
 444                 case T_MergeJoin:
 445                         param_list = set_unioni(param_list,
 446                                                                         _finalize_primnode(((MergeJoin *) plan)->mergeclauses, &subPlan));
 447                         Assert(subPlan == NULL);
 448                         break;
 449
 450                 case T_HashJoin:
 451                         param_list = set_unioni(param_list,
 452                                                                         _finalize_primnode(((HashJoin *) plan)->hashclauses, &subPlan));
 453                         Assert(subPlan == NULL);
 454                         break;
 455
 456                 case T_Hash:
 457                         param_list = set_unioni(param_list,
 458                                  _finalize_primnode(((Hash *) plan)->hashkey, &subPlan));
 459                         Assert(subPlan == NULL);
 460                         break;
 461
 462                 case T_Agg:
 463                         param_list = set_unioni(param_list,
 464                                          _finalize_primnode(((Agg *) plan)->aggs, &subPlan));
 465                         Assert(subPlan == NULL);
 466                         break;
 467
 468                 case T_SeqScan:
 469                 case T_NestLoop:
 470                 case T_Material:
 471                 case T_Sort:
 472                 case T_Unique:
 473                 case T_Group:
 474                         break;
 475                 default:
 476                         elog(ERROR, "SS_finalize_plan: node %d unsupported", nodeTag(plan));
 477                         return NULL;
 478         }
 479
 480         param_list = set_unioni(param_list, _finalize_primnode(plan->qual, &subPlan));
 481         param_list = set_unioni(param_list, SS_finalize_plan(plan->lefttree));
 482         param_list = set_unioni(param_list, SS_finalize_plan(plan->righttree));
 483
 484         foreach(lst, param_list)
 485         {
 486                 Var                *var = nth(lfirsti(lst), PlannerParamVar);
 487
 488                 if (var->varlevelsup < PlannerQueryLevel)
 489                         extParam = lappendi(extParam, lfirsti(lst));
 490                 else if (var->varlevelsup > PlannerQueryLevel)
 491                         elog(ERROR, "SS_finalize_plan: plan shouldn't reference subplan' variable");
 492                 else
 493                 {
 494                         Assert(var->varno == 0 && var->varattno == 0);
 495                         locParam = lappendi(locParam, lfirsti(lst));
 496                 }
 497         }
 498
 499         plan->extParam = extParam;
 500         plan->locParam = locParam;
 501         plan->subPlan = subPlan;
 502
 503         return param_list;
 504
 505 }
 506
 507 /* Construct a list of all subplans found within the given node tree */
 508
 509 List *
 510 SS_pull_subplan(Node *expr)
 511 {
 512         List       *result = NULL;
 513
 514         if (expr == NULL || single_node(expr))
 515                 return NULL;
 516
 517         if (IsA(expr, List))
 518         {
 519                 List       *le;
 520
 521                 foreach(le, (List *) expr)
 522                         result = nconc(result, SS_pull_subplan(lfirst(le)));
 523         }
 524         else if (IsA(expr, Iter))
 525                 return SS_pull_subplan(((Iter *) expr)->iterexpr);
 526         else if (or_clause(expr) || and_clause(expr) || is_opclause(expr) ||
 527                          not_clause(expr) || is_funcclause(expr))
 528                 return SS_pull_subplan((Node *) ((Expr *) expr)->args);
 529         else if (IsA(expr, Aggref))
 530                 return SS_pull_subplan(((Aggref *) expr)->target);
 531         else if (IsA(expr, ArrayRef))
 532         {
 533                 result = SS_pull_subplan((Node *)((ArrayRef *) expr)->refupperindexpr);
 534                 result = nconc(result,
 535                                 SS_pull_subplan((Node*) ((ArrayRef *) expr)->reflowerindexpr));
 536                 result = nconc(result,
 537                                            SS_pull_subplan(((ArrayRef *) expr)->refexpr));
 538                 result = nconc(result,
 539                                            SS_pull_subplan(((ArrayRef *) expr)->refassgnexpr));
 540         }
 541         else if (IsA(expr, TargetEntry))
 542                 return SS_pull_subplan(((TargetEntry *) expr)->expr);
 543         else if (is_subplan(expr))
 544                 return lcons(((Expr *) expr)->oper, NULL);
 545         else
 546                 elog(ERROR, "SS_pull_subplan: can't handle node %d",
 547                          nodeTag(expr));
 548
 549         return result;
 550 }