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

Suny At Buffalo, Amherst NY

Investigators

Abstract

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.