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

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

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.