~ubuntu-branches/ubuntu/karmic/postgresql-8.4/karmic-security

« back to all changes in this revision

Viewing changes to src/backend/optimizer/prep/prepjointree.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2009-05-05 00:58:06 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20090505005806-c19tt7oyqb7kuw49
Tags: 8.4~beta1+cvs20090503-1
New upstream snapshot.

Show diffs side-by-side

added added

removed removed

Lines of Context:
47
47
                                                          Relids available_rels, Node **jtlink);
48
48
static Node *pull_up_simple_subquery(PlannerInfo *root, Node *jtnode,
49
49
                                                RangeTblEntry *rte,
50
 
                                                bool below_outer_join,
51
 
                                                bool append_rel_member);
 
50
                                                JoinExpr *lowest_outer_join,
 
51
                                                AppendRelInfo *containing_appendrel);
52
52
static Node *pull_up_simple_union_all(PlannerInfo *root, Node *jtnode,
53
53
                                                 RangeTblEntry *rte);
54
54
static void pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root,
63
63
static List *insert_targetlist_placeholders(PlannerInfo *root, List *tlist,
64
64
                                                                                        int varno, bool wrap_non_vars);
65
65
static bool is_safe_append_member(Query *subquery);
66
 
static void resolvenew_in_jointree(Node *jtnode, int varno,
67
 
                                           RangeTblEntry *rte, List *subtlist);
 
66
static void resolvenew_in_jointree(Node *jtnode, int varno, RangeTblEntry *rte,
 
67
                                           List *subtlist, List *subtlist_with_phvs,
 
68
                                           JoinExpr *lowest_outer_join);
68
69
static reduce_outer_joins_state *reduce_outer_joins_pass1(Node *jtnode);
69
70
static void reduce_outer_joins_pass2(Node *jtnode,
70
71
                                                 reduce_outer_joins_state *state,
440
441
 *              Also, subqueries that are simple UNION ALL structures can be
441
442
 *              converted into "append relations".
442
443
 *
443
 
 * below_outer_join is true if this jointree node is within the nullable
444
 
 * side of an outer join.  This forces use of the PlaceHolderVar mechanism
445
 
 * for non-nullable targetlist items.
 
444
 * If this jointree node is within the nullable side of an outer join, then
 
445
 * lowest_outer_join references the lowest such JoinExpr node; otherwise it
 
446
 * is NULL.  This forces use of the PlaceHolderVar mechanism for references
 
447
 * to non-nullable targetlist items, but only for references above that join.
446
448
 *
447
 
 * append_rel_member is true if we are looking at a member subquery of
448
 
 * an append relation.  This forces use of the PlaceHolderVar mechanism
449
 
 * for all non-Var targetlist items, and puts some additional restrictions
450
 
 * on what can be pulled up.
 
449
 * If we are looking at a member subquery of an append relation,
 
450
 * containing_appendrel describes that relation; else it is NULL.
 
451
 * This forces use of the PlaceHolderVar mechanism for all non-Var targetlist
 
452
 * items, and puts some additional restrictions on what can be pulled up.
451
453
 *
452
454
 * A tricky aspect of this code is that if we pull up a subquery we have
453
455
 * to replace Vars that reference the subquery's outputs throughout the
457
459
 * subquery RangeTblRef entries will be replaced.  Also, we can't turn
458
460
 * ResolveNew loose on the whole jointree, because it'll return a mutated
459
461
 * copy of the tree; we have to invoke it just on the quals, instead.
 
462
 * This behavior is what makes it reasonable to pass lowest_outer_join as a
 
463
 * pointer rather than some more-indirect way of identifying the lowest OJ.
 
464
 * Likewise, we don't replace append_rel_list members but only their
 
465
 * substructure, so the containing_appendrel reference is safe to use.
460
466
 */
461
467
Node *
462
468
pull_up_subqueries(PlannerInfo *root, Node *jtnode,
463
 
                                   bool below_outer_join, bool append_rel_member)
 
469
                                   JoinExpr *lowest_outer_join,
 
470
                                   AppendRelInfo *containing_appendrel)
464
471
{
465
472
        if (jtnode == NULL)
466
473
                return NULL;
478
485
                 */
479
486
                if (rte->rtekind == RTE_SUBQUERY &&
480
487
                        is_simple_subquery(rte->subquery) &&
481
 
                        (!append_rel_member || is_safe_append_member(rte->subquery)))
 
488
                        (containing_appendrel == NULL ||
 
489
                         is_safe_append_member(rte->subquery)))
