CRII: III: RUI: Adaptive Query Processing for Crowd-Powered Database Systems

数据库系统向用户提供询问或查询关于系统存储的数据集合的能力（例如，找到在公司工作至少2年的员工），并快速提供答案。人比计算机更有能力解决需要判断或数据解释的问题，因为他们有真实世界的经验和感知。群体驱动的数据库系统使用被称为“群体”的人群来帮助回答用户的查询，这是通过招募他们使用主观的和/或需要视觉或语义解释的标准来处理数据。例如，用户可能希望找到一组教师职位，其中职位描述讨论了对多样性的承诺，并且学校位于安全位置;解释每个职位描述和研究犯罪统计数据是非常适合人们执行的任务。该系统可以协调群组工作者以比用户单独更有效地处理数据，这在存在多于少数数据项要处理时是有利的。虽然群体处理的查询可能需要数小时或数天才能完成，但群体驱动的数据库系统能够处理复杂的查询。例如，确定哪些关于某个医疗设备的研究文章包含将该设备与其他设备进行比较的实验结果，或者找出一组珠宝商中的哪一个只使用道德来源的金属和石头，并且还运往阿拉斯加。数据库系统被设计为优化单个用户的查询处理效率。查询通常涉及多个部分，例如，对于工作公告查询，这些是（1）过滤掉不描述对多样性的承诺的工作，以及（2）过滤掉不安全地点的学校的工作。不满足第一个标准的作业不需要为第二个标准处理，反之亦然。查询各部分的处理顺序会影响所需的计算量以及处理查询所需的时间。传统的数据库系统具有关于查询的部分将花费多长时间以及项目满足过滤器的可能性的信息;它们使用这些信息来为查询选择有效的处理顺序。然而，这些信息对于群体驱动的数据库系统来说是未知的。优化器对群体驱动数据库系统的有用性取决于它们在处理查询之前，当此信息未知时，找到一种有效的方法来处理用户的查询的能力。本研究项目的目的是通过开发一个系统来处理涉及多个过滤标准的查询，观察执行环境，并调整其处理策略，作为查询执行，以应对这一挑战。该项目将产生广泛的影响，产生一个查询处理系统，使用户能够提出更有趣的数据问题，推进在动态环境中分配人类计算资源的研究，本研究的目标是建立一个基于成本的查询优化器，用于群体查询，在优化中使用的重要统计数据在查询时未知的强力过滤器查询。这些统计数据包括传统的指标，如过滤器选择性，以及查询成本的新贡献者，如人群工作人员完成一个工作单元所需的时间，以及达成主观评估共识所需的工作人员数量。该项目采用自适应方法进行查询处理：当查询运行时，系统观察成本和选择性信息，并定期重新排序查询计划操作符，以降低整体查询成本。研究人员将证明，他们的查询优化器产生的查询成本与基于人群的最佳查询计划的成本相当，其中选择性和主观性信息是先验已知的。源代码、论文和演示文稿可在项目网站（https：//www.cs.hmc.edu/adaptivecrowd.shtml）上查阅。

Database systems provide users with the ability to ask questions, or queries, about collections of data that the system stores (e.g., find employees who had worked in the company for at least 2 years) and provide the answers very fast. People are better equipped than computers to tackle problems that require judgement or data interpretation due to their real-world experience and perception. A crowd-powered database system uses groups of people called "the crowd" to help with answering users' queries by recruiting them to process data using criteria that are subjective and/or require visual or semantic interpretation. For example, a user may want to find a set of faculty job postings in which the job description discusses a commitment to diversity and for which the school is in a safe location; interpreting each job description and researching crime statistics are tasks well-suited for people to perform. The system can coordinate crowd workers to process data more efficiently than the user alone could, which is advantageous when there are more than a handful of data items to process. While queries processed by the crowd may take hours or days to complete, crowd-powered database systems enable the processing of complex queries. For example, queries such as determining which research articles about a certain medical device contain experimental results comparing this and other devices, or finding out which of a set of jewelers only use ethically sourced metals and stones and also ship to Alaska. Database systems are designed to optimize the efficiency of query processing of individual users. A query often involves multiple parts, e.g., for the job postings query these are (1) filter out jobs that do not describe a commitment to diversity and (2) filter out jobs for schools in an unsafe location. A job that does not meet the first criterion does not need to be processed for the second one, and vice versa. The processing order for the parts of the query influences how much computation is needed and how long the query will take to process. Traditional database systems have information about how long parts of a query will take and the likelihood of items satisfying filters; they use this information to choose an efficient processing ordering for a query. However, this information is not known for crowd-powered database systems. The usefulness of optimizers for crowd-powered database systems hinges on their ability to find an efficient way to process a user's query when this information is unknown before processing the query. The aim of this research project is to tackle this challenge by developing a system to process queries involving multiple filtering criteria that observes the execution environment and adjusts its processing strategy as the query executes. This project will have broad impact by yielding a query processing system that will empower users to ask more interesting questions about data, advancing research in allocating human computation resources in dynamic environments, as well as training a group of undergraduate students both in research and in the principles of systems design.The goal of this research is to build a cost-based query optimizer for crowd-powered filter queries for which important statistics used in optimization are unknown at query time. These statistics include traditional metrics such as filter selectivity as well as new contributors to query cost such as the time it takes crowd workers to complete a unit of work and the number of workers needed to reach consensus for a subjective evaluation. The project takes an adaptive approach to query processing: while the query is running, the system observes cost and selectivity information and periodically reorders the query plan operators to reduce overall query cost. The researchers will demonstrate that their query optimizer yields query costs that are comparable to costs from the optimal crowd-based query plan for which selectivity and subjectivity information is known a priori. Source code, papers, and presentations are available on the project web site (https://www.cs.hmc.edu/~beth/adaptivecrowd.shtml).