Identity projection - Mailing list pgsql-hackers

Hello.

A very simple query shown below on partitioned tables can run for
four times as long as that on non-partitioned tables when the
whole data can be loaded onto memory.

* QUERY     : SELECT * FROM t;
* EXEC TREE : Result(Append(SeqScan)) for partitioned           : SeqScan                 for non-partitioned

One of the cause seems to be the Result node attached over an
Append node does projection regardless of the necessity.

When executing the query for non-partitioned tables, the top node
receives the tuples in relation heap. Meanwhile, for paritioned
one, the Result node executes projection which is redundant.

This patch reduces run time of such queries by 45% when result
recored has 30 columns and seems to have no harm for performance.
You can see the details of performance measurment later in this
message.

=====
Discussion underlying this patch.

As far as I saw, identity projection can be done by returning
econtext->ecxt_outertuple in ExecProject(). node->ps.ps_projInfo
== NULL also can indicate to do so but I preferred to capsulate
them into ExecProject() rather than scattering codes outside.

# 'identity projection' here means that the projected tuple
# contains all orignal attributes in original order.

The next thing to think is when to do so.

ExecBuildProjectionInfo() which controls direct mapping of tuple
slot had been seemed suitable to do that. But I couldn't find
apropriate condition for judging properly whether the lower tuple
slot can be thrown up to the upper node.

Then, I found set_upper_references() seems suitable. The types
and positions of tlist attributes can be examined in quite clear
way there.

More aggressively, Result node could be pruned for
non-projection-capable plans when it is an identity projection.
But set_upper_references() is called far after here so the
projection is unidentified as identity projection or not at the
moment.


Pros and Cons.

The most important advantage of this patch is significant
reduction of runtime for some part of queries returns many
columns for partitioned tables, and union ops.

The most poor point of this patch, I suppose, might be adding
similar examination for tlists, say, exam for direct mapping in
set_upper_references().. This may be implemented smarter than
this patch.

Additionally to that, two steps of copying the flag
tlist_lower_cogruent from Plan node to PlanState node and finally
onto ProjectionInfo seems somewhat ugly..


=====
Patch summary.

This patch introduces 'identity projection' in the process below.

1. set_upper_references() judges the 'congruency' (is this right wording?) between subplan->targetlist and
plan->tagetlist.And stores the result in plan->tlist_lower_congruent.
 

2. ExecAssignProjectionInfo() passes tlist_lower_congruent to  ExecBuildProjectionInfo() and the ProjectionInfo created
is marked as 'identity' according to the handed  tlist_lower_congruent.  I suppose ExecAssignProjectionInfo()  may be
calledwith tlist_lower_congruent == true only from  ExecInitResult(), ExecInitGroup() and ExecInitAgg().
 

3. ExecProject() does 'identity projection' if needed.

======
Performance measurement details.

The effect of this patch becomes greater as more columns exists.
The reduction of execution time was up to 45% for select * for a
partitioned table which has 30 columns, and 14% for single
column.

Exec time for non-partitioned (child) table seemes not to be
influenced by this patch.

The detail of the result follows. The result figures are the
averages for ten times run.

OS     CentOS6.3
CPU    Inter Core i7 965 @ 3.2GHz
Memory 6GB

shared_buffers=2GB  # No block read occurred on select.

### TEST FOR RESULT NODE
# CREATE TABLE parent (c01 int, c02 numeric,... cxx int);
# CREATE TABLE child () INHERITS(parent);
# INSERT INTO child (SELECT n, floor(random() * 10000),..
#                    FROM generate_series(0, 10000000 - 1) n);

30 columnsEXPLAIN ANALYZE SELECT * FROM parent;   original: 4868 ms    patched : 2691 ms (-45%)
EXPLAIN ANALYZE SELECT * FROM child;   original: 1252 ms   patched : 1125 ms (-10%)

15 columnsEXPLAIN ANALYZE SELECT * FROM parent;   original: 3785 ms    patched : 2685 ms (-29%)
EXPLAIN ANALYZE SELECT * FROM child0;   original: 1108 ms   patched : 1091 ms (-1.5%)

