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.