Querying Interval Data on Steroids

doi:10.1109/TKDE.2025.3597399

Querying Interval Data on Steroids

0

PRE

AI

DOI：10.1109/TKDE.2025.3597399

原文链接

原文求助

摘要

En 中文

广泛应用需要管理区间数据，其中选择操作和重叠连接是最基本的查询操作。选择查询通常采用区间索引进行评估。然而，当前最先进的HINT索引及其竞争对手仅针对单次查询请求设计，而现代系统需同时处理大量查询。针对这一挑战，我们研究了HINT上的选择查询批处理。我们提出了两种新颖策略，即基于层级和基于分区的策略，它们按层级顺序操作，即在移动到下一层级前先收集所有查询的结果。新策略减少了在索引层级中上行时的缓存未命中，特别是基于分区的策略可避免对每个索引分区扫描超过一次。我们在真实世界区间上的实验表明，我们的批处理策略始终优于串行执行查询的基线方法，且基于分区的策略整体效率最高。受查询批次共享计算技术的启发，我们还重新研究了重叠连接，涵盖基于区间索引（预）存在性的不同设置。对于未索引的输入，我们通过为HINT提出的有效分区技术增强了当前最先进的optFS连接算法；对于已索引的输入，我们提出了新型算法HINT-join，它并发扫描输入索引，并使用optFS连接分区对。测试表明，HINT-join在效率上优于采用B+树或仅探测单个HINT（即使结合我们的基于分区的批处理）的索引嵌套循环解决方案。

Keyword:

Interval data

query processing

range queries

selections

overlap joins

batch processing

Querying Interval Data on Steroids

摘要

期刊

机构

引用论文