In designing query processing primitives, a crucial design choice is the method for data transfer between two operators in a query plan. As we were considering this critical design mechanism for an in-memory database system that we are building, we quickly realized that (surprisingly) there isn't a clear definition of this concept. Papers are full of ad hoc use of terms like pipelining and blocking, but these terms are not crisply defined, making it hard to fully understand the results attributed to these concepts. To address this limitation, we introduce a clear terminology for how to think about data transfer between operators in a query pipeline. We argue that there isn't a clear definition of pipelining and blocking, and that there is a full spectrum of techniques based on a simple concept called unit-of-transfer. Next, we develop an analytical model for inter-operator communication, and highlight the key parameters that impact performance (for in-memory database settings). Armed with this model, we then apply it to the system we are designing and highlight the insights that we gathered from this exercise. We find that the gap between the traditional “pipelining” and “non-pipelining” methods of query processing, w.r.t. key factors such as performance and memory footprint is quite narrow, and thus system designers should likely rethink the notion of “pipelining” vs. “blocking” for in-memory database systems.

Interactive time responses are a crucial requirement for users analyzing large amounts of data, typically stored in a relational style data-warehouse where data is partitioned across thousands of nodes for high efficiency and throughput. However, consistently providing quick responses remains a big challenge for two reasons: (1) with data distributed across thousands of nodes, it is highly likely that some nodes are unavailable or are very slow during query execution and, (2) large number of users result in high resource contention which exacerbates the problem of slow and failing nodes. In such situations, systems typically straggle or fail the query resulting in higher latencies and wastage of resources. In this paper, we propose a novel solution to alleviate the failure/straggling problem: use the intermediate results from the partial query execution over available data, and exploit the statistical properties of efficiently partitioned data, particularly, co-hash partitioned data, to provide approximate answers along with confidence bounds. The proposed approach handles aggregate queries that involve joins, group bys, having clauses and a subclass of nested subqueries, covering a large portion of analytical queries. We validate our approach through extensive experiments on the TPC-H dataset and we observe that even with a low data availability of 1%, our proposed solution provides answers with less than 5% error.

Distributed in-memory caching is a key component of modern Internet services. Such caches are often accessed via remote procedure call (RPC), as RPC frameworks provide rich support for productionization, including protocol versioning, memory efficiency, auto-scaling, and hitless upgrades. However, full-featured RPC limits performance and scalability as it incurs high latencies and CPU overheads. Remote Memory Access (RMA) offers a promising alternative, but meeting productionization requirements can be a significant challenge with RMA-based systems due to limited programmability and narrow RMA primitives.

Modern servers pack enough storage and computing power that just a decade ago was spread across a modest-sized cluster. This paper presents a prototype system, called Quickstep, to exploit the large amount of parallelism that is packed inside modern servers. Quickstep builds on a vast body of previous methods for organizing data, optimizing, scheduling and executing queries, and brings them together in a single system. Quickstep also includes new query processing methods that go beyond previous approaches. To keep the project focused, the project's initial target is read-mostly in-memory data warehousing workloads in single-node settings. In this paper, we describe the design and implementation of Quickstep for this target application space. We also present experimental results comparing the performance of Quickstep to a number of other systems, demonstrating that Quickstep is often faster than many other contemporary systems, and in some cases faster by orders-of-magnitude. Quickstep is an Apache (incubating) project.