Microsoft recently introduced Azure Synapse Analytics, which offers an integrated experience across data ingestion, storage, and querying in Apache Spark and T-SQL over data in the lake, including files and warehouse tables. In this paper, we present our experiences with designing and implementing Hyperspace, the indexing subsystem underlying Synapse. Hyperspace enables users to build multiple types of secondary indexes on their data, maintain them through a multi-user concurrency model, and leverage them automatically---without any change to their application code---for query/workload acceleration. Many requirements of Hyperspace are based on feedback from several enterprise customers. We present the details of Hyperspace's underlying design, the user-facing APIs, its concurrency control protocol for index access, its index-aware query processing techniques, and its maintenance mechanisms for handling index updates. Evaluations over standard industry benchmarks and real customer workloads show that Hyperspace can accelerate query execution by up to 10x and in certain real-world workloads, even up to two orders of magnitude.

For decades, RDBMSs have supported declarative SQL as well as imperative functions and procedures as ways for users to express data processing tasks. While the evaluation of declarative SQL has received a lot of attention resulting in highly sophisticated techniques, the evaluation of imperative programs has remained naïve and highly inefficient. Imperative programs offer several benefits over SQL and hence are often preferred and widely used. But unfortunately, their abysmal performance discourages, and even prohibits their use in many situations. We address this important problem that has hitherto received little attention. We present Froid, an extensible framework for optimizing imperative programs in relational databases. Froid's novel approach automatically transforms entire User Defined Functions (UDFs) into relational algebraic expressions, and embeds them into the calling SQL query. This form is now amenable to cost-based optimization and results in efficient, set-oriented, parallel plans as opposed to inefficient, iterative, serial execution of UDFs. Froid's approach additionally brings the benefits of many compiler optimizations to UDFs with no additional implementation effort. We describe the design of Froid and present our experimental evaluation that demonstrates performance improvements of up to multiple orders of magnitude on real workloads.

In recent years, Massively Parallel Processors have increasingly been used to manage and query vast amounts of data. Dramatic performance improvements are achieved through distributed execution of queries across many nodes. Query optimization for such system is a challenging and important problem.

Research on query optimization has traditionally focused on exhaustive enumeration of an exponential number of candidate plans. Alternatively, heuristics for query optimization are restricted in several ways, such as by either focusing on join predicates only, ignoring the availability of indexes, or in general having high-degree polynomial complexity. In this paper we propose a heuristic approach to very efficiently obtain execution plans for complex queries, which takes into account the presence of indexes and goes beyond simple join reordering. We also introduce a realistic workload generator and validate our approach using both synthetic and real data.

Column statistics are an important element of cardinality estimation frameworks. More accurate estimates allow the optimizer of a RDBMS to generate better plans and improve the overall system's efficiency. This paper introduces filtered statistics, which model value distribution over a set of rows restricted by a predicate. This feature, available in Microsoft SQL Server, can be used to handle column correlation, as well as focus on interesting data ranges. In particular, it fits well for scenarios with logical subtables, like flexible schema or multi-tenant applications. Integration with the existing cardinality estimation infrastructure is presented.

Efficient and convenient handling of heterogeneous data is a current challenge for data management systems. In this paper, we discuss several common relational approaches to represent heterogeneity and argue for a design based on a single wide-table, referred to as a flexible schema. For this scenario, we focus on partial indexation and its support for efficient data storage and processing. Filtered indices provide partial indexation functionality in the Microsoft SQL Server product. We describe here the implementation of this feature, including index utilization in queries, index maintenance and query parameterization issues. Our performance experiments validate the expected benefits of the approach in our implementation.

As mainstream data warehouses are growing into the multi-terabyte range, adequate performance for decision support queries remains challenging for database query processors. Proper choice of query plan is essential in data warehouses where fact tables often store billions of rows. This paper discusses query optimization and execution strategies that Microsoft SQL Server employs for decision support queries in dimensionally modeled relational data warehouses. Our approach is based on pattern matching to detect typical star query patterns. When matching the pattern, the optimizer generates additional query plan alternatives specifically optimized for data warehouse performance. For high selectivity queries, the plans use nested loops joins and seeks. Medium selectivity queries in turn rely on right-deep hash joins with bitmap filters. Bitmap filters perform semi-join reductions to efficiently prune out non-qualifying rows early. Final plan choice is left for cost-based optimization which also compares the data warehouse specific plans against conventional query plans. We conducted an extensive experimental investigation using both synthetic workloads and several customer workloads. As our results show, the new plan shapes and execution strategies yield significant performance improvements across the targeted workloads as compared to earlier versions of Microsoft SQL Server.

Efficient support for applications that deal with data heterogeneity, hierarchies and schema evolution is an important challenge for relational engines. In this paper we show how this flexibility can be handled in Microsoft SQL Server. For this purpose, the engine has been equipped in an integrated package of relational extensions. The package includes sparse storage, column set operations, filtered indices, filtered statistics and hierarchy querying with OrdPath labeling. In addition, economical loading of metadata allow us to answer queries independently of the number of columns in a table and drastically improve scaling capabilities. The design of a prototypical content and collaboration application based on a wide table is described, along with experiments validating its performance.