2 columnsEXPLAIN ANALYZE SELECT * FROM parent;   original: 3785 ms    patched : 2560 ms (-32%)
EXPLAIN ANALYZE SELECT * FROM child;   original: 1108 ms   patched :  973 ms (-12%)

1 columnEXPLAIN ANALYZE SELECT * FROM parent;   original: 2998 ms    patched : 2593 ms (-14%)
EXPLAIN ANALYZE SELECT * FROM child;   original: 1141 ms   patched :  969 ms (-15%)


### TEST FOR GROUP NODE
# CREATE TABLE tbl (c01 int, c02 numeric, c03 int);
# INSERT INTO tbl (SELECT n, floor(random() * 10000),..
#                  FROM generate_series(0, 10000000 - 1) n);

3 columnsEXPLAIN ANALYZE SELECT * FROM tbl GROUP BY c01, c02, c03;   original:  860 ms   patched :  775 ms (-9.9%)


Negative check - additional time to process identity check on planning.

# CREATE OR REPLACE FUNCTION test () RETURNS int AS $BODY$
DECLARE r int;
BEGIN r := 0; LOOP   PERFORM * FROM parenta LIMIT 1;   r := r + 1;   EXIT WHEN r > 100000; END LOOP; RETURN 1;
END;
$BODY$ LANGUAGE plpgsql;

EXPLAIN ANALYZE SELECT test()   original: 2695 ms   patched : 2622 ms (-3%)


regards,

-- 
Kyotaro Horiguchi
NTT Open Source Software Center
diff --git a/src/backend/executor/execQual.c b/src/backend/executor/execQual.c
index 56b106a..da1113f 100644
--- a/src/backend/executor/execQual.c
+++ b/src/backend/executor/execQual.c
@@ -5360,6 +5360,11 @@ ExecProject(ProjectionInfo *projInfo, ExprDoneCond *isDone)    if (isDone)        *isDone =
ExprSingleResult;
+    /* Simply return outer tuple for identity projection */
+    if (projInfo->pi_identity)
+        return econtext->ecxt_outertuple;
+
+    /*     * Clear any former contents of the result slot.  This makes it safe for     * us to use the slot's
Datum/isnullarrays as workspace. (Also, we can
 
diff --git a/src/backend/executor/execUtils.c b/src/backend/executor/execUtils.c
index 0bbd0d4..38d259a 100644
--- a/src/backend/executor/execUtils.c
+++ b/src/backend/executor/execUtils.c
@@ -485,6 +485,9 @@ ExecGetResultType(PlanState *planstate) * ensured that tuple slot has a descriptor matching the
tlist!) Note that * the given tlist should be a list of ExprState nodes, not Expr nodes. *
 
+ * This ProjectionInfo is marked as identity projection and passes through the
+ * outer tupleslot in ExecProject() when lower_congruent is true.
+ * * inputDesc can be NULL, but if it is not, we check to see whether simple * Vars in the tlist match the descriptor.
  It is important to provide * inputDesc for relation-scan plan nodes, as a cross check that the relation
 
@@ -494,6 +497,7 @@ ExecGetResultType(PlanState *planstate) */ProjectionInfo *ExecBuildProjectionInfo(List
*targetList,
+                        bool lower_congruent,                        ExprContext *econtext,
TupleTableSlot*slot,                        TupleDesc inputDesc)
 
