为什么须要窗口函数？
Window是一个罕用且重要的性能，PolarDB-X作为一款分布式数据库，天然也反对了窗口函数。对于业务开发来讲，其能够大大简化业务SQL的设计，比方分组排序功能，如果反对窗口函数，则只需应用排序函数即可，例子如下。 例：我当初有一张表，蕴含学生姓名，学生班级，学生问题，当初请你帮我写一条SQL，实现对每个班级内的同学进行排名的需要？ 有窗口函数时：
SELECT
student_name,
class_name,
score,
DENSE_RANK() OVER (PARTITION BY class_name ORDER BY score DESC) AS rank
FROM student_scores
ORDER BY class_name, rank ASC;无窗口函数时：就须要写比较复杂的SQL，感兴趣的同学能够自行尝试或者网上搜寻一下如何写这样的SQL（或者这也可能在面试中被问到:)）。
窗口函数是什么？
实质上window是一种aggregation，然而不同于agg的是，agg要进行聚合的是该分组内的所有记录，每个分组也只会输入一行记录，而window则能够管制对于每一行来讲，想要聚合的记录到底是哪些，当然这种管制也是通过规定进行束缚的，输入的记录行数等于输出的记录行数，上面贴了一张图，应该还比较清楚:)。
上图中的partitioin by与大家常写的SQL中的group by根本等价，比拟容易了解，不再赘述。咱们来开展介绍一下frame是个什么样的货色，如前所述，frame管制的是进行partition分区后，在该partition分区内，该行应该抉择哪些行进行聚合运算。 具体来讲，咱们是通过between和and来指定咱们心愿框定向前和向后的哪些行进行聚合运算的，而指定形式也无非是行数，以后行以及不做限度，据此咱们能够将frame分为四类，如下图所示。
实际上，将frame划分为不同的类型，能够领导咱们依据不同的frame类型进行不同的优化，其次要目标是为了防止反复计算。比方对于unbounded preceding and unbounded following类型，显然咱们只需对该分组进行一次计算即可，该分组的后续记录可间接应用该后果。而对于sliding frame则不能这样解决，其解决要简单一些，对于每一行，咱们都须要找出该行所对应的框定行，而后对这些行进行聚合运算。 进一步的，frame能够分为两类，row模式和range模式，row模式寻找边界的根据是行数，而range模式的根据则是值。咱们拿一个例子进去，看下row模式和range模式的区别吧。如下图所示，其frame定义均为between current row and current row，然而在row模式和range模式下，其选中的行并不相同。
在上述的介绍中，咱们没有介绍每个分区内的order by字段，其实一个残缺的window的定义蕴含partition by, order by和frame specification。但order by了解起来也比较简单，顾名思义，order by即指定对于每个分区内的行，该当依照什么程序进行排序，frame中的向前向后多少行也是基于该排序后的汇合。 Q：抛一个问题，有趣味的敌人能够思考一下，向前向后的行肯定是间断的，这是为什么呢？比方range模式下如何保障这一点？
窗口函数的设计与实现
窗口函数可能不是那么容易了解，所以咱们在后面进行了比拟多的介绍，当初咱们终于来到了设计与实现局部。
如何执行窗口函数？
咱们以一条SQL为例吧，如下所示，partition字段为c1，排序字段为c2，frame定义为rows between 1 preceding and 1 following。
select
c1,
c2,
avg(c2) over (
partition by c1
order by c2
rows between 1 preceding and 1 following
)
from t;首先，关键点1，c1字段雷同的记录该当被搁置在一起（shuffle）；其次，关键点2，当咱们对c1 + c2进行排序时，即可辨认每行属于哪个分区以及该行的相干行是哪些。据此咱们来开展介绍一下优化器和执行器的设计。
优化器
咱们能够把优化器中的相干规定分为生成规定与优化规定，所谓生成规定，即用来确保window可能被正确的辨认和转换，而优化规定则是为了优化某些场景下带有窗口函数的SQL。
生成规定
生成规定次要蕴含三条，project如何生成logical window (ProjectToLogicalProjectAndWindowRule )，logical window如何转换为执行时所需的sort window (LogicalWindowToSortWindowRule )，如何让sort window并行起来 (MppSortWindowConvertRule )。 在project如何生成logical window 中，并没有太多要聊的货色，如何辨认和转换能够间接查看相干源码，咱们次要来聊一个有意思的问题，还是拿个SQL来举例子吧，如下。
select
c1,
c2,
avg(c2) over (
partition by c1
order by c2
rows between 1 preceding and 1 following
),
sum(c3) over (
partition by c1
order by c2
rows between 1 preceding and 1 following
)
from t;Q：上述SQL应该生成几个window？ A：生成两个是最简略的，但其window的定义是雷同的，所以现实状况下应该只须要生成一个window，window外面蕴含avg和sum函数就好了。 代码如下所示，如果这两个window定义雷同时，会被压到一个window中。
final List<Pair<RexWindow, Set<Integer>>> windowToIndices = new ArrayList<>();
for (int i = 0; i < exprs.size(); ++i) {
final RexNode expr = exprs.get(i);
if (expr instanceof RexOver) {
final RexOver over = (RexOver) expr;
// If we can found an existing cohort which satisfies the two conditions,
// we will add this RexOver into that cohort
boolean isFound = false;
for (Pair<RexWindow, Set<Integer>> pair : windowToIndices) {
if (pair.left.equals(over.getWindow())) {
pair.right.add(i);
isFound = true;
break;
}
}
// This RexOver cannot be added into any existing cohort
if (!isFound) {
final Set<Integer> newSet = Sets.newHashSet(i);
windowToIndices.add(Pair.of(over.getWindow(), newSet));
}
}
}Q：其实这外面有可供进一步优化的场景，实质上优化器和执行器须要更严密的配合，感兴趣的敌人能够debug一下。 接下来咱们来看一下logical window如何转换为执行时所需的sort window。外围在于咱们须要将sort的属性退出到window中，因为logical window自身是没有排序属性的，这里咱们须要window的输出是依照partition column + sort column有序的，同时sort window也领有此程序。
RelCollation relCollation = RelCollations.EMPTY;
if (groupSets.cardinality() + orderKeys.size() > 0) {
relCollation = CBOUtil.createRelCollation(sortFields, orderKeys);
}
// change trait set of input
RelNode newInput = convert(input, input.getTraitSet().replace(DrdsConvention.INSTANCE).replace(relCollation));
// change trait set of window
SortWindow newWindow =
SortWindow.create(
window.getTraitSet().replace(DrdsConvention.INSTANCE).replace(relCollation),
newInput,
window.getConstants(),
window.groups,
window.getRowType(),
window.getFixedCost()
);仔细的敌人会发现，咱们在批改排序属性之外，还将window的convention批改为了DrdsConvention ，感兴趣的敌人能够思考一下为什么？此外，咱们退出了排序属性之后，如果其input自身并不满足排序属性的要求时，是在哪里插入排序的算子的呢，答案是DrdsConvetion.enforce办法，相干代码如下 。
RelCollation toCollation = required.getTrait(RelCollationTraitDef.INSTANCE);
RelDistribution toDistribution = required.getTrait(RelDistributionTraitDef.INSTANCE);
if (!RuleUtils.satisfyCollation(toCollation, input)) {
RelTraitSet emptyTraitSet = input.getCluster().getPlanner().emptyTraitSet();
MemSort memSort = MemSort.create(
emptyTraitSet.replace(DrdsConvention.INSTANCE).replace(toCollation).replace(toDistribution),
input,
toCollation);
return memSort;
} else {
return input;
}最初，咱们来看一下如何将sort window并行起来，外围是咱们当初要加上distribution的属性了，以便可能充沛的并行，代码如下。
boolean noPartition = keys.size() == 0;
// for exchange(shuffle)
RelDistribution relDistribution =
noPartition ? RelDistributions.SINGLETON : RelDistributions.hash(groupSet);
RelCollation relCollation =
sortWindow.getTraitSet().getTrait(RelCollationTraitDef.INSTANCE);
input = convert(input, input.getTraitSet()
.replace(MppConvention.INSTANCE)
.replace(relDistribution)
.replace(relCollation));
SortWindow newSortWindow =
sortWindow.copy(
sortWindow.getTraitSet()
.replace(MppConvention.INSTANCE)
.replace(relDistribution),
Arrays.asList(input)
);优化规定
所有的优化规定起码要答复三个问题，为什么可能优化，在哪些场景中可能应用，在可能应用的场景中这种优化是否总是正向的。相干的规定次要包含，ProjectWindowTransposeRule ，FilterWindowTransposeRule 和CBOJoinWindowTransposeRule 。 ProjectWindowTransposeRule用于将project尽可能下压到window上面，以便尽早过滤不须要的列，须要留神的是project中下层窗口函数计算结果的列显然不能推下去。
FilterWindowTransposeRule用于将filter尽可能下压到window上面，以便尽早过滤不须要的记录。这外面的外围有两个，首先，咱们须要将filter中的condition合成为应用and连贯的condition列表，比方c1 = 1 and (c2 > 1 or c2 > 2) -> List{c1=1, c2 > 1 or c3 > 2}。其次，对上述list中的condition进行循环判断，当window中用于partition的列须要蕴含该condition中的所有列时，该condition能够被推到window上面，否则不行，代码如下。
// decompose condition by AND
final List<RexNode> conditions =
RelOptUtil.conjunctions(filterRel.getCondition());
for (RexNode condition : conditions) {
ImmutableBitSet rCols = RelOptUtil.InputFinder.bits(condition);
if (window.keys.contains(rCols)) {
pushedConditions.add(condition.accept(new RelOptUtil.RexInputConverter(rexBuilder,
origFields,
window.getInput(0).getRowType().getFieldList(),
adjustments)));
} else {
remainingConditions.add(condition);
}
}CBOJoinWindowTransposeRule 用于判断是否须要将join和window进行调换，筹备来讲，其匹配的模式是join的右侧为filter，同时filter的输出是window，如下所示。
public static final CBOJoinWindowTransposeRule INSTANCE =
new CBOJoinWindowTransposeRule(
operand(LogicalJoin.class,
operand(RelNode.class, any()),
operand(LogicalFilter.class, operand(LogicalWindow.class, any()))
),
RelFactories.LOGICAL_BUILDER,
"INSTANCE");转换前后的子树结构如下图所示，并非对于所有SQL，左边的子树都更优，这外面的外围在于join的过滤性与filter的过滤性。如果join的过滤性十分好，则左边可能会更优，因为通过join后，输出到window中的记录数被大大削减。不过利用该规定须要比拟小心，join的右边列必须要能保障全局惟一，否则通过join后，输出到window中的相干的右表的记录数会被放大，这就不满足原始的语义了，同时join应该为等值join并且join key与window的partition key雷同。
执行器
window算子接管到的输出是依照partition key + sort column排好序的，所以咱们要做的就是，找出每行记录对应的分区，而后依据目前缓存的记录和frame的定义，计算可能计算的所有行，如果须要输入，则向下层吐数据，否则持续承受下一批输出。当然，因为状况还比拟多，所以有一些细节须要思考，具体可参考OverWindowFramesExec ，也可对照下图进行了解。
其次是如何接入异步执行框架，因为这并不是一个通用的需要，并且咱们还没有进行异步执行框架的源码解读，开展介绍不容易讲清楚，意义也不太大。 最初，咱们来聊两个细节的优化吧。第一个优化的出发点是针对非凡场景进行优化，即是否在所有场景下，咱们都须要缓存数据，实际上只有窗口不会蕴含以后行的后续行，就不须要缓存数据，详情可见下图，这部分的解决在NonFrameOverWindowExec 算子中。
第二个优化的出发点是尽量避免当窗口滑动时，窗口函数须要全副从新计算。如下图所示，当咱们从右边的窗口滑动至左边的窗口时，咱们只须要把新增的记录放入窗口函数中计算即可，不用全副从新计算。
咱们再来看一个略微更简单一点的滑动窗口，此时并非只有新增的记录，也有移除的记录，做增量的计算就变得更加简单了。如下图所示，窗口中新增了y，然而移除了x，在这种状况下是否须要全量的从新计算取决于聚合函数的类型，比方sum是能够的，然而bit_and或者max之类的就是不行的，或者说没有那么容易，而且在这种状况下这种优化的成果是否有比拟好的成果取决于窗口的大小。更加简单一点的优化，感兴趣的敌人能够搜寻线段树。
总结
在本文中，咱们首先介绍了window是什么，后续通过举例的形式，别离从优化器和执行器方面对窗口函数的设计要点进行了介绍。
作者：越寒
原文链接
本文为阿里云原创内容，未经容许不得转载。
发表回复