US 11,636,108 B1Granted

Federated query optimization

AssigneeTableau Software, Inc.

InventorsLiqi Xu, Richard L. Cole, Daniel Ting

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method builds a regression model for predicting processing times for federated queries using a variety of data sources. The method includes obtaining federated queries (e.g., from benchmarks), and generates a plurality of federated query plans for each federated query. Each federated query plan corresponds to executing a respective federated query using a respective data source as the federation engine. The method includes forming feature vectors for each federated query plan based on cost estimations for executing the respective federated query plan and cost estimations for data transfer. The method further includes training a regression model, using the feature vectors for the plurality of federated query plans, to predict runtimes for executing federated queries using the variety of data sources as a federation engine. Some implementations use the trained regression model to determine a suitable federation engine for a given federated query.

Claims17

Dependent claims

A method of building a model for predicting runtimes of federated queries, performed at a computer system having one or more processors and memory storing one or more programs configured for execution by the one or more processors, the method comprising:

obtaining a plurality of federated queries, each federated query specifying retrieval of data from datasets stored in a respective plurality of data sources at distinct physical locations, each data source coupled to the other data sources via a communication network;
generating a respective plurality of federated query plans for each federated query, each federated query plan corresponding to executing a respective federated query using a respective data source as a federation engine, wherein:
each federated query plan includes a respective plurality of query operators and each query operator specifies retrieval of data from a respective dataset stored in a corresponding data source;
and
each federated query plan designates a respective federation engine that (i) controls and coordinates federation of data sources, (ii) receives data from other data sources, (iii) processes the received data, and (iv) returns final results for the respective federated query plan;
for each federated query plan, forming a feature vector ν=[ν1, ν2, . . . , νn] whose components include a plurality of features selected from the group consisting of:
a remote cost estimate for executing query operators of the respective federated query plan on data sources distinct from the respective data source;
a local cost estimate for executing query operators of the respective federated query plan on the respective data source;
and
a data transfer cost estimate for transferring partial results of the respective federated query plan, via the communication network, from data sources distinct from the respective data source to the respective data source;
and
training a regression model, using the feature vectors for the plurality of federated query plans, to predict runtimes for executing queries using each of the plurality of data sources as a federation engine.

9 more elements

A computer system, comprising:

one or more processors;
and
memory storing one or more programs for execution by the one or more processors, the one or more programs including instructions for:
obtaining a plurality of federated queries, each federated query specifying retrieval of data from datasets stored in a respective plurality of data sources at distinct physical locations, each data source coupled to the other data sources via a communication network;
generating a respective plurality of federated query plans for each federated query, each federated query plan corresponding to executing a respective federated query using a respective data source as a federation engine, wherein:
each federated query plan includes a respective plurality of query operators and each query operator specifies retrieval of data from a respective dataset stored in a corresponding data source;
and
each federated query plan designates a respective federation engine that (i) controls and coordinates federation of data sources, (ii) receives data from other data sources, (iii) processes the received data, and (iv) returns final results for the respective federated query plan;
for each federated query plan, forming a feature vector ν=[ν1, ν2, . . . , νn] whose components include a plurality of features selected from the group consisting of:
a remote cost estimate for executing query operators of the respective federated query plan on data sources distinct from the respective data source;
a local cost estimate for executing query operators of the respective federated query plan on the respective data source;
and
a data transfer cost estimate for transferring partial results of the respective federated query plan, via the communication network, from data sources distinct from the respective data source to the respective data source;
and
training a regression model, using the feature vectors for the plurality of federated query plans, to predict runtimes for executing queries using each of the plurality of data sources as a federation engine.

12 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/573,988Filed 17 Sep 2019 · us provisional application
Priority: 18 Mar 2019
Granted: 25 Apr 2023
Term ends: Not estimatedThe source records don’t support an estimate.

Classification7 codes

G06F 16/24545
Plan optimisation: selectivity estimation or determination
G06F 16/24537
Query rewriting; Transformation: of operators
G06F 16/256
Integrating or interfacing systems involving database management systems: in federated or virtual databases
G06N 5/04
Computing arrangements using knowledge-based models: inference or reasoning models