@@ -511,6 +515,12 @@ ExecBuildProjectionInfo(List *targetList,    projInfo->pi_exprContext = econtext;
projInfo->pi_slot= slot;
 
+    projInfo->pi_identity = lower_congruent;
+
+    /* identity projection does not need further fields */
+    if (lower_congruent)
+        return projInfo;
+        /* since these are all int arrays, we need do just one palloc */    workspace = (int *) palloc(len * 3 *
sizeof(int));   projInfo->pi_varSlotOffsets = varSlotOffsets = workspace;
 
@@ -676,6 +686,7 @@ ExecAssignProjectionInfo(PlanState *planstate,{    planstate->ps_ProjInfo =
ExecBuildProjectionInfo(planstate->targetlist,
+                                planstate->tlist_lower_congruent,
planstate->ps_ExprContext,                               planstate->ps_ResultTupleSlot,
inputDesc);
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 38c7141..6e84aa7 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -1449,6 +1449,7 @@ ExecInitAgg(Agg *node, EState *estate, int eflags)    aggstate->ss.ps.qual = (List *)
ExecInitExpr((Expr*) node->plan.qual,                     (PlanState *) aggstate);
 
+    aggstate->ss.ps.tlist_lower_congruent = node->plan.tlist_lower_congruent;    /*     * initialize child nodes
@@ -1748,6 +1749,7 @@ ExecInitAgg(Agg *node, EState *estate, int eflags)        /* Set up projection info for
evaluation*/        peraggstate->evalproj = ExecBuildProjectionInfo(aggrefstate->args,
 
+                                                        false,
aggstate->tmpcontext,                                                       peraggstate->evalslot,
                                 NULL);
 
diff --git a/src/backend/executor/nodeGroup.c b/src/backend/executor/nodeGroup.c
index a8a1fe6..048c265 100644
--- a/src/backend/executor/nodeGroup.c
+++ b/src/backend/executor/nodeGroup.c
@@ -229,6 +229,7 @@ ExecInitGroup(Group *node, EState *estate, int eflags)    grpstate->ss.ps.qual = (List *)
ExecInitExpr((Expr*) node->plan.qual,                     (PlanState *) grpstate);
 
+    grpstate->ss.ps.tlist_lower_congruent = node->plan.tlist_lower_congruent;    /*     * initialize child nodes
diff --git a/src/backend/executor/nodeModifyTable.c b/src/backend/executor/nodeModifyTable.c
index 26a59d0..aa95004 100644
--- a/src/backend/executor/nodeModifyTable.c
+++ b/src/backend/executor/nodeModifyTable.c
@@ -1006,7 +1006,7 @@ ExecInitModifyTable(ModifyTable *node, EState *estate, int eflags)            rliststate = (List
*)ExecInitExpr((Expr *) rlist, &mtstate->ps);            resultRelInfo->ri_projectReturning =
 
-                ExecBuildProjectionInfo(rliststate, econtext, slot,
+                ExecBuildProjectionInfo(rliststate, false, econtext, slot,
resultRelInfo->ri_RelationDesc->rd_att);           resultRelInfo++;        }
 
diff --git a/src/backend/executor/nodeResult.c b/src/backend/executor/nodeResult.c
index b51efd8..cd6c8f2 100644
--- a/src/backend/executor/nodeResult.c
+++ b/src/backend/executor/nodeResult.c
@@ -246,6 +246,7 @@ ExecInitResult(Result *node, EState *estate, int eflags)                     (PlanState *)
resstate);   resstate->resconstantqual = ExecInitExpr((Expr *) node->resconstantqual,
         (PlanState *) resstate);
 
+    resstate->ps.tlist_lower_congruent = node->plan.tlist_lower_congruent;    /*     * initialize child nodes
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index d615b78..5612e93 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -866,6 +866,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)        slot = ExecInitExtraTupleSlot(estate);
     ExecSetSlotDescriptor(slot, tupDesc);        sstate->projLeft = ExecBuildProjectionInfo(lefttlist,
 
+                                                   false,                                                   NULL,
                                            slot,                                                   NULL);
 
@@ -874,6 +875,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)        slot = ExecInitExtraTupleSlot(estate);
     ExecSetSlotDescriptor(slot, tupDesc);        sstate->projRight = ExecBuildProjectionInfo(righttlist,
 
+                                                    false,
sstate->innerecontext,                                                   slot,
         NULL);
 
diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c
index ade9b57..dd557a8 100644
--- a/src/backend/executor/nodeWindowAgg.c
+++ b/src/backend/executor/nodeWindowAgg.c
@@ -1457,6 +1457,7 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags)    winstate->ss.ps.targetlist =
(List*)        ExecInitExpr((Expr *) node->plan.targetlist,                     (PlanState *) winstate);
 
+    winstate->ss.ps.tlist_lower_congruent = node->plan.tlist_lower_congruent;    /*     * WindowAgg nodes never have
quals,since they can only occur at the
 
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index ccd69fc..776ce64 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -26,7 +26,6 @@#include "utils/lsyscache.h"#include "utils/syscache.h"
-typedef struct{    Index        varno;            /* RT index of Var */
@@ -1184,6 +1183,7 @@ set_upper_references(PlannerInfo *root, Plan *plan, int rtoffset)    indexed_tlist
*subplan_itlist;   List       *output_targetlist;    ListCell   *l;
 
+    int         nmatch = 0;    subplan_itlist = build_tlist_index(subplan->targetlist);
@@ -1214,12 +1214,25 @@ set_upper_references(PlannerInfo *root, Plan *plan, int rtoffset)
     subplan_itlist,                                     OUTER_VAR,                                     rtoffset);
 
+        
+        if (IsA(newexpr, Var) && ((Var*)newexpr)->varattno == nmatch + 1)
+            nmatch++;
+        tle = flatCopyTargetEntry(tle);        tle->expr = (Expr *) newexpr;        output_targetlist =
lappend(output_targetlist,tle);    }
 
-    plan->targetlist = output_targetlist;
+    /*
+     * Directly refer to the lower tuple slot on projection if the all elements
+     * in target list exactly correspond to the ones in the lower tlist.
+     */
+    plan->tlist_lower_congruent  =
+        (nmatch == list_length(plan->targetlist) &&
+         nmatch == list_length(subplan->targetlist));
+
+    plan->targetlist = output_targetlist;
+     plan->qual = (List *)        fix_upper_expr(root,                       (Node *) plan->qual,
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 075bbe8..f705262 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -328,6 +328,7 @@ extern void ExecAssignResultType(PlanState *planstate, TupleDesc tupDesc);extern void
ExecAssignResultTypeFromTL(PlanState*planstate);extern TupleDesc ExecGetResultType(PlanState *planstate);extern
ProjectionInfo*ExecBuildProjectionInfo(List *targetList, 
+                        bool tlist_lower_congruent,                        ExprContext *econtext,
 TupleTableSlot *slot,                        TupleDesc inputDesc);
 
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index fec07b8..d3b0bc6 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -220,6 +220,7 @@ typedef struct ReturnSetInfo *        slot            slot to place projection result in *
itemIsDone       workspace array for ExecProject *        directMap        true if varOutputCols[] is an identity map
 
+ *        identity        true if this is an identity projection *        numSimpleVars    number of simple Vars found
inoriginal tlist *        varSlotOffsets    array indicating which slot each simple Var is from *        varNumbers
  array containing input attr numbers of simple Vars
 
@@ -237,6 +238,7 @@ typedef struct ProjectionInfo    TupleTableSlot *pi_slot;    ExprDoneCond *pi_itemIsDone;    bool
    pi_directMap;
 
+    bool        pi_identity;    int            pi_numSimpleVars;    int           *pi_varSlotOffsets;    int
*pi_varNumbers;
@@ -987,6 +989,7 @@ typedef struct PlanState     * subPlan list, which does not exist in the plan tree).     */    List
     *targetlist;        /* target list to be computed at this node */
 
+    bool        tlist_lower_congruent; /* target list is lower-congruent   */    List       *qual;            /*
implicitly-ANDedqual conditions */    struct PlanState *lefttree; /* input plan tree(s) */    struct PlanState
*righttree;
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index fb9a863..9e7729c 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -106,6 +106,7 @@ typedef struct Plan     * Common structural data for all Plan types.     */    List
*targetlist;       /* target list to be computed at this node */
 
+    bool        tlist_lower_congruent; /* target list is lower-congruent */    List       *qual;            /*
implicitly-ANDedqual conditions */    struct Plan *lefttree;        /* input plan tree(s) */    struct Plan *righttree;