1、一个分区表的问题
假如我们有一个分区表叫parent，里面只有一列数据，int类型的id。然后它是由三个分区表组成的--child1、child2和child3。他们分别是id从[0, 250)，[250,500)以及[-10000,0)。
当我执行这个命令的时候：SELECT * FROM parent ORDER BY id;数据库会有这样的执行方式：
这里我child1和child2都加了索引，但是child3没有。所以是child3上面先进行一个排序，然后index扫描child1和child2，然后再用一个merge append节点来把它们的结果汇集起来。
但是不对啊。我们的分区表是分段分区的。child1里面所有的东西一定都是小于child2的。child3里面的东西一定都是小于其他两个分区的。本来里面的都是已经排好序了（index scan其实就是一种排序），为什么最后需要用merge append对已经排好序的结果再排一次呢？merge append本身是使用priority tree来实现的，还是有点开销的。这里我们应该可以用一个简单的append节点来代替。
2、让我们来修改内核吧
首先我们要注意到这个问题是在排序的才会产生的。那么自然而然，我们就需要想办法在优化器中识别出这个状态。
什么样的情况可以增加我们想要的优化呢？我们要从一个分区表里面去排序地选择东西。这个分区表呢，是一个range partition table，而且它的每一个分区都没有子分区（因为那样实现起来太麻烦了）。
那么我们在优化器中该如何判断呢？首先应该想到的是PartitionBoundInfo这个结构体。它描述了分区表中每一个分区的上下限的关系，还有这个分区表的分区类型。
那么应该从哪儿下手呢？对源代码进行一点点搜索，你会发现这个函数：generate_mergeappend_paths。毕竟我们要把一个merge append的node变成一个append的node，从这个函数下手应该是合理的。
let's see some codes.
static void
generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
List *live_childrels,
List *all_child_pathkeys,
List *partitioned_rels)
{
ListCell *lcp;
bool is_range_partitioned = false;
List *partition_keys = NIL;
List *partition_keys_desc = NIL;
PartitionBoundInfo bound_info = rel->boundinfo;
if (bound_info->strategy == PARTITION_STRATEGY_RANGE)
{
is_range_partitioned = true;
}
if (is_range_partitioned == true)
{
partition_keys = generate_partition_pathkeys(root, rel, ForwardScanDirection);
partition_keys_desc = generate_partition_pathkeys(root, rel, BackwardScanDirection);
}
foreach(lcp, all_child_pathkeys)
{
List *pathkeys = (List *) lfirst(lcp);
List *startup_subpaths = NIL;
List *total_subpaths = NIL;
bool startup_neq_total = false;
ListCell *lcr;
bool try_append = false;
bool try_append_desc = false;
if (is_range_partitioned)
{
if (pathkeys_contained_in(pathkeys, partition_keys))
{
try_append = true;
}
if (pathkeys_contained_in(pathkeys, partition_keys_desc))
{
try_append_desc = true;
}
}
/* Select the child paths for this ordering... */
foreach(lcr, live_childrels)
{
RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr);
Path *cheapest_startup,
*cheapest_total;
/* Locate the right paths, if they are available. */
cheapest_startup =
get_cheapest_path_for_pathkeys(childrel->pathlist,
pathkeys,
NULL,
STARTUP_COST,
false);
cheapest_total =
get_cheapest_path_for_pathkeys(childrel->pathlist,
pathkeys,
NULL,
TOTAL_COST,
false);
/*
* If we can't find any paths with the right order just use the
* cheapest-total path; we'll have to sort it later.
*/
if (cheapest_startup == NULL || cheapest_total == NULL)
{
cheapest_startup = cheapest_total =
childrel->cheapest_total_path;
/* Assert we do have an unparameterized path for this child */
Assert(cheapest_total->param_info == NULL);
}
/*
* Notice whether we actually have different paths for the
* "cheapest" and "total" cases; frequently there will be no point
* in two create_merge_append_path() calls.
*/
if (cheapest_startup != cheapest_total)
startup_neq_total = true;
accumulate_append_subpath(cheapest_startup,
&startup_subpaths, NULL);
accumulate_append_subpath(cheapest_total,
&total_subpaths, NULL);
}
//这里先不管desc的情况了。先让程序能够跑起来。
if (try_append || try_append_desc)
{
add_path(rel, (Path *)create_append_path(root,
rel,
startup_subpaths,
NIL,
pathkeys,
NULL,
,
false,
partitioned_rels,
-1 ));
if (startup_neq_total)
{
add_path(rel, (Path *)create_append_path(root,
rel,
total_subpaths,
NIL,
pathkeys,
NULL,
,
false,
partitioned_rels,
-1));
}
} else
{
/* ... and build the MergeAppend paths */
add_path(rel, (Path *) create_merge_append_path(root,
rel,
startup_subpaths,
pathkeys,
NULL,
partitioned_rels));
if (startup_neq_total)
add_path(rel, (Path *) create_merge_append_path(root,
rel,
total_subpaths,
pathkeys,
NULL,
partitioned_rels));
}
}
}这个代码实际上是我在原有的基础上改的，改动也不是很多。大家可以自己下载源代码来进行比对。
首先是这几个部分：
PartitionBoundInfo bound_info = rel->boundinfo;
if (bound_info->strategy == PARTITION_STRATEGY_RANGE)
{
is_range_partitioned = true;
}
if (is_range_partitioned == true)
{
partition_keys = generate_partition_pathkeys(root, rel, ForwardScanDirection);
partition_keys_desc = generate_partition_pathkeys(root, rel, BackwardScanDirection);
}
这个是判断它是不是一个range partition table。如果是的话呢，就按照正反两个方向来生成两个需要对这个表排序的pathkey。在PostgreSQL中，pathkey是用来描述排序的变量。 generate_partition_pathkeys我是这样写的：
List *
generate_partition_pathkeys(PlannerInfo *root, RelOptInfo *parent_rel, ScanDirection direction)
{
PartitionScheme part_scheme = parent_rel->part_scheme;
PartitionBoundInfo bound_info = parent_rel->boundinfo;
if (part_scheme->strategy != PARTITION_STRATEGY_RANGE || partition_bound_has_default(bound_info))
{
// 我们只考虑range的情况。
//如果分区有默认分区的话，就需要merge append了。
return NIL;
}
List *result = NIL;
for (int i=; i<part_scheme->partnatts; i++)
{
PathKey *key;
Expr *expr = linitial(parent_rel->partexprs[i]);
key = make_pathkey_from_sortinfo(root,
expr,
NULL,
part_scheme->partopfamily[i],
part_scheme->partopcintype[i],
part_scheme->partcollation[i],
ScanDirectionIsBackward(direction),
ScanDirectionIsBackward(direction),
,
parent_rel->relids,
false
);
result = lappend(result, key);
}
return result;
}这个还是很好理解的。我们进入到了merge append了，不管怎么样我们总是要排序的。既然要排序，那就先把pathkey算出来吧。到时候可以用来做判断。
然后的程序就很简单了。我们对每一个subrelation去得到它的最佳的path。注意到这里的path有两个（对于每一个relation来说是cheapest_startup和cheapest_total） 。这个和最终优化器去算代价是有关系的。然后如果是我们需要的情况，那就用生成append path，然后加入到parent的pathlist中去。
我们的修改之旅到这里并没有结束。因为如果只是这样修改的话，那么结果会是这样的：
对！最上面突然出现了一个sort节点。这是append本身是不支持排序的。所以如果要用append的话，我们是需要修改append相关函数的。
首先是 create_append_path。这个很简单，只需要在输入的参数里面加上其他函数弄好的pathkeys，然后设置上pathnode->path.pathkeys = pathkeys;本来是pathnode->path.pathkeys = NIL;的。
然后在中检测一下我们是不是有一个pathkey。如果有，那就说明是需要排序的，然后就很简单地做一个排序就行了。
static Plan *
create_append_plan(PlannerInfo *root, AppendPath *best_path)
{
//Append *plan;
Append *node = makeNode(Append);
Plan *plan = &node->plan;
List *pathkeys = best_path->path.pathkeys;
plan->qual = NIL;
plan->lefttree = NULL;
plan->righttree = NULL;
List *tlist = build_path_tlist(root, &best_path->path);
plan->targetlist = tlist;
List *subplans = NIL;
ListCell *subpaths;
RelOptInfo *rel = best_path->path.parent;
PartitionPruneInfo *partpruneinfo = NULL;
bool append_sort = false;
int numCols;
int numsortkeys;
AttrNumber *sortColIdx = NULL;
Oid *sortOperators = NULL;
Oid *collations = NULL;
bool *nullFirst = NULL;
if (pathkeys != NIL)
{
(void)prepare_sort_from_pathkeys(plan,
pathkeys,
best_path->path.parent->relids,
NULL,
true,
&numsortkeys,
&sortColIdx,
&sortOperators,
&collations,
&nullFirst);
}
/*
* The subpaths list could be empty, if every child was proven empty by
* constraint exclusion. In that case generate a dummy plan that returns
* no rows.
*
* Note that an AppendPath with no members is also generated in certain
* cases where there was no appending construct at all, but we know the
* relation is empty (see set_dummy_rel_pathlist).
*/
if (best_path->subpaths == NIL)
{
/* Generate a Result plan with constant-FALSE gating qual */
Plan *plan;
plan = (Plan *)make_result(tlist,
(Node *)list_make1(makeBoolConst(false,
false)),
NULL);
copy_generic_path_info(plan, (Path *)best_path);
return plan;
}
/* Build the plan for each child */
foreach (subpaths, best_path->subpaths)
{
Path *subpath = (Path *)lfirst(subpaths);
Plan *subplan;
int new_numsortkeys;
AttrNumber *new_sortColIdx;
Oid *new_sortOperators;
Oid *new_collations;
bool *New_nullFirst;
/* Must insist that all children return the same tlist */
subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
if (pathkeys != NIL)
{
subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
subpath->parent->relids,
sortColIdx,
false,
&new_numsortkeys,
&new_sortColIdx,
&new_sortOperators,
&new_collations,
&New_nullFirst);
if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
{
Sort *sort = make_sort(subplan, new_numsortkeys,
new_sortColIdx, new_sortOperators,
new_collations, New_nullFirst);
subplan = (Plan *)sort;
}
}
subplans = lappend(subplans, subplan);
}然后最后的结果就会变成这样：
这里最上面的cost为0，主要是我太懒了没有更新cost计算的事情。
3、总结
这篇文章主要是我读了：
https://www.postgresql.org/message-id/flat/CAKJS1f-hAqhPLRk_RaSFTgYxd=Tz5hA7kQ2h4-DhJufQk8TGuw@mail.gmail.com这里的讨论而写的。周末花了一天的时间看了前三个版本的实现，然后花了一天来简单实现一下。当然，写这个最主要的原因是我勇者斗恶龙11打通关了，周末没事做。偶尔看看技术文章挺好的。
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/31537575/viewspace-3128942/ ，如需转载，请注明出处，否则将追究法律责任。
