博文

group by 语句从parsetree到portal全过程内存结构

已有 7536 次阅读 2010-5-5 11:09 |个人分类:postgresql|系统分类:科研笔记| group, postgresql, parsetree, plantree

上次写完了最简单的：
select catcode from pois;
Postgresql Executor 阶段内存结构，这回我们重新开始看看group by语句的内存结构，从parsetree，到plantree到portal执行中的所有相关的内存结构。
先定义我们的表，这回数据表稍微比原先的复杂些：
CREATE TABLE pois
(
uid integer not null,
name VARCHAR(128),
catcode VARCHAR(32) not null,
catname VARCHAR(32),
others VARCHAR(32)
);
执行 select count(*) from pois group by catcode;

1.parsetree
debug得到的parsetree list如下：
parsetree_list 0x08e39a5c
type T_List
length 1
head 0x08e39a48
data {...}
ptr_value 0x08e399bc
type T_SelectStmt
distinctClause 0x00000000
intoClause 0x00000000
targetList 0x08e3988c
type T_List
length 1
head 0x08e39878
data {...}
ptr_value 0x08e3984c
type T_ResTarget
name 0x00000000
indirection 0x00000000
val 0x08e39820
type T_FuncCall
funcname 0x08e39804
type T_List
length 1
head 0x08e397f0
data {...}
ptr_value 0x08e397dc
type T_String
val {...}
ival 149133256
str 0x08e397c8
int_value 149133276
oid_value 149133276
next 0x00000000
tail 0x08e397f0
args 0x00000000
agg_star true
agg_distinct false
func_variadic false
over 0x00000000
location 7
location 7
int_value 149133388
oid_value 149133388
next 0x00000000
tail 0x08e39878
fromClause 0x08e398fc
type T_List
length 1
head 0x08e398e8
data {...}
ptr_value 0x08e398bc
type T_RangeVar
catalogname 0x00000000
schemaname 0x00000000
relname 0x08e398a8
*relname 'p'
inhOpt INH_DEFAULT
istemp false
alias 0x00000000
location 21
int_value 149133500
oid_value 149133500
next 0x00000000
tail 0x08e398e8
whereClause 0x00000000
groupClause 0x08e399a0
type T_List
length 1
head 0x08e3998c
data {...}
ptr_value 0x08e3992c
type T_ColumnRef
fields 0x08e39970
type T_List
length 1
head 0x08e3995c
data {...}
ptr_value 0x08e39948
type T_String
val {...}
ival 149133592
str 0x08e39918
*str 'c'
int_value 149133640
oid_value 149133640
next 0x00000000
tail 0x08e3995c
location 35
int_value 149133612
oid_value 149133612
next 0x00000000
tail 0x08e3998c
havingClause 0x00000000
windowClause 0x00000000
withClause 0x00000000
valuesLists 0x00000000
sortClause 0x00000000
limitOffset 0x00000000
limitCount 0x00000000
lockingClause 0x00000000
op SETOP_NONE
all false
larg 0x00000000
rarg 0x00000000
int_value 149133756
oid_value 149133756
next 0x00000000
tail 0x08e39a48

parstree如下图：

其中：

主要是多了group by 子句，及targetlist中的funccall数据结构，注意到funccall指向的Value中count函数并没有包含参数catcode。

2.Querytree
这回我们先通过日志（关于如何查看postgresql的日志，请参考配置postgresql服务器以查看日志）看看query是什么样子：
DETAIL: {QUERY
:commandType 1
:querySource 0
:canSetTag true
:utilityStmt <>
:resultRelation 0
:intoClause <>
:hasAggs true
:hasWindowFuncs false
:hasSubLinks false
:hasDistinctOn false
:hasRecursive false
:cteList <>
:rtable (
{RTE
:alias <>
:eref
{ALIAS
:aliasname pois
:colnames ("uid" "name" "catcode" "catname" "others" "location")
}
:rtekind 0
:relid 17229
:inh true
:inFromCl true
:requiredPerms 2
:checkAsUser 0
:selectedCols (b 11)
:modifiedCols (b)
}
)
:jointree
{FROMEXPR
:fromlist (
{RANGETBLREF
:rtindex 1
}
)
:quals <>
}
:targetList (
{TARGETENTRY
:expr
{AGGREF
:aggfnoid 2803
:aggtype 20
:args <>
:agglevelsup 0
:aggstar true
:aggdistinct false
:location 7
}
:resno 1
:resname count
:ressortgroupref 0
:resorigtbl 0
:resorigcol 0
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 3
:vartype 1043
:vartypmod 36
:varlevelsup 0
:varnoold 1
:varoattno 3
:location 35
}
:resno 2
:resname <>
:ressortgroupref 1
:resorigtbl 0
:resorigcol 0
:resjunk true
}
)
:returningList <>
:groupClause (
{SORTGROUPCLAUSE
:tleSortGroupRef 1
:eqop 98
:sortop 664
:nulls_first false
}
)
:havingQual <>
:windowClause <>
:distinctClause <>
:sortClause <>
:limitOffset <>
:limitCount <>
:rowMarks <>
:setOperations <>
}
值得注意的是groupclause中的eqop 98 和sortop 664 项。

