Efficient Incrementialization of Correlated Nested Aggregate Queries using Relative Partial Aggregate Indexes (RPAI)
Efficient Incrementialization of Correlated Nested Aggregate Queries using Relative Partial Aggregate Indexes (RPAI)
复制标题
使用相对部分聚合索引 (RPAI) 实现相关嵌套聚合查询的高效增量化
DOI：
10.1145/3514221.3517889
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Rompf, Tiark
中科院分区：
文献类型：
--
作者：
Abeysinghe, Supun;He, Qiyang;Rompf, Tiark
在数据作为流到达并且输出是延迟关键的和/或在接收到完整数据之前期望的情况下，查询的增量化是必要的。增量执行通过重用以前计算的输出或维护的视图来计算给定时间的输出，而不是从头开始重新计算查询。有各种方法来执行这种增量化，范围从查询特定算法和数据结构（例如，DYN，AJU）到通用系统（例如，DBToaster是一个最先进的系统，它具有吸引人的理论背景，基于递归地应用增量视图维护（IVM）的思想，通过增量查询维护物化视图的层次结构。然而，这种方法的一个关键限制是，由于这种查询的低效增量规则，它无法有效地增量相关嵌套聚合查询。此外，其他专门的方法也没有显示出优化此类查询的有效方法。尽管如此，这些类型的查询可以在许多现实世界的应用领域中找到（例如，金融），其中有效的增值仍然是一个关键的开放问题。在这项工作中，我们提出了一种方法来增加这种查询的基础上，一种新的基于树的索引结构，称为相对部分聚合索引（RPAI）。我们的方法比其他系统快得多，并且在具有实际意义的工作负载中显示出高达1100倍的加速比。
Incrementalization of queries is imperative in cases where data arrives as streams and output is latency-critical and/or desired before the full data has been received. Incremental execution computes the output at a given time by reusing the previously computed outputs or maintained views rather than re-evaluating the query from scratch. There are various approaches to perform this incrementalization ranging from query-specific algorithms and data structures (e.g., DYN, AJU) to general systems (e.g., DBToaster, Materialize).DBToaster is a state-of-the-art system that comes with an appealing theoretical background based on the idea of applying Incremental View Maintenance (IVM) recursively, maintaining a hierarchy of materialized views via delta queries. However, one key limitation of this approach is its inability to efficiently incrementalize correlated nested-aggregate queries due to an inefficient delta rule for such queries. Moreover, none of the other specialized approaches have shown efficient ways to optimize such queries either. Nonetheless, these types of queries can be found in many real-world application domains (e.g., finance), for which efficient incrementalization remains a crucial open problem. In this work, we propose an approach to incrementalize such queries based on a novel tree-based index structure called Relative Partial Aggregate Indexes (RPAI). Our approach is asymptotically faster than other systems and shows up to 1100× speedups in workloads of practical importance.
登录
查看更多内容
数据库环中的增量查询评估
DOI：
10.1145/1807085.1807100
发表时间：
2010
期刊：
Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
影响因子：
--
作者：
Christoph E. Koch
通讯作者：
Christoph E. Koch
优化高级程序中的数据结构
DOI：
10.1145/2480359.2429128
发表时间：
2013
期刊：
Sigplan Notices
影响因子：
--
作者：
Tiark Rompf;Arvind K. Sujeeth;Nada Amin;Kevin J. Brown;V. Jovanovic;HyoukJoong Lee;Manohar Jonnalagedda;K. Olukotun;Martin Odersky
通讯作者：
Martin Odersky
Grosbeak：支持资源感知增量计算的数据仓库
DOI：
10.1145/3318464.3384708
发表时间：
2020
期刊：
Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data
影响因子：
--
作者：
Zuozhi Wang;Kai Zeng;Botong Huang;Wei Chen;Xiaozong Cui;Bo Wang;J. Liu;Liya Fan;Dachuan Qu;Zhenyu Hou;Tao Guan;Chen Li;Jingren Zhou
通讯作者：
Jingren Zhou
Function Pearl：500 行代码的 SQL 到 C 编译器
DOI：
10.1145/2784731.2784760
发表时间：
2015
期刊：
Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming
影响因子：
--
作者：
Tiark Rompf;Nada Amin
通讯作者：
Nada Amin
天妇罗
影响因子：
2.5
作者：
Z. Wang;Kai Zeng;Botong Huang;Wei Chen;Xiaozong Cui;Bo Wang;J. Liu;Liya Fan;Dachuan Qu;Zhenyu Hou;Tao Guan;Chen Li;Jingren Zhou
通讯作者：
Jingren Zhou