482
490
                        return pull_up_simple_subquery(root, jtnode, rte,
483
 
                                                                                   below_outer_join,
484
 
                                                                                   append_rel_member);
 
491
                                                                                   lowest_outer_join,
 
492
                                                                                   containing_appendrel);
485
493
 
486
494
                /*
487
495
                 * Alternatively, is it a simple UNION ALL subquery?  If so, flatten
503
511
                FromExpr   *f = (FromExpr *) jtnode;
504
512
                ListCell   *l;
505
513
 
506
 
                Assert(!append_rel_member);
 
514
                Assert(containing_appendrel == NULL);
507
515
                foreach(l, f->fromlist)
508
516
                        lfirst(l) = pull_up_subqueries(root, lfirst(l),
509
 
                                                                                   below_outer_join, false);
 
517
                                                                                   lowest_outer_join, NULL);
510
518
        }
511
519
        else if (IsA(jtnode, JoinExpr))
512
520
        {
513
521
                JoinExpr   *j = (JoinExpr *) jtnode;
514
522
 
515
 
                Assert(!append_rel_member);
 
523
                Assert(containing_appendrel == NULL);
516
524
                /* Recurse, being careful to tell myself when inside outer join */
517
525
                switch (j->jointype)
518
526
                {
519
527
                        case JOIN_INNER:
520
528
                                j->larg = pull_up_subqueries(root, j->larg,
521
 
                                                                                         below_outer_join, false);
 
529
                                                                                         lowest_outer_join, NULL);
522
530
                                j->rarg = pull_up_subqueries(root, j->rarg,
523
 
                                                                                         below_outer_join, false);
 
531
                                                                                         lowest_outer_join, NULL);
524
532
                                break;
525
533
                        case JOIN_LEFT:
526
534
                        case JOIN_SEMI:
527
535
                        case JOIN_ANTI:
528
536
                                j->larg = pull_up_subqueries(root, j->larg,
529
 
                                                                                         below_outer_join, false);
 
537
                                                                                         lowest_outer_join, NULL);
530
538
                                j->rarg = pull_up_subqueries(root, j->rarg,
531
 
                                                                                         true, false);
 
539
                                                                                         j, NULL);
532
540
                                break;
533
541
                        case JOIN_FULL:
534
542
                                j->larg = pull_up_subqueries(root, j->larg,
535
 
                                                                                         true, false);
 
543
                                                                                         j, NULL);
536
544
                                j->rarg = pull_up_subqueries(root, j->rarg,
537
 
                                                                                         true, false);
 
545
                                                                                         j, NULL);
538
546
                                break;
539
547
                        case JOIN_RIGHT:
540
548
                                j->larg = pull_up_subqueries(root, j->larg,
541
 
                                                                                         true, false);
 
549
                                                                                         j, NULL);
542
550
                                j->rarg = pull_up_subqueries(root, j->rarg,
543
 
                                                                                         below_outer_join, false);
 
551
                                                                                         lowest_outer_join, NULL);
544
552
                                break;
545
553
                        default:
546
554
                                elog(ERROR, "unrecognized join type: %d",
562
570
 * subquery by pull_up_subqueries.      We return the replacement jointree node,
563
571
 * or jtnode itself if we determine that the subquery can't be pulled up after
564
572
 * all.
 
573
 *
 
574
 * rte is the RangeTblEntry referenced by jtnode.  Remaining parameters are
 
575
 * as for pull_up_subqueries.
565
576
 */
566
577
static Node *
567
578
pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
568
 
                                                bool below_outer_join, bool append_rel_member)
 
579
                                                JoinExpr *lowest_outer_join,
 
580
                                                AppendRelInfo *containing_appendrel)