从select * from pg_operator where oid = 98; 可以查到：
98;"=";11;10;"b";TRUE;TRUE;25;25;16;98;531;"texteq";"eqsel";"eqjoinsel"
可见该操作符对字符串（我们的catecode就属于该类）运算等于操作
从select * from pg_operator where oid = 664; 可以查到：
664;"<";11;10;"b";FALSE;FALSE;25;25;16;666;667;"text_lt";"scalarltsel";"scalarltjoinsel"
可见，用于排序的操作符为<，且对text类型的数据进行排序。

另外一个参数是targetlist中aggfnoid 2803
mydb=# select oid,proname from pg_proc where proname = 'count';
oid | proname
------+---------
2803 | count
2147 | count
(2 rows)
发现2803为count函数。
另外一个问题是在parsetree中我们只有count(*)一个target，为什么到了querytree里变成了两个了,实际上单单解析parsetree的targetlist只得到第一个，接着解析group by的时候才增加的第2个。可以通过如下调用明白其中的道理：
postgresql Thread [C/C++ Attach to Application]
gdb Debugger (5/4/10 3:42 PM) (Suspended)
Thread [1] (Suspended)
13 findTargetlistEntrySQL99() /home/postgres/develop/.../src/backend/parser/parse_clause.c:1423
12 transformGroupClause() /home/postgres/develop/.../src/backend/parser/parse_clause.c:1457
11 transformSelectStmt() /home/postgres/develop/.../src/backend/parser/analyze.c:838
10 transformStmt() /home/postgres/develop/.../src/backend/parser/analyze.c:190 0x08127e3f
9 parse_analyze() /home/postgres/develop/.../src/backend/parser/analyze.c:93 0x0812a32f
8 pg_analyze_and_rewrite() /home/postgres/develop/.../src/backend/tcop/postgres.c:606
7 exec_simple_query() /home/postgres/develop/.../src/backend/tcop/postgres.c:918
6 PostgresMain() /home/postgres/develop/.../src/backend/tcop/postgres.c:3617 0x0827a75e
5 BackendRun() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:3449
4 BackendStartup() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:3063
3 ServerLoop() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:1387
2 PostmasterMain() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:1040
1 main() /home/postgres/develop/.../src/backend/main/main.c:188
在findTargetlistEntrySQL99（）中：
static TargetEntry *findTargetlistEntrySQL99(ParseState *pstate, Node *node, List **tlist){
TargetEntry *target_result;
ListCell *tl;
Node *expr;
/*
* Convert the untransformed node to a transformed expression, and search
* for a match in the tlist. NOTE: it doesn't really matter whether there
* is more than one match. Also, we are willing to match an existing
* resjunk target here, though the SQL92 cases above must ignore resjunk
* targets.
*/
expr = transformExpr(pstate, node);
foreach(tl, *tlist) {
TargetEntry *tle = (TargetEntry *) lfirst(tl);
if (equal(expr, tle->expr))
return tle;
}
/*
* If no matches, construct a new target entry which is appended to the
* end of the target list. This target is given resjunk = TRUE so that it
* will not be projected into the final tuple.
*/
target_result = transformTargetEntry(pstate, node, expr, NULL, true); //就是这里实现的
*tlist = lappend(*tlist, target_result);
return target_result;
}
本段小结，我们画出我们的query tree如下：

