III: Small: Towards a Database Engine for Interactive and Online Sampling and Analytics

现有数据库和数据管理系统的设计和优化是为了完整地执行查询和分析工作。用户与此类系统的交互仅限于二元决策：要么等待最终的确切答案，要么在作业仍在运行时终止作业，并且对最终输出知之甚少，甚至一无所知。这种模式不再适用于大数据，因为等待确切的查询或分析结果可能需要很长时间。好消息是，在大数据计算中，用户通常不需要精确的结果；相反，他们对近似值很满意，特别是对有质量保证的近似值。如果在执行查询时，以在线方式逐渐提高近似质量，并且用户可以实时控制效率-精度权衡，那就更好了。该项目设计了一些技术，用于构建支持这种交互式和在线探索和分析的数据库引擎。该项目的结果对下游数据分析模块（如信息可视化）也很有用。随着数据的不断增长，整体执行查询和分析的成本越来越高，而且无法实现交互式探索和分析。该项目研究了新的在线采样和近似技术，以实现数据库系统中大数据的在线交互式探索和分析。其主要思想是从一组记录中生成独立的随机样本，这些记录以连续的在线方式满足用户查询。本项目设计的技术可以高效地为数据库引擎中的各种查询和分析工作负载（如join和group-by查询）生成此类在线样本。该项目还开发了基于这些在线样本的在线近似技术。通过将这些技术集成到现有的数据库引擎中，正在开发一个系统原型。在这个项目中开发的技术和系统通过实现交互式和在线探索和分析，有助于提高用户和科学家在各个应用领域的生产力。该项目还通过各种教学、教育和外展活动产生更广泛的影响。

Existing databases and data management systems are designed and optimized for executing queries and analytical jobs in their entirety. User interactions with such systems are limited to binary decisions: either wait for exact answers in the end, or terminate a job while it is still running and obtain little or even zero knowledge regarding the final output. This model no loner works well with big data as waiting for the exact query or analytical results may take a long time. The good news is that often users do not need exact results in big data computation; instead, they are happy with approximations, especially for approximations with quality guarantees. It is even better if the approximation quality gradually improves over time in an online fashion, while the query is being executed, and users can control the efficiency-accuracy tradeoff in realtime. This project designs techniques for building a database engine that supports such interactive and online exploration and analytics. The results of this project is also useful for downstream data analytical modules such as information visualization.As data continues to grow, executing queries and analytics in their entirety is increasingly more expensive and falls short of enabling interactive exploration and analytics. This project investigates novel online sampling and approximation techniques to enable online and interactive exploration and analytics over big data in a database system. The main idea is to produce independent random samples from the set of records that satisfy the user query in a continuous online fashion. This project designs techniques that produce such online samples efficiently and effectively for a wide range of queries and analytical workloads, such as join and group-by queries, in a database engine. The project also develops online approximation techniques based on these online samples. A system prototype is being developed by integrating these techniques into an existing database engine. The techniques and the system developed in this project helps increase the productivity of users and scientists in various application domains by enabling interactive and online exploration and analytics. The project also makes broader impacts through various teaching, education, and outreach activities.