569
581
{
570
582
        Query      *parse = root->parse;
571
583
        int                     varno = ((RangeTblRef *) jtnode)->rtindex;
573
585
        PlannerInfo *subroot;
574
586
        int                     rtoffset;
575
587
        List       *subtlist;
576
 
        ListCell   *rt;
 
588
        List       *subtlist_with_phvs;
 
589
        ListCell   *lc;
577
590
 
578
591
        /*
579
592
         * Need a modifiable copy of the subquery to hack on.  Even if we didn't
624
637
         * pull_up_subqueries' processing is complete for its jointree and
625
638
         * rangetable.
626
639
         *
627
 
         * Note: below_outer_join = false is correct here even if we are within an
628
 
         * outer join in the upper query; the lower query starts with a clean
629
 
         * slate for outer-join semantics.      Likewise, we say we aren't handling an
 
640
         * Note: we should pass NULL for containing-join info even if we are within
 
641
         * an outer join in the upper query; the lower query starts with a clean
 
642
         * slate for outer-join semantics.  Likewise, we say we aren't handling an
630
643
         * appendrel member.
631
644
         */
632
645
        subquery->jointree = (FromExpr *)
633
 
                pull_up_subqueries(subroot, (Node *) subquery->jointree, false, false);
 
646
                pull_up_subqueries(subroot, (Node *) subquery->jointree, NULL, NULL);
634
647
 
635
648
        /*
636
649
         * Now we must recheck whether the subquery is still simple enough to pull
641
654
         * pull_up_subqueries.
642
655
         */
643
656
        if (is_simple_subquery(subquery) &&
644
 
                (!append_rel_member || is_safe_append_member(subquery)))
 
657
                (containing_appendrel == NULL || is_safe_append_member(subquery)))
645
658
        {
646
659
                /* good to go */
647
660
        }
677
690
        /*
678
691
         * The subquery's targetlist items are now in the appropriate form to
679
692
         * insert into the top query, but if we are under an outer join then
680
 
         * non-nullable items have to be turned into PlaceHolderVars.  If we
 
693
         * non-nullable items may have to be turned into PlaceHolderVars.  If we
681
694
         * are dealing with an appendrel member then anything that's not a
682
695
         * simple Var has to be turned into a PlaceHolderVar.
683
696
         */
684
 
        if (below_outer_join || append_rel_member)
685
 
                subtlist = insert_targetlist_placeholders(root, subquery->targetList,
686
 
                                                                                                  varno, append_rel_member);
 
697
        subtlist = subquery->targetList;
 
698
        if (lowest_outer_join != NULL || containing_appendrel != NULL)
 
699
                subtlist_with_phvs = insert_targetlist_placeholders(root,
 
700
                                                                                                                        subtlist,
 
701
                                                                                                                        varno,
 
702
                                                                                                                        containing_appendrel != NULL);
687
703
        else
688
 
                subtlist = subquery->targetList;
 
704
                subtlist_with_phvs = subtlist;
689
705
 
690
706
        /*
691
707
         * Replace all of the top query's references to the subquery's outputs
692
708
         * with copies of the adjusted subtlist items, being careful not to
693
709
         * replace any of the jointree structure. (This'd be a lot cleaner if we
694
 
         * could use query_tree_mutator.)
 
710
         * could use query_tree_mutator.)  We have to use PHVs in the targetList,
 
711
         * returningList, and havingQual, since those are certainly above any
 
712
         * outer join.  resolvenew_in_jointree tracks its location in the jointree
 
713
         * and uses PHVs or not appropriately.
695
714
         */
696
715
        parse->targetList = (List *)
697
716
                ResolveNew((Node *) parse->targetList,
698
717
                                   varno, 0, rte,
699
 
                                   subtlist, CMD_SELECT, 0);
 
718
                                   subtlist_with_phvs, CMD_SELECT, 0);
700
719
        parse->returningList = (List *)
701
720
                ResolveNew((Node *) parse->returningList,
702
721
                                   varno, 0, rte,
703
 
                                   subtlist, CMD_SELECT, 0);
704
 
        resolvenew_in_jointree((Node *) parse->jointree, varno,
705
 
                                                   rte, subtlist);
 
722
                                   subtlist_with_phvs, CMD_SELECT, 0);
 
723
        resolvenew_in_jointree((Node *) parse->jointree, varno, rte,
 
724
                                                   subtlist, subtlist_with_phvs,
 
725
                                                   lowest_outer_join);
706
726
        Assert(parse->setOperations == NULL);
707
727
        parse->havingQual =
708
728
                ResolveNew(parse->havingQual,
709
729
                                   varno, 0, rte,
710
 
                                   subtlist, CMD_SELECT, 0);
711
 
        root->append_rel_list = (List *)
712
 
                ResolveNew((Node *) root->append_rel_list,
713
 
                                   varno, 0, rte,
714
 
                                   subtlist, CMD_SELECT, 0);
715
 
 
716
 
        foreach(rt, parse->rtable)
717
 
        {
718
 
                RangeTblEntry *otherrte = (RangeTblEntry *) lfirst(rt);
 
730
                                   subtlist_with_phvs, CMD_SELECT, 0);
 
