US 2006/0041537 A1 · Selecting candidate queries

Abstract

Iterative, linear, and exhaustive candidate selection techniques are described. In the techniques described herein, a set of semantically equivalent queries (also called a set of candidate queries) is determined for an incoming query based on a particular candidate selection technique. A choice is then made among the candidate queries, usually based on a cost measure, as to which query to execute or store for later execution. In one embodiment, there are multiple, available candidate selection techniques and before the set of candidate queries is determined, a choice of candidate selection techniques is made from among the available candidate selection techniques. The choice of candidate selection techniques may be made based on a configuration file or user input or based on some aspect of the query, the user, or the database on which the query will run.

Claims124

Dependent claims

A method of processing a query, comprising:

determining which particular candidate identification technique, of two or more candidate identification techniques available to a query-processing unit, to use to process the query;
wherein each candidate identification technique is a technique for identifying which semantically equivalent queries, of all possible semantically equivalent queries, will belong to a particular set of candidate queries;
determining an initial set of candidate queries for the query based on the particular candidate identification technique;
determining costs for one or more particular queries of the initial set of candidate queries;
choosing a particular query, from a set of candidate queries, based on costs for each query in the set of candidate queries, wherein the set of candidate queries includes the one or more particular queries;
and
responding to a request to execute the query by executing the particular query.

4 more elements

A method of processing a query, comprising:

receiving the query, wherein the query comprises one or more query blocks;
establishing a current-best query based on the query;
determining a set of candidate queries and costs corresponding to each candidate query in the set of candidate queries, wherein each candidate query in the set of candidate queries is determined based on the current-best query and an alternative state of a particular query block of the one or more query blocks, wherein if a particular cost associated with a particular candidate query satisfies a first particular mathematical relationship with a current-best cost for the current-best query, then the particular candidate query is established as the current-best query;
choosing a particular query from the set of candidate queries based on the costs for the candidate queries in the set of candidate queries;
and
responding to a request to execute the query by executing the particular query.

3 more elements

A method of processing a query, comprising:

receiving the query, wherein the query comprises one or more query blocks;
determining multiple starting queries based on the query and one or more heuristics;
for each starting query of the multiple starting queries:
establishing the starting query as a local-best query;
determining a set of candidate queries and costs for each query in the set of candidate queries, wherein each candidate query in the set of candidate queries is determined based on the local-best query and an alternative state for a particular query block of the one or more query blocks, and wherein, if a first cost for the candidate query satisfies a first particular mathematical relationship with a local-best cost for the local-best query, then establishing the candidate query as the local-best query;
choosing a particular query from a set of local-best queries based on costs for each query in the set of local-best queries, wherein the set of local-best queries comprises the local-best query for each set of candidate queries;
and
responding to a request to execute the query by executing the particular query.

5 more elements

Dependencies are inferred from the claim text.

Selecting candidate queries

Life of this patent

Selecting candidate queries

Life of this patent

Abstract

Claims124