CRII: III: Optimal Data Organization for Hybrid Transactional/Analytical Processing Data Systems

科学、商业和政府应用程序越来越依赖于使用历史数据和实时更新的数据驱动的洞察和决策。社交馈送、传感器读数(物联网应用的常见用例)和电子小额支付(一种新兴的电子商务模式)产生了新的工作负载。它们都有共同之处：(I)交易量非常大，(Ii)需要使用历史和实时数据来提供有用和可操作的见解的大量分析查询。主要的挑战是这些工作负载具有相互冲突的要求，并且通常使用不同的数据系统架构。一方面，我们希望能够回答这样的分析问题，例如，“过去一年中每个月讨论最多的话题是什么？”，或者“X市每个社区的平均能耗是多少？”另一方面，我们希望高效地存储传入的更新，并能够提供实时洞察力，如“我们现在哪里有电网超载？”，或“基于城市X的社交馈送，灾难发生的可能性有多大？”传统上，数据系统被设计为高效地支持事务性工作负载--即快速存储新项--或分析性工作负载。后者通常包括更改数据布局和组织，以及构建辅助索引结构以允许高效的数据访问。复杂工作负载的出现推动了开发能够支持混合事务/分析处理(HTAP)的新系统的需求。这项研究将允许高效地执行此类工作负载，并以稳健的方式预测工作负载变化。最终，该项目将使数据获取和数据分析过程更加顺畅，并将使复杂的应用程序能够快速分析其数据。研究人员将构建能够有效评估混合工作负载的数据系统，方法是在读取优化和更新优化的数据系统体系结构之间进行导航。要做到这一点，关键是改变物理数据组织，并为每个用例找到最优的。通常，数据对象在物理上以不同的方式在两个极端之间组织：它们要么遵循摄取顺序，即它们在系统中生成或插入的方式，要么根据它们的值(或它们的属性的特定子集)进行组织。这种“结构”(在文献中也称为“有界无序”)被视为这两个极端之间的连续体。在这两者之间，混合数据组织使用不同的方案组织数据集的不同部分。事务更新添加了无序的数据，而高效地回答分析查询需要有界无序的数据。当今的一个根本挑战是找到一种数据组织，使数据系统能够在高效更新和快速分析查询之间实现可调的平衡。该项目从三个不同的角度应对这一挑战。首先，通过制定一个可以在运行时解决的优化问题。第二，通过构造一个稳健的优化问题，即使在初步假设不准确的情况下，也能提供良好的性能。第三，通过构建可以利用底层数据中任何固有的有限无序的访问方法来减少高效分析任务所需的数据组织工作。这项研究工作介绍了HTAP数据系统，该系统可以优化组织数据并利用固有的有界无序，同时在工作负载变化中保持健壮。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Scientific, commercial, and governmental applications increasingly rely on data-driven insights and decision-making using both historical data and real-time updates. New workloads are generated by social feeds, sensor readings (a common use-case of Internet-of-Things applications) and electronic micro-payments (an emerging model of e-commerce). They all have in common: (i) a very high volume of transactions and (ii) a high volume of analysis queries that need to use both historic and real-time data to provide useful and actionable insights. The primary challenge is that these workloads have conflicting requirements, and typically use different data systems architectures. On the one hand, we want to be able to answer analysis queries like, "what was the most discussed topic in each month of the past year?", or "what is the average power consumption per neighborhood of city X?". On the other hand, we want to efficiently store incoming updates and be able to provide real-time insights like "where do we have a power network overload now?", or "what is the probability that a disaster is taking place based on the social feeds of a city X?". Traditionally, data systems were engineered to efficiently support either a transactional workload -- that is, storing quickly new items -- or an analytical workload. The latter typically includes changing the data layout and organization, and building auxiliary indexing structures to allow for efficient data access. The emergence of complex workloads has pushed towards the need to develop new systems that can support hybrid transactional/analytical processing (HTAP). This research will allow to execute such workloads efficiently and to anticipate workload changes in a robust way. Ultimately, the project will make data ingestion and data analysis a smoother process and will enable complex applications to have their data analyzed quickly. The researchers will build data systems that can efficiently evaluate mixed workloads by navigating the read-optimized vs. update-optimized continuum of data systems architectures. The key to do so is to vary the physical data organization and find the optimal for each use-case. Typically, data objects are physically organized in various ways between two extremes: either they follow the ingestion order, that is, the way they are generated or inserted in the system, or they are organized based on their value (or a specific subset of their attributes). This "structure" (also called "bounded disorder" in the literature) is treated as a continuum between the two extremes. In-between, hybrid data organizations have different parts of the dataset organized with different schemes. Transactional updates add data with disorder, while answering analytical queries efficiently requires data with bounded disorder. A fundamental challenge today is to find the data organization that enables a data system to offer a tunable balance between efficient updates and fast analysis queries. This project addresses this challenge from three different angles. First, by formulating an optimization problem, which can be solved at run-time. Second, by formulating a robust optimization problem which will deliver good performance even when preliminary assumptions are not accurate. Third, by building access methods that can exploit any inherently limited disorder in the underlying data to reduce the data organization effort needed for efficient analysis tasks. This research effort introduces HTAP data systems that can optimally organize data and exploit inherently bounded disorder while being robust in workload changes.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.