XML is often used to represent objects that expose different sets of properties. This "property bag" scenario is a prominent use case for the XML support added to Microsoft SQL Server 2005. However, each property extraction in our initial implementation executed as a separate relational subquery. This was problematic since query performance became unacceptable even for small data sizes when returning an increasing number of properties. We addressed this problem by developing an interesting generalization of common subexpressions. This paper makes the following contributions: (1) it introduces an equivalence rewrite for relational query optimization to fold similar scalar subqueries. Several such subqueries are merged into a single equivalent multi-column subquery using both predicate disjunction and rowset pivoting. The rewrite operates at the logical operator level which makes it equally applicable to XML queries and SQL queries. (2) We explain how this optimization can be applied to the XML property bag scenario and how it has been implemented for the XML index in Microsoft SQL Server 2005. (3) An experimental investigation with Microsoft SQL Server 2005 studies the performance characteristics of the optimization. It shows that the optimization yields significant performance improvements - without limiting essential optimizer execution plan choices.

Optimizing SQL subqueries has been an active area in database research and the database industry throughout the last decades. Previous work has already identified some approaches to efficiently execute relational subqueries. For satisfactory performance, proper choice of subquery execution strategies becomes even more essential today with the increase in decision support systems and automatically generated SQL, e.g., with ad-hoc reporting tools. This goes hand in hand with increasing query complexity and growing data volumes, which all pose challenges for an industrial-strength query optimizer.

A rich set of concepts and techniques has been developed in the context of query processing for the efficient and robust execution of queries. So far, this work has mostly focused on issues related to data-retrieval queries, with a strong backing on relational algebra. However, update operations can also exhibit a number of query processing issues, depending on the complexity of the operations and the volume of data to process. Such issues include lookup and matching of values, navigational vs. set-oriented algorithms and trade-offs between plans that do serial or random I/Os.In this paper we present an overview of the basic techniques used to support SQL DML (Data Manipulation Language) in Microsoft SQL Server. Our focus is on the integration of update operations into the query processor, the query execution primitives required to support updates, and the update-specific considerations to analyze and execute update plans. Full integration of update processing in the query processor provides a robust and flexible framework and leverages existing query processing techniques.

There is considerable overlap between strategies proposed for subquery evaluation, and those for grouping and aggregation. In this paper we show how a number of small, independent primitives generate a rich set of efficient execution strategies —covering standard proposals for subquery evaluation suggested in earlier literature. These small primitives fall into two main, orthogonal areas: Correlation removal, and efficient processing of outerjoins and GroupBy. An optimization approach based on these pieces provides syntax-independence of query processing with respect to subqueries, i. e. equivalent queries written with or without subquery produce the same efficient plan.

Testing an SQL database system by running large sets of deterministic or stochastic SQL statements is common practice in commercial database development. However, code defects often remain undetected as the query optimizer's choice of an execution plan is not only depending on the query but strongly influenced by a large number of parameters describing the database and the hardware environment. Modifying these parameters in order to steer the optimizer to select other plans is difficult since this means anticipating often complex search strategies implemented in the optimizer.

Conventional database optimizers take full advantage of associativity and commutativity properties of join to implement efficient and powerful optimizations on select/project/join queries.However, only limited optimization is performed on other binary operators.In this article, we present the theory and algorithms needed to generate alternative evaluation orders for the optimization of queries containing outerjoins.Our results include both a complete set of transformation rules, suitable for new-generation, transformation-based optimizers, and a bottom-up join enumeration algorithm compatible with those used by traditional optimizers.

The outerjoin operator is currently available in the query language of several major DBMSs, and it is included in the proposed SQL2 standard draft. However, “associativity problems” of the operator have been pointed out since its introduction. In this paper we propose a shift in the intuition behind outerjoin: Instead of computing the join while also preserving its arguments, outerjoin delivers tuples that come either from the join or from the arguments. Queries with joins and outerjoins deliver tuples that come from one out of several joins, where a single relation is a trivial join. An advantage of this view is that, in contrast to preservation, disjunction is commutative and associative, which is a significant property for intuition, formalisms, and generation of execution plans.

The authors provide a nearly complete theory for reordering join/outerjoin queries. The theory is used to describe modular extensions that strengthen a conventional optimizer to handle nearly all select/project/join/outerjoin queries. Unlike previous work, these results are not limited to queries possessing a nice structure, or queries that are nicely represented in relational calculus. The theoretical results concern query simplification and reassociation using a generalized outerjoin.>

We determine when a join/outerjoin query can be expressed unambiguously as a query graph, without an explicit specification of the order of evaluation. To do so, we first characterize the set of expression trees that implement a given join/outerjoin query graph, and investigate the existence of transformations among the various trees. Our main theorem is that a join/outerjoin query is freely reorderable if the query graph derived from it falls within a particular class, every tree that “implements” such a graph evaluates to the same result.