此图中，我们注意到第2项targetentry的ressortgroupref =1和resjunk = true。
关于ressortgroupref ，注释做了很好的说明：
Index ressortgroupref;/* nonzero if referenced by a sort/group clause */
注意Index ressortgroupref=1 最终赋值为1（初始化为0）是在如下assignSortGroupRef() 函数中，对应的堆栈为：
postgresql Thread [C/C++ Attach to Application]
gdb Debugger (5/4/10 4:46 PM) (Suspended)
Thread [1] (Suspended)
14 assignSortGroupRef() /home/postgres/develop/.../src/backend/parser/parse_clause.c:2091
13 addTargetToGroupList() /home/postgres/develop/.../src/backend/parser/parse_clause.c:2062
12 transformGroupClause() /home/postgres/develop/.../src/backend/parser/parse_clause.c:1497
11 transformSelectStmt() /home/postgres/develop/.../src/backend/parser/analyze.c:838
10 transformStmt() /home/postgres/develop/.../src/backend/parser/analyze.c:190 0x08127e3f
9 parse_analyze() /home/postgres/develop/.../src/backend/parser/analyze.c:93 0x0812a32f
8 pg_analyze_and_rewrite() /home/postgres/develop/.../src/backend/tcop/postgres.c:606
7 exec_simple_query() /home/postgres/develop/.../src/backend/tcop/postgres.c:918
6 PostgresMain() /home/postgres/develop/.../src/backend/tcop/postgres.c:3617 0x0827a75e
5 BackendRun() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:3449
4 BackendStartup() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:3063
3 ServerLoop() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:1387
2 PostmasterMain() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:1040
1 main() /home/postgres/develop/.../src/backend/main/main.c:188 0x081e7ee7
关于resjunk = true，即最终不发送到客户端。
另外，rewritten parse tree:阶段没有对我们的parse tree做任何修改，因为我们没有针对view的数据表，所以没有重写规则。

3.Plantree
先看日志：
STATEMENT: select count(*) from pois group by catcode;
LOG: plan:
DETAIL: {PLANNEDSTMT
:commandType 1
:canSetTag true
:planTree
{AGG
:startup_cost 19.07
:total_cost 19.11
:plan_rows 3
:plan_width 2
:targetlist (
{TARGETENTRY
:expr
{AGGREF
:aggfnoid 2803
:aggtype 20
:args <>
:agglevelsup 0
:aggstar true
:aggdistinct false
:location 7
}
:resno 1
:resname count
:ressortgroupref 0
:resorigtbl 0
:resorigcol 0
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 3
:vartype 1043
:vartypmod 36
:varlevelsup 0
:varnoold 1
:varoattno 3
:location 35
}
:resno 2
:resname <>
:ressortgroupref 1
:resorigtbl 0
:resorigcol 0
:resjunk true
}
)
:qual <>
:lefttree
{SEQSCAN
:startup_cost 0.00
:total_cost 16.05
:plan_rows 605
:plan_width 2
:targetlist (
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
:location -1
}
:resno 1
:resname <>
:ressortgroupref 0
:resorigtbl 0
:resorigcol 0
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 2
:vartype 1043
:vartypmod 132
:varlevelsup 0
:varnoold 1
:varoattno 2
:location -1
}
:resno 2
:resname <>
:ressortgroupref 0
:resorigtbl 0
:resorigcol 0
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 3
:vartype 1043
:vartypmod 36
:varlevelsup 0
:varnoold 1
:varoattno 3
:location -1
}
:resno 3
:resname <>
:ressortgroupref 0
:resorigtbl 0
:resorigcol 0
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 4
:vartype 1043
:vartypmod 36
:varlevelsup 0
:varnoold 1
:varoattno 4
:location -1
}
:resno 4
:resname <>
:ressortgroupref 0
:resorigtbl 0
:resorigcol 0
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 5
:vartype 1043
:vartypmod 36
:varlevelsup 0
:varnoold 1
:varoattno 5
:location -1
}
:resno 5
:resname <>
:ressortgroupref 0
:resorigtbl 0
:resorigcol 0
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 6
:vartype 16394
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 6
:location -1
}
:resno 6
:resname <>
:ressortgroupref 0
:resorigtbl 0
:resorigcol 0
:resjunk false
}
)
:qual <>
:lefttree <>
:righttree <>
:initPlan <>
:extParam (b)
:allParam (b)
:scanrelid 1
}
:righttree <>
:initPlan <>
:extParam (b)
:allParam (b)
:aggstrategy 2
:numCols 1
:grpColIdx 3
:grpOperators 98
:numGroups 3
}
:rtable (
{RTE
:alias <>
:eref
{ALIAS
:aliasname pois
:colnames ("uid" "name" "catcode" "catname" "others" "location")
}
:rtekind 0
:relid 17229
:inh false
:inFromCl true
:requiredPerms 2
:checkAsUser 0
:selectedCols (b 11)
:modifiedCols (b)
}
)
:resultRelations <>
:utilityStmt <>
:intoClause <>
:subplans <>
:rewindPlanIDs (b)
:returningLists <>
:rowMarks <>
:relationOids (o 17229)
:invalItems <>
:nParamExec 0
}
先根据这些信息生成plantree图，如下：

