Query Optimization

• US 20110093500A1
• Filed: 12/23/2010
• Published: 04/21/2011
• Est. Priority Date: 01/21/2009
• Status: Abandoned Application

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Giannandrea, John, Degener, Jutta, Meyer, Scott, Michener, Barak
• Application Number:
  US12/978,337
• Publication Number:
  US 20110093500A1
• Time in Patent Office: Days
• US Class Current: 707/774
• CPC Class Codes: G06F 16/972 Access to data in other repository systems, e.g. legacy data or dynamic Web page generation

Abstract

A new database design is implemented in which everything in the database is modeled with primitives, including the links and nodes for a graph tuple store. A query syntax provides a nested tree of constraints with a single global schema. Various optimization techniques for queries and replication techniques are also 10 described.

Claims

1. A computer-implemented method for performing a cost-based optimization that is applied to a universe of nested sets of identity constraints, where sets of identities represent a constraint having particular types and values that are combined into said sets, comprising the steps of:

generating a database query in a template-based query language, said query comprising primitives which comprise any of nodes in a graph and links that express relationships between said primitives, wherein each primitive has a type and a value, wherein a query results in a node returning corresponding first and second lists of candidates, said first list for a first link of a first type having a first value, and said second list for a second link of a second type having a second value;

performing a separate search to satisfy each of said links in said query by taking a candidate from said first list of candidates and checking said candidate from said first list against said second list of candidates, and simultaneously taking a candidate from said second list of candidates and checking said candidate from said second list against said first list of candidates;

computing at least a first few items in each of said first and second lists of candidates and recording how much this costs for each list in terms of an abstract count;

determining which of said first and second lists containing sets of candidates to use as a producer and which of said first and second lists to use as a checker based upon said abstract count;

returning a resulting a list of candidates for each link; and

intersecting said sets of candidates to resolve said query.

2. The method of claim 1, further comprising:

constraining resources invested in executing a resolution of each of said lists pursuant to a query execution with a budget granter;

wherein when execution of a resolution for a list overruns an allocated budget for said resolution, an indication is returned that said list does not have a resolution within said budget; and

if and when said budget is increased, execution of a resolution for said budget constrained list is resumed;

wherein an interruptible, budget-driven value function is provided to execute a portion of a query and return results back to a top level of a hierarchical tree as soon as possible and as accurately as possible.

3. The method of claim 2, further comprising:

providing a hierarchical constraint tree comprising a tree of data structures that describe a query, wherein each constraint is one of a plurality of branches of said tree, each branch comprising an iterator, wherein each said iterator is executed to determine a potential resolution for the constraint associated with said iterator and return a list therefor, wherein said iterators are executed in parallel, beginning at a lowest level in said hierarchy and proceeding, branch by branch, to a top level, terminus point in said hierarchy as said iterators resolve said associated constraints; and

ending execution of all of said iterators and returning a query result when a first path of iterators is finished processing to said top level.

4. The method of claim 3, further comprising:

freezing an iterator into a string form and storing said string; and

thawing said string to resume a query by retrieving said string form of said iterator, thus restoring all pointers in said iterator;

wherein a query executed by said iterator is resumed.

5. The method of claim 3, further comprising the steps of:

providing a write master;

replicating data from said write master into multiple read servers and clients that are connected to said read servers;

wherein if a cursor is returned by a read server in response to a query, once the cursor is received, either of;

a status is encoded inside said cursor, wherein when a cursor is sent to a read server, said read server is provided with sufficient information to find any records a querying client is paging through, wherein an optimization strategy is included in cursor; and

storing a state, sharing said state, or binding a user to one read server, and assuring that a user only communicates with a particular read server.

6. The method of claim 5, further comprising the steps of:

pausing execution of said query;

saving said paused query by converting each said iterators to a string form;

storing said strings; and

resuming execution of said query by converting said iterators from a string form back into iterators.

7. The method of claim 5, further comprising the steps of:

returning a desired portion of a total query result which is less than said total query result;

providing a cursor with said returned portion of said total query result, said cursor indicating that additional results exist;

said cursor temporarily suspending retrieval of said additional query results;

said processor configured for allowing execution of write operations during said temporary suspension; and

said processor configured for resuming said retrieval and returning said additional results upon presentation of said cursor.

8. The method of claim 5, further comprising the step of:

presenting a query to identify primitives that have been added since a previous query which was accompanied by a cursor.

9. The method of claim 8, wherein a cursor always encodes a particular virtual time, said particular virtual time comprising a time of said cursor'"'"'s creation, wherein execution of a cursor takes place as of said encoded virtual time, wherein results returned by a series of cursored queries are identical to results reviewed by a single query having a sufficiently large page size.

10. The method of claim 1, further comprising the steps of:

said processor configured for using iterators to resolve each of said query terms, beginning at a lowest hierarchical level, across all hierarchy branches;

wherein if said query terms are resolved, results for said query terms are passed up to a next hierarchical level, and iterators at said next hierarchical level are used to resolve said query terms;

if at a top hierarchical level it is determined that a query cannot be resolved, even if there is at least some resolution of some of the query terms at lower hierarchical levels, which resolution is not useful because it leads to a dead end, then either terminating query execution or continuing query execution, branch by branch, to said top hierarchical level until there is a complete query resolution; and

said processor configured for employing a budget function to establish a resource threshold and to determine, on a branch by branch basis, if excessive resources are being used to resolve the query, in which case resources are no longer applied to resolving the query and query execution is terminated;

else completing query execution for each branch that does not exceed said resource threshold.

11. The method of claim 10, further comprising the steps of:

using a primitive linkage and a set in connection with computing a new set comprising results obtained by looking up a specified linkage of every member of said set; and

computing a union of all linkages of said linkage specified for every member of said set.