731
 
 
732
        /*
 
733
         * Replace references in the translated_vars lists of appendrels.
 
734
         * When pulling up an appendrel member, we do not need PHVs in the list
 
735
         * of the parent appendrel --- there isn't any outer join between.
 
736
         * Elsewhere, use PHVs for safety.  (This analysis could be made tighter
 
737
         * but it seems unlikely to be worth much trouble.)
 
738
         */
 
739
        foreach(lc, root->append_rel_list)
 
740
        {
 
741
                AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
 
742
 
 
743
                appinfo->translated_vars = (List *)
 
744
                        ResolveNew((Node *) appinfo->translated_vars,
 
745
                                           varno, 0, rte,
 
746
                                           (appinfo == containing_appendrel) ?
 
747
                                           subtlist : subtlist_with_phvs,
 
748
                                           CMD_SELECT, 0);
 
749
        }
 
750
 
 
751
        /*
 
752
         * Replace references in the joinaliasvars lists of join RTEs.
 
753
         *
 
754
         * You might think that we could avoid using PHVs for alias vars of joins
 
755
         * below lowest_outer_join, but that doesn't work because the alias vars
 
756
         * could be referenced above that join; we need the PHVs to be present
 
757
         * in such references after the alias vars get flattened.  (It might be
 
758
         * worth trying to be smarter here, someday.)
 
759
         */
 
760
        foreach(lc, parse->rtable)
 
761
        {
 
762
                RangeTblEntry *otherrte = (RangeTblEntry *) lfirst(lc);
719
763
 
720
764
                if (otherrte->rtekind == RTE_JOIN)
721
765
                        otherrte->joinaliasvars = (List *)
722
766
                                ResolveNew((Node *) otherrte->joinaliasvars,
723
767
                                                   varno, 0, rte,
724
 
                                                   subtlist, CMD_SELECT, 0);
 
768
                                                   subtlist_with_phvs, CMD_SELECT, 0);
725
769
        }
726
770
 
727
771
        /*
884
928
                /*
885
929
                 * Recursively apply pull_up_subqueries to the new child RTE.  (We
886
930
                 * must build the AppendRelInfo first, because this will modify it.)
887
 
                 * Note that we can pass below_outer_join = false even if we're
 
931
                 * Note that we can pass NULL for containing-join info even if we're
888
932
                 * actually under an outer join, because the child's expressions
889
933
                 * aren't going to propagate up above the join.
890
934
                 */
891
935
                rtr = makeNode(RangeTblRef);
892
936
                rtr->rtindex = childRTindex;
893
 
                (void) pull_up_subqueries(root, (Node *) rtr, false, true);
 
937
                (void) pull_up_subqueries(root, (Node *) rtr, NULL, appinfo);
894
938
        }
895
939
        else if (IsA(setOp, SetOperationStmt))
896
940
        {
1096
1140
 *        Insert PlaceHolderVar nodes into any non-junk targetlist items that are
1097
1141
 *        not simple variables or strict functions of simple variables (and hence
1098
1142
 *        might not correctly go to NULL when examined above the point of an outer
1099
 
 *        join).  We assume we can modify the tlist items in-place.
 
1143
 *        join).
1100
1144
 *
1101
1145
 * varno is the upper-query relid of the subquery; this is used as the
1102
1146
 * syntactic location of the PlaceHolderVars.
1107
1151
insert_targetlist_placeholders(PlannerInfo *root, List *tlist,
1108
1152
                                                           int varno, bool wrap_non_vars)
