An important feature of modern query optimizers is the ability to produce a query plan that is optimal for the underlying data set. This requires the ability to estimate cardinalities and computational costs of intermediate query plan nodes, which is highly dependent on both the query shape and the underlying data distribution. Traditional methods include collecting statistics on base tables and implementing cardinality and computational cost derivation inside the optimizer, which is error-prone for complex query shapes. This paper presents Presto's novel history-based optimization framework (HBO), which collects execution histories and uses them to optimize similar queries in the future. The framework produces accurate estimates for complex query shapes in a lightweight, automated manner, and adapts automatically to changes in underlying data distributions. We present the design and implementation of the HBO framework and provide details on its use in various optimization rules, as well as details on implementing the statistics store on top of a Redis key-value store. We also present the results of running HBO in production in two large data infrastructure organizations (Meta and Uber).

Performing a detailed workload analysis is a crucial step in determining the feasibility, timeline and cost of a major data warehouse replatforming project, i.e., migration from one platform to another. A large company's data warehouse applications may include millions of queries, some of which will use features that are unsupported or have different semantics in the new warehouse, or may have poor performance there.

In recent years, increased interest in cloud-based data warehousing technologies has emerged with many enterprises moving away from on-premise data warehousing solutions. The incentives for adopting cloud data warehousing technologies are many: cost-cutting, on-demand pricing, offloading data centers, unlimited hardware resources, built-in disaster recovery, to name a few. There is inherent difference in the language surface and feature sets of on-premise and cloud data warehousing solutions. This could range from subtle syntactic and semantic differences, with potentially big impact on result correctness, to complete features that exist in one system but are missing in other systems. While there have been some efforts to help automate the migration of on-premise applications to new cloud environments, a major challenge that slows down the migration pace is the handling of features not yet supported, or partially supported, by the cloud technologies. In this paper we build on our earlier work in adaptive data virtualization and present novel techniques that allow running applications utilizing sophisticated database features within foreign query engines lacking the native support of such features. In particular, we introduce a framework to manage discrepancy of metadata across heterogeneous query engines, and various mechanisms to emulate database applications code in cloud environments without any need to rewrite or change the application code.

Query throughput degradation is a common problem when migrating applications from an on-premises to a cloud-based data warehouse. In this paper, we propose CAQR: a context-aware query router. CAQR is a middleware-based database replication solution that improves workload throughput by combining the strong points of existing data replication methods and mitigating their limitations at the same time. CAQR provides strong data consistency without the need for real-time synchronization or manual annotation of queries. Employing a master-slave architecture, CAQR runs atop an adaptive data virtualization layer and automatically sends a query to the correct replica, so that the execution preserves the strong data consistency property. Extensive experiments on real-world and benchmark workloads show the practicality and efficiency of the solution: CAQR achieves near-linear scalability, without requiring any changes to the application layer.

The database industry is about to undergo a fundamental transformation of unprecedented magnitude as enterprises start trading their well-established database stacks on premises for cloud database technology in order to take advantage of the economics cloud service providers have long promised. Industry experts and analysts expect the next years to prove a watershed moment in this transformation, as cloud databases finally reached critical mass and maturity.

Wall Street's trading engines are complex database applications written for time series databases like kdb+ that uses the query language Q to perform real-time analysis. Extending the models to include other data sources, e.g., historic data, is critical for backtesting and compliance. However, Q applications cannot run directly on SQL databases. Therefore, financial institutions face the dilemma of either maintaining two separate application stacks, one written in Q and the other in SQL, which means increased IT cost and increased risk, or migrating all Q applications to SQL, which results in losing the inherent competitive advantage on Q real-time processing. Neither solution is desirable as both alternatives are costly, disruptive, and suboptimal. In this paper we present Hyper-Q, a data virtualization plat- form that overcomes the chasm. Hyper-Q enables Q applications to run natively on PostgreSQL-compatible databases by translating queries and results on the fly. We outline the basic concepts, detail specific difficulties, and demonstrate the viability of the approach with a case study.

Partitioning of tables based on value ranges provides a powerful mechanism to organize tables in database systems. In the context of data warehousing and large-scale data analysis partitioned tables are of particular interest as the nature of queries favors scanning large swaths of data. In this scenario, eliminating partitions from a query plan that contain data not relevant to answering a given query can represent substantial performance improvements. Dealing with partitioned tables in query optimization has attracted significant attention recently, yet, a number of challenges unique to Massively Parallel Processing (MPP) databases and their distributed nature remain unresolved. In this paper, we present optimization techniques for queries over partitioned tables as implemented in Pivotal Greenplum Database. We present a concise and unified representation for partitioned tables and devise optimization techniques to generate query plans that can defer decisions on accessing certain partitions to query run-time. We demonstrate, the resulting query plans distinctly outperform conventional query plans in a variety of scenarios.

The performance of analytical query processing in data management systems depends primarily on the capabilities of the system's query optimizer. Increased data volumes and heightened interest in processing complex analytical queries have prompted Pivotal to build a new query optimizer.

MayBMS is a state-of-the-art probabilistic database management system which leverages the strengths of previous database research for achieving scalability. As a proof of concept for its ease of use, we have built on top of MayBMS a Web-based application that offers NBA-related information based on what-if analysis of team dynamics using data available at www.nba.com.

This paper introduces U-relations, a succinct and purely relational representation system for uncertain databases. U-relations support attribute-level uncertainty using vertical partitioning. If we consider positive relational algebra extended by an operation for computing possible answers, a query on the logical level can be translated into, and evaluated as, a single relational algebra query on the U-relational representation. The translation scheme essentially preserves the size of the query in terms of number of operations and, in particular, number of joins. Standard techniques employed in off-the-shelf relational database management systems are effective for optimizing and processing queries on U-relations. In our experiments we show that query evaluation on U-relations scales to large amounts of data with high degrees of uncertainty.

We present a decomposition-based approach to managing incomplete information. We introduce world-set decompositions (WSDs), a space-efficient and complete representation system for finite sets of worlds. We study the problem of efficiently evaluating relational algebra queries on world-sets represented by WSDs. We also evaluate our technique experimentally in a large census data scenario and show that it is both scalable and efficient.

Managing incomplete information is important in many real world applications. In this demonstration we present MayBMS - a system for representing and managing finite sets of possible worlds - that successfully combines expressiveness and efficiency. Some features of MayBMS are: completeness of the representation system for finite world-sets; space-efficient representation of large world-sets; scalable evaluation and support for full relational algebra queries; and probabilistic extension of the representation system and the query language. MayBMS is implemented on top of PostgreSQL. It models incomplete data using the so-called world-set decompositions (WSDs) (Ruggles et al., 2004). For this demonstration, we introduce a probabilistic extension of world-sets and WSDs, where worlds or correlations between worlds have probabilities. The main idea underlying probabilistic WSDs is to use relational factorization combined with probabilistic independence in order to efficiently decompose large world-sets into a set of independent smaller relations. Queries in MayBMS can be expressed in an SQL-like language with special constructs that deal with incompleteness and probabilities. MayBMS rewrites and optimizes user queries into a sequence of relational queries on world-set decompositions.

Incomplete information arises naturally in numerous data management applications. Recently, several researchers have studied query processing in the context of incomplete information. Most work has combined the syntax of a traditional query language like relational algebra with a nonstandard semantics such as certain or ranked possible answers. There are now also languages with special features to deal with uncertainty. However, to the standards of the data management community, to date no language proposal has been made that can be considered a natural analog to SQL or relational algebra for the case of incomplete information.