Microsoft Technology Licensing, LLC

Wentao Wu

Surajit J Chaudhuri

Vivek Ravindranath Narasayya

Rahul Potharaju

Tarique Ashraf Siddiqui

Terry Yumin Kim

Chi Wang

Lev Novik

Philip Alan Bernstein

Apoorve Dave

Sudipto Das

Bailu Ding

Walter Zhen Cai

Xiaoying Wang

Alexander Raizman

Saehan Jo

Matteo Brucato

This disclosure describes a workload reduction system that reduces the complexity of workloads sent to a database system. For instance, the workload reduction system pre-processes workloads sent to a database system by generating reduced workloads that include less complex queries that reference fewer tables or columns than the original workloads. In various implementations, the workload reduction system uses table reduction functions and query re-writing functions to generate the reduced workloads. As a result, the workload reduction system improves computational efficiency by rewriting complex queries from workloads into simpler ones that speed up index tuning and decrease individual what-if call times.

Using workload reduction to improve index tuning

This document relates to budget-constrained index tuning in database systems. A method for index tuning within a database system includes receiving a budget constraint, generating a set of candidate indexes for a workload of queries, and determining a derived cost for each query-configuration pair (QCP). The method further involves identifying a subset of QCPs where the derived cost and a what-if cost have a delta value below a predefined difference threshold and allocating the budget constraint to these identified QCPs to avoid what-if calls. Additionally, the method reallocates a saved portion of the budget constraint to other QCPs where the delta value exceeds the difference threshold, evaluates these other QCPs using what-if calls to select an optimal index configuration, and applies the selected index configuration to the database system.

Budget-constrained index tuning in database systems

A method of training an index filter for an index tuning system includes receiving a plurality of different workloads and a plurality of different databases, each database including different tables and each workload including a plurality of queries; generating labeled training by making optimizer calls to a query optimizer using query and index configuration pairs from the plurality of databases and the plurality of workloads; training an index filter model to identify signals in the labeled training data, the signals being indicative of a potential performance improvement associated with using an index configuration for a given query; training the index filter model to learn rules over the signals for identifying spurious indexes; and storing the index filter model in a memory.

Scalable index tuning with index filtering and index cost models

The present disclosure relates to methods and systems for compressing workloads for use with index tuning. The methods and systems receive a workload with a plurality of queries. The methods and systems represent each query using query features and a utility. The methods and systems select a query for a query subset based on a benefit of the query determined using the query features and the utility. The methods and systems update the features and the utility of the remaining queries in the workload and select another query to add to the query subset based on an updated benefit determined using the updated features and utilities. The methods and systems select queries for the query subset equal to a received query subset size. The methods and systems use the query subset in index tuning to provide one or more indexes to recommendations.

Compressing workloads for scalable index tuning

The present disclosure relates to systems, methods, and computer-readable media for determining optimal index configurations for processing workloads in a database management system. For instance, an index configuration system can efficiently determine a subset of indexes for processing a workload utilizing one or more reinforcement learning models. For example, in various implementations, the index configuration system utilizes a Markov decision process and/or a Monte Carlo tree search model to determine an optimal subset of indexes for processing a workload in a manner that effectively utilizes computing device resources while also avoiding significant interference with customer workloads.

Constraint-based index tuning in database management systems utilizing reinforcement learning

Methods, systems and computer program products are described herein that provide a serverless, multi-engine, multi-user data lake indexing subsystem and application programming interface. Indexes are defined as derived datasets and stored on the data lake in a universal format that enables disparate engines to create and/or discover indexes for workload optimization. Embodiment of indexes enable stateful control and management of an index via metadata included in the index and stored on the data lake.

Serverless data lake indexing subsystem and application programming interface

Methods, systems, apparatuses, and computer program products are described herein for the generation and traversal of a hierarchical index structure. The structure indexes search keys from data ingested from different data sources and enables efficient retrieval of the keys. As data is ingested, index nodes are generated at the lowest level of the structure. The nodes are analyzed to determine whether such nodes comprise duplicate keys. Responsive to doing so, a new index node is generated located at a higher level of the structure. This process results in a DAG comprising orphan nodes including different search keys. When processing a query for search keys, the orphan index nodes are initially analyzed for the keys. Upon finding a search key, its child nodes are recursively searched until location information specifying the location of ingested data in which the search key is located is found.

