granicus.if.org Git - postgresql/blob - 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 = 1; ; 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         {
  96                 i = _new_param (var, PlannerQueryLevel - var->varlevelsup);
  97         }
  98
  99         retval = makeNode(Param);
 100         retval->paramkind = PARAM_EXEC;
 101         retval->paramid = (AttrNumber) i;
 102         retval->paramtype = var->vartype;
 103
 104         return (retval);
 105 }
 106
 107 static Node*
 108 _make_subplan (SubLink *slink)
 109 {
 110         SubPlan    *node = makeNode (SubPlan);
 111         Plan       *plan;
 112         List       *lst;
 113         Node       *result;
 114         List       *saved_ip = PlannerInitPlan;
 115
 116         PlannerInitPlan = NULL;
 117
 118         PlannerQueryLevel++;            /* we becomes child */
 119
 120         node->plan = plan = union_planner ((Query*) slink->subselect);
 121
 122         /*
 123          * Assign subPlan, extParam and locParam to plan nodes.
 124          * At the moment, SS_finalize_plan doesn't handle initPlan-s
 125          * and so we assigne them to the topmost plan node and take
 126          * care about its extParam too.
 127          */
 128         (void) SS_finalize_plan (plan);
 129         plan->initPlan = PlannerInitPlan;
 130
 131         /* Get extParam from InitPlan-s */
 132         foreach (lst, PlannerInitPlan)
 133         {
 134                 List   *lp;
 135
 136                 foreach (lp, ((SubPlan*) lfirst (lst))->plan->extParam)
 137                 {
 138                         if ( !intMember (lfirsti(lp), plan->extParam) )
 139                                 plan->extParam = lappendi (plan->extParam, lfirsti(lp));
 140                 }
 141         }
 142
 143         /* and now we are parent again */
 144         PlannerInitPlan = saved_ip;
 145         PlannerQueryLevel--;
 146
 147         node->plan_id = PlannerPlanId++;
 148         node->rtable = ((Query*) slink->subselect)->rtable;
 149         node->sublink = slink;
 150         slink->subselect = NULL;        /* cool ?! */
 151
 152         /* make parParam list */
 153         foreach (lst, plan->extParam)
 154         {
 155                 Var        *var = nth (lfirsti(lst), PlannerParamVar);
 156
 157                 if ( var->varlevelsup == PlannerQueryLevel )
 158                         node->parParam = lappendi (node->parParam, lfirsti(lst));
 159         }
 160
 161         /*
 162          * Un-correlated or undirect correlated plans of EXISTS or EXPR
 163          * types can be used as initPlans...
 164          */
 165         if ( node->parParam == NULL && slink->subLinkType == EXPR_SUBLINK )
 166         {
 167                 int     i = 0;
 168
 169                 /* transform right side of all sublink Oper-s into Param */
 170                 foreach (lst, slink->oper)
 171                 {
 172                         List               *rside = lnext(((Expr*) lfirst(lst))->args);
 173                         TargetEntry        *te = nth (i, plan->targetlist);
 174                         Var                        *var = makeVar (0, 0, te->resdom->restype,
 175                                                                                    te->resdom->restypmod,
 176                                                                                    PlannerQueryLevel, 0, 0);
 177                         Param              *prm = makeNode(Param);
 178
 179                         prm->paramkind = PARAM_EXEC;
 180                         prm->paramid = (AttrNumber) _new_param (var, PlannerQueryLevel);
 181                         prm->paramtype = var->vartype;
 182                         lfirst(rside) = prm;
 183                         node->setParam = lappendi (node->setParam, prm->paramid);
 184                         pfree (var);
 185                         i++;
 186                 }
 187                 PlannerInitPlan = lappend (PlannerInitPlan, node);
 188                 if ( i > 1 )
 189                         result = (Node*) ((slink->useor) ? make_orclause (slink->oper) :
 190                                                                                            make_andclause (slink->oper));
 191                 else
 192                         result = (Node*) lfirst (slink->oper);
 193         }
 194         else if ( node->parParam == NULL && slink->subLinkType == EXISTS_SUBLINK )
 195         {
 196                 Var                *var = makeVar (0, 0, BOOLOID, -1, PlannerQueryLevel, 0, 0);
 197                 Param      *prm = makeNode(Param);
 198
 199                 prm->paramkind = PARAM_EXEC;
 200                 prm->paramid = (AttrNumber) _new_param (var, PlannerQueryLevel);
 201                 prm->paramtype = var->vartype;
 202                 node->setParam = lappendi (node->setParam, prm->paramid);
 203                 pfree (var);
 204                 PlannerInitPlan = lappend (PlannerInitPlan, node);
 205                 result = (Node*) prm;
 206         }
 207         else    /* make expression of SUBPLAN type */
 208         {
 209                 Expr   *expr = makeNode (Expr);
 210                 List   *args = NULL;
 211                 int             i = 0;
 212
 213                 expr->typeOid = BOOLOID;
 214                 expr->opType = SUBPLAN_EXPR;
 215                 expr->oper = (Node*) node;
 216
 217                 /*
 218                  * Make expr->args from parParam. Left sides of sublink Oper-s
 219                  * are handled by optimizer directly...
 220                  * Also, transform right side of sublink Oper-s into Const.
 221                  */
 222                 foreach (lst, node->parParam)
 223                 {
 224                         Var        *var = nth (lfirsti (lst), PlannerParamVar);
 225
 226                         var = (Var*) copyObject (var);
 227                         var->varlevelsup = 0;
 228                         args = lappend (args, var);
 229                 }
 230                 foreach (lst, slink->oper)
 231                 {
 232                         List               *rside = lnext(((Expr*) lfirst(lst))->args);
 233                         TargetEntry        *te = nth (i, plan->targetlist);
 234                         Const              *con = makeConst (te->resdom->restype,
 235                                                                                          0, 0, true, 0, 0, 0);
 236                         lfirst(rside) = con;
 237                         i++;
 238                 }
 239                 expr->args = args;
 240                 result = (Node*) expr;
 241         }
 242
 243         return (result);
 244
 245 }
 246
 247 static List *
 248 set_unioni (List *l1, List *l2)
 249 {
 250         if (l1 == NULL)
 251                 return (l2);
 252         if (l2 == NULL)
 253                 return (l1);
 254
 255         return (nconc (l1, set_differencei (l2, l1)));
 256 }
 257
 258 static List *
 259 _finalize_primnode (void *expr, List **subplan)
 260 {
 261         List   *result = NULL;
 262
 263         if ( expr == NULL )
 264                 return (NULL);
 265
 266         if (IsA (expr, Param))
 267         {
 268                 if ( ((Param*) expr)->paramkind == PARAM_EXEC )
 269                         return (lconsi (((Param*) expr)->paramid, (List*) NULL));
 270         }
 271         else if (single_node(expr))
 272                 return (NULL);
 273         else if (IsA (expr, List))
 274         {
 275                 List   *le;
 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, Aggreg))
 286                 return (_finalize_primnode (((Aggreg *) 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                 foreach (le, (List*) expr)
 330                         lfirst(le) = SS_replace_correlation_vars ((Node*) lfirst(le));
 331         }
 332         else if (IsA (expr, Var))
 333         {
 334                 if ( ((Var*) expr)->varlevelsup > 0 )
 335                 {
 336                         Assert (((Var*) expr)->varlevelsup < PlannerQueryLevel);
 337                         expr = (Node*) _replace_var ((Var*) expr);
 338                 }
 339         }
 340         else if (IsA (expr, Iter))
 341         {
 342                 ((Iter*) expr)->iterexpr =
 343                         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, Aggreg))
 352                 ((Aggreg *) expr)->target =
 353                                 SS_replace_correlation_vars ((Node*) ((Aggreg *) expr)->target);
 354         else if (IsA (expr, ArrayRef))
 355         {
 356                 ((ArrayRef *) expr)->refupperindexpr = (List*)
 357                         SS_replace_correlation_vars ((Node*) ((ArrayRef *) expr)->refupperindexpr);
 358                 ((ArrayRef *) expr)->reflowerindexpr = (List*)
 359                         SS_replace_correlation_vars ((Node*) ((ArrayRef *) expr)->reflowerindexpr);
 360                 ((ArrayRef *) expr)->refexpr =
 361                         SS_replace_correlation_vars ((Node*) ((ArrayRef *) expr)->refexpr);
 362                 ((ArrayRef *) expr)->refassgnexpr =
 363                         SS_replace_correlation_vars (((ArrayRef *) expr)->refassgnexpr);
 364         }
 365         else if (IsA (expr, TargetEntry))
 366                 ((TargetEntry*) expr)->expr =
 367                         SS_replace_correlation_vars ((Node*) ((TargetEntry*) expr)->expr);
 368         else if (IsA (expr, SubLink))
 369         {
 370                 List   *le;
 371
 372                 foreach (le, ((SubLink*) expr)->oper)   /* left sides only */
 373                 {
 374                         List   *oparg = ((Expr*) lfirst (le))->args;
 375
 376                         lfirst (oparg) = (List*)
 377                                 SS_replace_correlation_vars ((Node*) lfirst (oparg));
 378                 }
 379                 ((SubLink*) expr)->lefthand = (List*)
 380                         SS_replace_correlation_vars ((Node*) ((SubLink*) expr)->lefthand);
 381         }
 382         else
 383                 elog (NOTICE, "SS_replace_correlation_vars: can't handle node %d",
 384                         nodeTag (expr));
 385
 386         return (expr);
 387 }
 388
 389 Node*
 390 SS_process_sublinks (Node *expr)
 391 {
 392         if ( expr == NULL )
 393                 return (NULL);
 394         if (IsA (expr, List))
 395         {
 396                 List   *le;
 397                 foreach (le, (List*) expr)
 398                         lfirst(le) = SS_process_sublinks ((Node*) lfirst(le));
 399         }
 400         else if (or_clause(expr) || and_clause(expr) || is_opclause(expr) ||
 401                                 not_clause (expr) || is_funcclause(expr))
 402                 ((Expr *) expr)->args = (List*)
 403                         SS_process_sublinks ((Node*) ((Expr *) expr)->args);
 404         else if (IsA (expr, SubLink))           /* got it! */
 405                 expr = _make_subplan ((SubLink*) expr);
 406
 407         return (expr);
 408 }
 409
 410 List*
 411 SS_finalize_plan (Plan *plan)
 412 {
 413         List   *extParam = NULL;
 414         List   *locParam = NULL;
 415         List   *subPlan = NULL;
 416         List   *param_list;
 417         List   *lst;
 418
 419         if ( plan == NULL )
 420                 return (NULL);
 421
 422         param_list = _finalize_primnode (plan->targetlist, &subPlan);
 423         Assert (subPlan == NULL);
 424
 425         switch (nodeTag(plan))
 426         {
 427                 case T_Result:
 428                         param_list = set_unioni (param_list,
 429                                 _finalize_primnode (((Result*) plan)->resconstantqual, &subPlan));
 430                         break;
 431
 432                 case T_Append:
 433                         foreach (lst, ((Append*) plan)->unionplans)
 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 List *SS_pull_subplan (void *expr);
 508
 509 List *
 510 SS_pull_subplan (void *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                 foreach (le, (List*) expr)
 521                         result = nconc (result, SS_pull_subplan (lfirst(le)));
 522         }
 523         else if (IsA (expr, Iter))
 524                 return (SS_pull_subplan (((Iter*) expr)->iterexpr));
 525         else if (or_clause(expr) || and_clause(expr) || is_opclause(expr) ||
 526                                 not_clause (expr) || is_funcclause(expr))
 527                 return (SS_pull_subplan (((Expr*) expr)->args));
 528         else if (IsA (expr, Aggreg))
 529                 return (SS_pull_subplan (((Aggreg *) expr)->target));
 530         else if (IsA (expr, ArrayRef))
 531         {
 532                 result = SS_pull_subplan (((ArrayRef*) expr)->refupperindexpr);
 533                 result = nconc (result,
 534                         SS_pull_subplan (((ArrayRef *) expr)->reflowerindexpr));
 535                 result = nconc (result,
 536                         SS_pull_subplan (((ArrayRef *) expr)->refexpr));
 537                 result = nconc (result,
 538                         SS_pull_subplan (((ArrayRef *) expr)->refassgnexpr));
 539         }
 540         else if (IsA (expr, TargetEntry))
 541                 return (SS_pull_subplan (((TargetEntry*) expr)->expr));
 542         else if (is_subplan (expr))
 543                 return (lcons (((Expr*) expr)->oper, NULL));
 544         else
 545                 elog (ERROR, "SS_pull_subplan: can't handle node %d",
 546                         nodeTag (expr));
 547
 548         return (result);
 549 }