Modern trends in data collection are bringing current mainstream techniques for database query processing to their limits. Consequently, various novel approaches for efficient query processing are being actively studied. One such approach is based on hypertree decompositions (HDs), which have been shown to carry great potential to process complex queries more efficiently and with stronger theoretical guarantees. However, using HDs for query execution relies on the difficult task of computing decompositions of the query structure, which guides the efficient execution of the query. From theoretical results we know that the performance of purely sequential methods is inherently limited, yet the problem is susceptible to parallelisation. In this paper we propose the first algorithm for computing hypertree decompositions that is well-suited for parallelisation. The proposed algorithm log-k-decomp requires only a logarithmic number of recursion levels and additionally allows for highly parallelised pruning of the search space by restriction to balanced separators. We provide detailed experimental evaluation over the HyperBench benchmark and demonstrate that our approach is highly effective especially for complex queries.


翻译:现代数据收集趋势正在将当前数据库查询处理的主流技术提高到极限,因此,正在积极研究各种高效查询处理的新办法,其中一种办法是基于超树分解法(HDs),这证明极树分解法极有可能更高效地处理复杂的查询,并具有更强的理论保障。然而,使用HDs进行查询执行取决于对查询结构进行计算分解的困难任务,这指导了查询的有效执行。根据理论结果,我们知道纯顺序方法的性能必然有限,但问题容易发生平行化。在本文件中,我们提出了计算极树分解法的首个算法,该算法非常适合平行化。提议的log-k-decomp只需要对数的递合率,并额外允许通过限制平衡的分隔器对搜索空间进行高度平行的剪裁。我们提供了对超贝辛基准的详细实验性评估,并表明我们的方法特别对复杂的查询非常有效。

0
下载
关闭预览

相关内容

Processing 是一门开源编程语言和与之配套的集成开发环境(IDE)的名称。Processing 在电子艺术和视觉设计社区被用来教授编程基础,并运用于大量的新媒体和互动艺术作品中。
专知会员服务
52+阅读 · 2020年9月7日
专知会员服务
17+阅读 · 2020年9月6日
【Google论文】ALBERT:自我监督学习语言表达的精简BERT
专知会员服务
22+阅读 · 2019年11月4日
开源书:PyTorch深度学习起步
专知会员服务
50+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
91+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
8+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
利用动态深度学习预测金融时间序列基于Python
量化投资与机器学习
18+阅读 · 2018年10月30日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年6月16日
Arxiv
0+阅读 · 2021年6月15日
VIP会员
相关VIP内容
专知会员服务
52+阅读 · 2020年9月7日
专知会员服务
17+阅读 · 2020年9月6日
【Google论文】ALBERT:自我监督学习语言表达的精简BERT
专知会员服务
22+阅读 · 2019年11月4日
开源书:PyTorch深度学习起步
专知会员服务
50+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
91+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
8+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
利用动态深度学习预测金融时间序列基于Python
量化投资与机器学习
18+阅读 · 2018年10月30日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员