Generation and traversal of a hierarchical index structure for efficient data retrieval

Methods, systems, apparatuses, and computer program products are directed to the generation of a global index structure. Agents executing on different data sources locally pre-process (e.g., format, filter, compress, encode, serialize etc.) data generated thereby and index such data. The agents also manage the resources thereof to perform the pre-processing and indexing operations. Each index generated by an agent is formatted as a plurality of index nodes. The index nodes and pre-processed data are provided to backend server(s) that maintain the global index structure and store the data in a globally distributed file system, which aid in unexpected disaster recovery. The backend server(s) generate the global index structure based on the index nodes. As new index nodes are received by the backend servers, the backend servers merge the newly-received index nodes with the global index structure. Global index structure traversal techniques for retrieving search keys are also described herein.

Agent-based data pre-processing and data indexing for efficient data retrieval

Methods, systems, apparatuses, and computer program products are provided for determining a query plan. A query is received that comprises a request for a data result for each of a plurality of original time windows. The plurality of original time windows included in the query are identified. An initial window representation is generated that identifies a set of connections between windows in a window set that includes at least the original time windows. A revised window representation is generated that includes an alternative set of connections between windows in the window set based at least on an execution cost for at least one window. The revised window representation is selected to obtain the data result for each of the plurality of original time windows. A revised query plan based on the revised window representation is provided to obtain the data result for each of the plurality of original time windows.

Optimizing aggregates over correlated windows in a stream-query system

Methods, systems and computer program products are described herein that enable data workload optimization through 'what-if' modeling of indexes and index recommendation. In an example aspect, a system is configured to accept a workload comprising a plurality of queries directed at data having a first physical data layout, generate a set of candidate indexes based on the plurality of queries, enumerate index configurations based of the set of candidate indexes, each index configuration comprising a subset on the set of candidate indexes, generate a hierarchical graph of the index configurations, search the hierarchical graph for a recommended index configuration comprising an index configuration with the lowest estimated cost while pruning index configurations not considered from the graph of index configurations to generate a pruned graph, execute a graph query against the pruned graph generating a graph query result and perform an optimization operation based on the graph query result.

Data lake workload optimization through explaining and optimizing index recommendations

Methods, systems and computer program products are described herein that enable data workload optimization through 'what-if' modeling of indexes and index recommendation. In an example aspect, a system is configured to accept a workload in the form of a plurality of data queries, extract indexable columns from the queries, generate candidate indexes from the indexable columns, select and then build the best candidate indexes. Furthermore, the system may receive a query, generate a query plan for the query configured to use one or more of the built candidate indexes, and execute the query plan to generate a query result.

Data lake workload optimization through index modeling and recommendation

This application describes a data stream processing system for receiving and processing multiple data streams using a stream join model and based on the stream join model having a threshold function for which an output of the stream join model crosses the threshold two or less times (e.g., where the threshold function is a convex function, linear function, monotonic function, or other function having a similar property). The data stream processing system may generate filtered data streams using a number of techniques and algorithms without risk of false negatives and mis2169sing instances where an output of a stream join exceeds or violates a threshold condition. The data stream processing system can significantly reduce processing expense, particularly in cases where one or more devices have limited memory and where caching tuples from incoming data streams consumes significant processing resources.

Optimizing input streams for a stream join model having a threshold function

Systems, methods, and computer-executable instructions for creating a query execution plan for a query of a database includes receiving, from the database, a set of previously executed query execution plans for the query. Each previously-executed query execution plans includes subplans. Each subplan indicates a tree of physical operators. Physical operators that executed in the set of previously-executed query execution plans are determined. For each physical operator, an execution cost based is determined. Invalid physical operators from the previously-executed query execution plans that are invalid for the database are removed. Equivalent subplans from the previously-executed query execution plans are identified based on physical properties and logical expressions of the subplans. A constrained search space is created based on the equivalent subplans. A query execution plan for the query is constructed from the constrained search space based on the execution cost. The constructed query execution plan is not within the previously-executed query execution plans.

Growing community of inventors

Bellevue, WA, United States of America

Wentao Wu