CAREER: Speedy and Reliable Approximate Queries in Hybrid Transactional/Analytical Systems

实时数据分析使人们能够从当今快速增长的大型数据库中提取及时的见解，这些数据库可以提供重要的经济和社会价值。例如，使用在线金融交易数据进行欺诈检测，基于对实时数据的分析来优化营销策略等。构建了一种称为混合交易/分析处理(HTAP)的新型数据库系统，以在响应时间较短的在线交易数据库上执行这些分析查询，但它们需要不断增加的计算资源，并且随着数据的持续快速增长，查询响应时间可能仍然会延长。近似查询处理(AQP)技术可以通过在查询处理管道中执行随机采样来显著减少查询响应时间，但它们仅适用于无法在线更新的静态数据库。该项目旨在通过在HTAP系统中启用快速可靠的AQP功能，支持在大型且快速增长的数据库上进行可扩展的实时数据分析。该项目将产生一个支持近似实时数据分析的开源系统，从而有可能实现上述实时数据分析应用程序。此外，该项目还将支持开发关于现代数据管理系统的新教材，包括HTAP和AQP系统，以及对本科生和研究生的研究培训，以提高STEM工作人员的准备程度。此外，它还将支持开发K-12外联计划的数据管理教育材料，并提高公众对数据库技术的认识。现有的HTAP系统执行精确的查询处理，这至少会导致输入大小的线性计算成本，不再是一个可行的解决方案，因为数据的快速增长已经超过了处理器速度和存储带宽的有限增长。近似查询处理(AQP)是一种快速的替代方法，如果应用程序可以容忍近似处理，则可能达到次线性时间开销，但现有技术存在几个缺点，包括高数据扫描成本，无法执行正确和有效的事务更新，以及不准确的估计和不可靠的错误诊断结果。该项目旨在通过AQP和HTAP系统组件的共同设计来解决这些缺陷，这些组件包括数据存储和索引层、事务并发控制协议和近似查询处理算法。具体地说，该项目将产生三个主要的科学贡献：(1)它将为HTAP存储开发一个线程安全、高性能和简洁的采样索引设计。它将提供必要的线程安全原子更新和快速采样功能，以便在HTAP系统中实现快速可靠的AQP。(2)将设计新的协议，对具有混合更新和近似查询的数据库事务执行快照隔离和可串行化。(3)它还将研究一种新的采样策略，该策略利用快速采样功能在给定用户指定的置信度目标的情况下将近似查询延迟降至最低，以及一种后台诊断服务，用于可靠地诊断真实答案未落入用户指定置信度的估计置信度区间的估计失败。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Real-time data analytics allow one to extract timely insights from today’s large and rapidly growing databases, which can provide important economic and social values. Examples include fraud detection using online financial transaction data, optimizing marketing strategies based on analysis of real time data, etc. A new type of database system called Hybrid Transactional/Analytical Processing (HTAP) is built to perform these analytical queries over online transactional databases with low response time, but they require increasing computation resources and may still have prolonged query response time as the data continue to grow rapidly. Approximate Query Processing (AQP) techniques can significantly reduce query response time by performing random sampling in the query processing pipelines, but they are only designed for static databases that cannot be updated online. This project seeks to support scalable real-time data analytics on large and rapidly growing databases, by enabling speedy and reliable AQP capabilities in HTAP systems. The project will result in an open-source system that supports approximate real-time data analytics, and thus can potentially enable the aforementioned real-time data analytics applications. Furthermore, this project will also support the development of new educational materials on modern data management systems, include HTAP and AQP systems, as well as research training of undergraduate and graduate students, to improve the readiness of the STEM workforce. In addition, it will also support development of educational materials in data management for K-12 outreach programs and improve the public awareness of database technologies.Existing HTAP systems perform exact query processing, which incurs at least linear computation cost to input size, and are no longer a viable solution as the rapid growth of data has outpaced limited increase in processor speed and storage bandwidth. Approximate Query Processing (AQP) is a fast alternative that may achieve sublinear time cost if the application can tolerate approximation, but the existing techniques suffer from several drawbacks including high data scan cost, inability to perform correct and efficient transactional updates, as well as inaccurate estimation and unreliable error diagnosis results. This project aims to resolve these drawbacks through a co-design of AQP and HTAP system components including data storage and indexing layer, transaction concurrency control protocols and approximate query processing algorithms. Specifically, this project will result in three main scientific contributions: (1) It will develop a thread-safe, high-performance, and succinct sampling index design for HTAP storage. It will provide the necessary thread-safe atomic update and fast sampling capabilities for enabling speedy and reliable AQP in HTAP systems. (2) It will design new protocols to enforce snapshot isolation and serializability for database transactions with mixed updates and approximate queries. (3) It will also investigate a new sampling strategy leveraging the fast-sampling capabilities to minimize approximate query latency given a user-specified confidence bound target, and a background diagnosis service for reliably diagnosing estimation failures where the true answer does not fall into the estimated confidence interval with the user-specified confidence.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.