1109
1153
{
 
1154
        List       *result = NIL;
1110
1155
        ListCell   *lc;
1111
1156
 
1112
1157
        foreach(lc, tlist)
1113
1158
        {
1114
1159
                TargetEntry *tle = (TargetEntry *) lfirst(lc);
 
1160
                TargetEntry *newtle;
1115
1161
 
1116
 
                /* ignore resjunk columns */
 
1162
                /* resjunk columns need not be changed */
1117
1163
                if (tle->resjunk)
 
1164
                {
 
1165
                        result = lappend(result, tle);
1118
1166
                        continue;
 
1167
                }
1119
1168
 
1120
1169
                /*
1121
1170
                 * Simple Vars always escape being wrapped.  This is common enough
1123
1172
                 */
1124
1173
                if (tle->expr && IsA(tle->expr, Var) &&
1125
1174
                        ((Var *) tle->expr)->varlevelsup == 0)
 
1175
                {
 
1176
                        result = lappend(result, tle);
1126
1177
                        continue;
 
1178
                }
1127
1179
 
1128
1180
                if (!wrap_non_vars)
1129
1181
                {
1136
1188
                         */
1137
1189
                        if (contain_vars_of_level((Node *) tle->expr, 0) &&
1138
1190
                                !contain_nonstrict_functions((Node *) tle->expr))
 
1191
                        {
 
1192
                                result = lappend(result, tle);
1139
1193
                                continue;
 
1194
                        }
1140
1195
                }
1141
1196
 
1142
1197
                /* Else wrap it in a PlaceHolderVar */
1143
 
                tle->expr = (Expr *) make_placeholder_expr(root,
1144
 
                                                                                                   tle->expr,
1145
 
                                                                                                   bms_make_singleton(varno));
 
1198
                newtle = makeNode(TargetEntry);
 
1199
                memcpy(newtle, tle, sizeof(TargetEntry));
 
1200
                newtle->expr = (Expr *)
 
1201
                        make_placeholder_expr(root,
 
1202
                                                                  tle->expr,
 
1203
                                                                  bms_make_singleton(varno));
 
1204
                result = lappend(result, newtle);
1146
1205
        }
1147
 
        return tlist;
 
1206
        return result;
1148
1207
}
1149
1208
 
1150
1209
/*
1187
1246
 * Helper routine for pull_up_subqueries: do ResolveNew on every expression
1188
1247
 * in the jointree, without changing the jointree structure itself.  Ugly,
1189
1248
 * but there's no other way...
 
1249
 *
 
1250
 * If we are above lowest_outer_join then use subtlist_with_phvs; at or
 
1251
 * below it, use subtlist.  (When no outer joins are in the picture,
 
1252
 * these will be the same list.)
1190
1253
 */
1191
1254
static void
1192
 
resolvenew_in_jointree(Node *jtnode, int varno,
1193
 
                                           RangeTblEntry *rte, List *subtlist)
 
1255
resolvenew_in_jointree(Node *jtnode, int varno, RangeTblEntry *rte,
 
1256
                                           List *subtlist, List *subtlist_with_phvs,
 
1257
                                           JoinExpr *lowest_outer_join)
1194
1258
{
1195
1259
        if (jtnode == NULL)
1196
1260
                return;
1204
1268
                ListCell   *l;
1205
1269
 
1206
1270
                foreach(l, f->fromlist)
1207
 
                        resolvenew_in_jointree(lfirst(l), varno, rte, subtlist);
 
1271
                        resolvenew_in_jointree(lfirst(l), varno, rte,
 
1272
                                                                   subtlist, subtlist_with_phvs,
 
1273
                                                                   lowest_outer_join);
1208
1274
                f->quals = ResolveNew(f->quals,
1209
1275
                                                          varno, 0, rte,
1210
 
                                                          subtlist, CMD_SELECT, 0);
 
1276
                                                          subtlist_with_phvs, CMD_SELECT, 0);
1211
1277
        }
1212
1278
        else if (IsA(jtnode, JoinExpr))
1213
1279
        {
1214
1280
                JoinExpr   *j = (JoinExpr *) jtnode;
1215
1281
 
1216
 
                resolvenew_in_jointree(j->larg, varno, rte, subtlist);
1217
 
                resolvenew_in_jointree(j->rarg, varno, rte, subtlist);
 
1282
                if (j == lowest_outer_join)
 
1283
                {
 
1284
                        /* no more PHVs in or below this join */
 
1285
                        subtlist_with_phvs = subtlist;
 
1286
                        lowest_outer_join = NULL;
 
1287
                }
 
1288
                resolvenew_in_jointree(j->larg, varno, rte,
 
1289
                                                           subtlist, subtlist_with_phvs,
 
1290
                                                           lowest_outer_join);
 
1291
                resolvenew_in_jointree(j->rarg, varno, rte,
 
1292
                                                           subtlist, subtlist_with_phvs,
 
1293
                                                           lowest_outer_join);
1218
1294
                j->quals = ResolveNew(j->quals,
1219
1295
                                                          varno, 0, rte,
1220
 
                                                          subtlist, CMD_SELECT, 0);
 
1296
                                                          subtlist_with_phvs, CMD_SELECT, 0);
1221
1297
 
1222
1298
                /*
1223
1299
                 * We don't bother to update the colvars list, since it won't be used