Less is More: How Fewer Results Improve Progressive Join Query Processing
Less is More: How Fewer Results Improve Progressive Join Query Processing
复制标题
少即是多：更少的结果如何改进渐进式连接查询处理
DOI：
10.1145/3603719.3603728
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Eldawy, Ahmed
中科院分区：
文献类型：
--
作者：
Zhang, Xin;Eldawy, Ahmed
随着交互式和高效地进行数据分析和探索的需求，渐进式数据处理，特别是渐进式连接，成为数据科学的关键。由于输入数据集之间的相关性，连接查询特别具有挑战性，这会导致结果偏向于某些连接键。现有的方法仔细控制输入的哪些部分进行处理，以提高渐进结果的质量。如果质量不令人满意，他们将处理更多的数据以改善结果。在本文中，我们提出了一种替代方法，最初似乎违反直觉，但令人惊讶的是，它工作得很好。在查询处理之后，我们有意地向用户报告较少的结果，以提高质量。关键的想法是，如果输出偏离了正确的分布，我们暂时隐藏一些结果来纠正偏差。当我们处理更多的数据时，隐藏的结果会被插入，直到处理完整个数据集。主要的挑战是，我们不知道正确的输出分布，而渐进式查询正在运行。在这项工作中，我们正式定义了渐进连接问题的质量和渐进的结果率的限制。我们提出了一个输入和输出质量感知的渐进连接框架（QPJ），它（1）提供输入控制，决定处理输入的哪些部分;（2）渐进地估计最终结果分布;（3）自动控制渐进输出速率的质量;（4）结合输入和输出控制，以实现渐进结果的质量控制。我们比较QPJ与现有的方法，并显示QPJ可以提供渐进的输出，可以代表比现有的方法更好的最终答案。
With the requirements to enable data analytics and exploration interactively and efficiently, progressive data processing, especially progressive join, became essential to data science. Join queries are particularly challenging due to the correlation between input datasets which causes the results to be biased towards some join keys. Existing methods carefully control which parts of the input to process in order to improve the quality of progressive results. If the quality is not satisfactory, they will process more data to improve the result. In this paper, we propose an alternative approach that initially seems counter-intuitive but surprisingly works very well. After query processing, we intentionally report fewer results to the user with the goal of improving the quality. The key idea is that if the output is deviated from the correct distribution, we temporarily hide some results to correct the bias. As we process more data, the hidden results are inserted back until the full dataset is processed. The main challenge is that we do not know the correct output distribution while the progressive query is running. In this work, we formally define the progressive join problem with quality and progressive result rate constraints. We propose an input&output quality-aware progressive join framework (QPJ) that (1) provides input control that decides which parts of the input to process; (2) estimates the final result distribution progressively; (3) automatically controls the quality of the progressive output rate; and (4) combines input&output control to enable quality control of the progressive results. We compare QPJ with existing methods and show QPJ can provide the progressive output that can represent the final answer better than existing methods.