Query Optimization
First Claim
Patent Images
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
11 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
Specification