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:
- a processor configured for formulating and presenting a database query in a template-based query language, said query terms 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;
said processor configured for 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;
said processor configured for 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;
said processor configured for deciding 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;
said processor configured for returning a resulting a list of candidates for each link; and
said processor configured for intersecting said sets of candidates to resolve said query.
5 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 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:
-
a processor configured for formulating and presenting a database query in a template-based query language, said query terms 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; said processor configured for 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; said processor configured for 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; said processor configured for deciding 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; said processor configured for returning a resulting a list of candidates for each link; and said processor configured for intersecting said sets of candidates to resolve said query. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
Specification