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.

One of the bottlenecks in parallel query processing is the cost of shuffling data across nodes in a cluster. Ideally, given a distribution of the data across the nodes and a query, we want to execute the query by performing only local computation and no communication: in this case, the query is called parallel-correct with respect to the data distribution. Previous work studied this problem for Conjunctive Queries in the case where the distribution scheme is oblivious, i.e., the location of each tuple depends only on the tuple and is independent of the instance. In this work, we show that oblivious schemes have a fundamental theoretical limitation, and initiate the formal study of distribution schemes that are locality-aware. In particular, we focus on a class of distribution schemes called co-hash distribution schemes, which are widely used in parallel systems. In co-hash partitioning, some tables are initially hashed, and the remaining tables are co-located so that a join condition is always satisfied. Given a co-hash distribution scheme, we formally study the complexity of deciding various desirable properties, including obliviousness and redundancy. Then, for a given Conjunctive Query and co-hash scheme, we determine the computational complexity of deciding whether the query is parallel-correct. We also explore a stronger notion of correctness, called parallel disjoint correctness, which guarantees that the query result will be disjointly partitioned across nodes, i.e., there is no duplication of results.

Representation systems have been widely used to capture different forms of incomplete data in various settings. However, existing representation systems are not expressive enough to handle the more complex scenarios of missing data that can occur in practice: these could vary from missing attribute values, missing a known number of tuples, or even missing an unknown number of tuples. In this work, we propose a new representation system called m-tables, that can represent many different types of missing data. We show that m-tables form a closed, complete and strong representation system under both set and bag semantics and are strictly more expressive than conditional tables under both the closed and open world assumptions. We further study the complexity of computing certain and possible answers in m-tables. Finally, we discuss how to "interpret" m-tables through a novel labeling scheme that marks a type of generalized tuples as certain or possible.

Scaling complex transactional workloads in parallel and distributed systems is a challenging problem. When transactions span data partitions that reside in different nodes, significant overheads emerge that limit the throughput of these systems. In this paper, we present a low-overhead data partitioning approach, termed JECB, that can reduce the number of distributed transactions in complex database workloads such as TPC-E. The proposed approach analyzes the transaction source code of the given workload and the database schema to find a good partitioning solution. JECB leverages partitioning by key-foreign key relationships to automatically identify the best way to partition tables using attributes from tables. We experimentally compare our approach with the state of the art data-partitioning techniques and show that over the benchmarks considered, JECB provides better partitioning solutions with significantly less overhead.