对于图中我们发现了几个有意思的事情，一个是Agg中已经知道了最终结果有3个group，即Long numGroups=3这是怎知道的呢？
另外一个有意思的事情是Agg中的AggStrategy Aggstrategy=AGG_HASHED，这个hash策略是什么意思呢？
我们先来看第一个。numGroups是在get_variable_numdistinct() 中计算的。
调用堆栈为：
Thread [1] (Suspended)
16 get_variable_numdistinct() /home/postgres/develop/.../src/backend/utils/adt/selfuncs.c:4227 0x082e2036
15 add_unique_group_var() /home/postgres/develop/.../src/backend/utils/adt/selfuncs.c:2831 0x082e2c2c
14 estimate_num_groups() /home/postgres/develop/.../src/backend/utils/adt/selfuncs.c:2979 0x082e2d79
13 query_planner() /home/postgres/develop/.../src/backend/optimizer/plan/planmain.c:276 0x0821e529
12 grouping_planner() /home/postgres/develop/.../src/backend/optimizer/plan/planner.c:1006 0x0821fc23
11 subquery_planner() /home/postgres/develop/.../src/backend/optimizer/plan/planner.c:481 0x082219af
10 standard_planner() /home/postgres/develop/.../src/backend/optimizer/plan/planner.c:190 0x08221f5b
9 pg_plan_query() /home/postgres/develop/.../src/backend/tcop/postgres.c:697 0x0827885e
8 pg_plan_queries() /home/postgres/develop/.../src/backend/tcop/postgres.c:756 0x08278963
7 exec_simple_query() /home/postgres/develop/.../src/backend/tcop/postgres.c:921 0x08278df2
6 PostgresMain() /home/postgres/develop/.../src/backend/tcop/postgres.c:3617 0x0827a75e
5 BackendRun() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:3449 0x0824440d
4 BackendStartup() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:3063 0x0824440d
3 ServerLoop() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:1387 0x0824440d
2 PostmasterMain() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:1040 0x08246f18
1 main() /home/postgres/develop/.../src/backend/main/main.c:188 0x081e7ee7
我们来看看这个函数：
double get_variable_numdistinct(VariableStatData *vardata)
{
double stadistinct;
double ntuples;

/*
* Determine the stadistinct value to use. There are cases where we can
* get an estimate even without a pg_statistic entry, or can get a better
* value than is in pg_statistic.
*/
if (HeapTupleIsValid(vardata->statsTuple))
{
/* Use the pg_statistic entry */
Form_pg_statistic stats;

stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
stadistinct = stats->stadistinct;
}
else if (vardata->vartype == BOOLOID)
{
/*
* Special-case boolean columns: presumably, two distinct values.
*
* Are there any other datatypes we should wire in special estimates
* for?
*/
stadistinct = 2.0;
}
else
{
/*
* We don't keep statistics for system columns, but in some cases we
* can infer distinctness anyway.
*/
if (vardata->var && IsA(vardata->var, Var))
{
switch (((Var *) vardata->var)->varattno)
{
case ObjectIdAttributeNumber:
case SelfItemPointerAttributeNumber:
stadistinct = -1.0; /* unique */
break;
case TableOidAttributeNumber:
stadistinct = 1.0; /* only 1 value */
break;
default:
stadistinct = 0.0; /* means "unknown" */
break;
}
}
else
stadistinct = 0.0; /* means "unknown" */

/*
* XXX consider using estimate_num_groups on expressions?
*/
}

/*
* If there is a unique index for the variable, assume it is unique no
* matter what pg_statistic says; the statistics could be out of date, or
* we might have found a partial unique index that proves the var is
* unique for this query.
*/
if (vardata->isunique)
stadistinct = -1.0;

/*
* If we had an absolute estimate, use that.
*/
if (stadistinct > 0.0)
return stadistinct;

/*
* Otherwise we need to get the relation size; punt if not available.
*/
if (vardata->rel == NULL)
return DEFAULT_NUM_DISTINCT;
ntuples = vardata->rel->tuples;
if (ntuples <= 0.0)
return DEFAULT_NUM_DISTINCT;

/*
* If we had a relative estimate, use that.
*/
if (stadistinct < 0.0)
return floor((-stadistinct * ntuples) + 0.5);

/*
* With no data, estimate ndistinct = ntuples if the table is small, else
* use default.
*/
if (ntuples < DEFAULT_NUM_DISTINCT)
return ntuples;

return DEFAULT_NUM_DISTINCT;
}
基本思想是使用pg_statistic.stadistinct 来设置 Agg.numGroups。
我们 select starelid,staattnum,stadistinct from pg_statistic where starelid = 17229;看看：
starelid | staattnum | stadistinct
----------+-----------+-------------
17229 | 1 | -1
17229 | 2 | -0.945455
17229 | 3 | 3
17229 | 4 | 3
17229 | 5 | 1
17229 | 6 | -1
(6 rows)
发现catcode（对应第3项）确实只有3个distinct value。
接下来我们看第二个问题：Agg中的AggStrategy Aggstrategy=AGG_HASHED？
这个主要是在函数：
choose_hashed_grouping(root,
tuple_fraction, limit_tuples,
cheapest_path, sorted_path,
dNumGroups, &agg_counts);
中计算的，主要是比较seq+hash 和seq+sort的代价，如果seq+hash代价小，则选择seq+hash 。
该阶段中最后通过：
result_plan = (Plan *) make_agg(root,
tlist,
(List *) parse->havingQual,
AGG_HASHED,
numGroupCols,
groupColIdx,
extract_grouping_ops(parse->groupClause),
numGroups,
agg_counts.numAggs,
result_plan);
生成最终的agg plan，并把leftchild赋值seq对应的plan。

