Page 222 - 《软件学报》2021年第10期

3194 Journal of Software 软件学报 Vol.32, No.10, October 2021

统不断扫描事实表,将元组推入过滤器中,元组在 filter 中对维度表进行 join 操作,之后被推入聚合算子中.CJoin
流水线可同时进行多个查询,在扫描时通过对 tuple 进行标记,带有查询 id 的 tuple 被源源不断地推入 filter 中与
维度表进行连接,之后再推入聚合算子以生成一个多查询结果集,最后通过查询 id 得到查询所对应的元组.实验
中,CJoin 在高并发星型查询场景下,吞吐量比传统商业系统要领先一个数量级.但 Cjoin 的设计使其支持的查询
场景单一,可扩展性不高;并且对于设备内存要求较高,因为其维度表必须存储在内存中,否则事实表与维度表
的连接操作将大大拖慢整个系统.
Aggr
聚合算子
连续扫描
Continuous scan
事实表 预处理器 过滤器 过滤器 过滤器 分配器 Aggr
Fact table Preprocessor Filter Filter Filter Distributor 聚合算子

流水线管理器 Aggr
Pipeline
manager 聚合算子
Fig.13 Cjoin pipeline
图 13 Cjoin 查询流水线模型

SELECT ,A Aggr 1 ,..., Aggr k
FROM ,FD 1 d ,...,D n d


j
j
WHERE 1≤≤ nF  D 1 d AND 1≤ ≤ n  j c (D j d ) AND  co F
( )
GROUP BY B
Fig.14 Star query mode
图 14 星型查询模式
2010 年,Subi 利用各种多查询共享技术,设计了一个以数据为中心的多查询原型数据库系统,名为
Datapath [21] .在 DataPath 中,查询不请求数据,取而代之的是:系统自动地将数据推送到 CPU 中进行计算,一旦到
达该相应的位置,所有可以使用数据的运算符都将对它们进行所需的计算,而 DataPath 中的共享机会在于将多
个相似的运算符合并,并在数据被推入运算符时达到共享计算的目的.Datapath 把全局查询计划中的每个运算
符视为一个 waypoint,新来的查询被拆分为若干运算符,这些运算符要么与相同的 waypoint 合并,要么被创建为
新的 waypoint 并加入到全局查询计划中.系统每隔一段时间就将数据 push 至各 waypoint 中.
Datapath 主要围绕两个问题进行研究:路径网络和调度策略.Subi 等人设计的显示调度策略如下:调度程序
为单线程,主要对 work queue 进行操作.当 I/O 子系统或 waypoint 产生一个块时,该块和任何相关的元数据将被
放入 work queue 中.调度程序不断监视 work queue 中块的进出.从 work queue 中提取块时,调度程序有两个选项:
(1) 系统可能没有足够的 CPU 资源来处理该块,因此必须丢弃该块;(2) 调度程序可以将块提供给相关的
waypoint.waypoint 本身在调度程序的线程上运行,并像调度程序一样,它们实际上不执行任何数据处理.取而代
之的是:一个 waypoint 将数据块打包到一个工作单元中,该工作单元既包含数据块,也需要处理该数据块所需的
任何其他状态信息,包括代码和元数据.工作单元构造完成后,调度程序将工作单元发送到工作线程,由该线程
执行工作单元.调度程序通常为每个 CPU 内核维护一个工作线程.Subi 等人设计的路径网络优化策略如下:路径
网络优化器类似于传统的基于成本的查询优化器;系统将现有的路径网络作为输入,然后以数据移动代价尽可
能小的方式将新查询应用到路径网络中;他们将路径网络优化视为基于成本的搜索问题,对于一个 waypoint(w)
来说,设 t(w)为该 waypoint 所对应的算子需要执行的所有元组;路径网络 P 的成本定义为  tw
() .Subi 等人
WP
目前使用 A*style 搜索 [19] 来实现将新查询集成到路径网络中的过程.
到目前为止,Datapath 的研究进展并不是很乐观,最大的原因是:当查询并发量非常大时,waypoint 的管理和
维护成本也变得非常高,新来的查询往往无法与原本的 waypoint 进行合并,从而达不到共享的效果.对此,