另这里上传了一张包含plantree和解析成plantree过程中用到的数据结构图。

4.Portal中用到的数据结构
走到这里了，我们才发现，原来这里的数据结构最复杂。
先把我们的图摆上：

更清晰的大图可以从这里下载。

图中我们发现几个有趣的问题：
第1个问题：
AggState中的
FmgrInfo *eqfunctions=67
FmgrInfo *hashfunctions=400
这两个字段是什么意思？我们来查查:
mydb=# select oid,proname from pg_proc where oid = 400 or oid= 67;
oid | proname
-----+----------
67 | texteq
400 | hashtext
(2 rows)
可见
eqfunction= 67主要是实现了group by中对catcode 实施“=”操作符具体采用的函数。
hashfunctions=400则表明了需要使用的hash函数。

对这两项的赋值是在：
void
execTuplesHashPrepare(int numCols,
Oid *eqOperators,
FmgrInfo **eqFunctions,
FmgrInfo **hashFunctions)
实现的。
调用堆栈为：
Thread [1] (Suspended)
13 execTuplesHashPrepare() /home/postgres/develop/.../src/backend/executor/execGrouping.c:239
12 ExecInitAgg() /home/postgres/develop/.../src/backend/executor/nodeAgg.c:1316 0x081c94ed
11 ExecInitNode() /home/postgres/develop/.../src/backend/executor/execProcnode.c:260 0x081bbd01
10 InitPlan() /home/postgres/develop/.../src/backend/executor/execMain.c:835 0x081ba116
9 standard_ExecutorStart() /home/postgres/develop/.../src/backend/executor/execMain.c:219 0x081bb0af
8 PortalStart() /home/postgres/develop/.../src/backend/tcop/pquery.c:539 0x0827e3b3
7 exec_simple_query() /home/postgres/develop/.../src/backend/tcop/postgres.c:953 0x08278c0e
6 PostgresMain() /home/postgres/develop/.../src/backend/tcop/postgres.c:3615 0x0827a75e
5 BackendRun() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:3449 0x0824440d
4 BackendStartup() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:3063 0x0824440d
3 ServerLoop() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:1387 0x0824440d
2 PostmasterMain() /home/postgres/develop/.../src/backend/postmaster/postmaster.c:1040 0x08246f18
1 main() /home/postgres/develop/.../src/backend/main/main.c:188 0x081e7ee7

第2个有意思的问题是关于 agg中的 type=20
我们通过：
mydb=# select typname,typlen,typinput,typoutput from pg_type where oid = 20;
typname | typlen | typinput | typoutput
---------+--------+----------+-----------
int8 | 8 | int8in | int8out
(1 row)
来看看。

第3个有意思的问题是关于AggStatePerAggData.transfn 中的 fn_oid=1219
我们通过
mydb=# select proname from pg_proc where oid= 1219;
proname
---------
int8inc
(1 row)
知道该函数为递增函数。详细实现在/backend/utils/adt/int8.c中。