Optimizing multi-predicate selections on a relation using indexes
AssigneeMicrosoft Corporation
InventorsPrasana Ganesan, Surajit Chaudhuri
Life of this patent
Estimating the term…
Abstract
Methods of optimizing access to a relation queried through a number of predicates. The methods identify one or more candidate predicates of the selection condition that can be used to factorize the selection condition. A gain from using one or more of the candidate predicates to factorize the selection condition is computed. One or more of the candidate predicates that result in a positive gain are factored from the selection condition to produce a rewritten selection condition. The candidate predicates can be predicates that appear exactly in the selection condition more than once and/or merged predicates that may be predicates in the selection condition that overlap.
Claims75
In a relational database having records stored on a medium, a computer-implemented method of optimizing processing of a query with a record selection condition that includes a number of predicates, comprising:
- a) identifying one or more candidate predicates of the selection condition that can be used to factorize the selection condition;
- b) computing a gain from using a candidate predicate to factorize the selection condition;
- c) factorizing a candidate predicate that results in a positive gain from said selection condition to produce a rewritten selection condition;
- and
- d) processing said query with said rewritten selection condition.
In a database having records stored on a medium, a computer-implemented method of optimizing processing of a query with a record selection condition that includes a number of predicates, comprising:
- a) identifying one or more merged predicates produced by the union of overlapping predicates of the selection condition that can be used to factorize the selection condition;
- b) computing a gain from using a candidate merged predicate to factorize the selection condition;
- c) substituting the merged predicate that results in a positive gain for overlapping predicates used to produce the merged predicate being substituted;
- d) factorizing the merged predicate substituted for overlapping predicates from said selection condition to produce a rewritten selection condition;
- and
- e) processing said query with said rewritten selection condition.
In a database having records stored on a medium, a computer-implemented method of optimizing processing of a query with a record selection condition that includes a number of predicates, comprising:
- a) identifying a set of predicates on a given attribute;
- b) identifying overlapping predicates in the set;
- c) producing merged predicates by the union of overlapping predicates in the set;
- d) identifying one or more merged predicate that produce a greater gain than the overlapping predicates used to form the candidate merged predicates;
- e) adding the one or more candidate merged predicates to said set of predicates;
- f) selecting a predicate from said set that produces the greatest gain;
- g) factorizing the predicate selected from the set from said selection condition to produce a rewritten selection condition;
- and
- h) processing said query with said rewritten selection condition.
In a database having records stored on a medium, a computer-implemented method of optimizing processing of a query with a selection condition that includes a number of predicates, comprising:
- a) identifying an exact factor predicate that is an exact factor of the selection condition and produces a gain when used to factorize the selection condition;
- b) identifying a merged predicate produced by the union of overlapping predicates of the selection condition that produces a gain when used to factorize the selection condition;
- c) determining which of the exact factor predicate and the merged predicate produces a greater gain when used to factorize the selection condition;
- d) factorizing the exact factor predicate from said selection condition to produce a rewritten selection condition when said exact factor predicate produces said greater gain;
- e) factorizing the merged predicate from said selection condition to produce a rewritten selection condition when said merged predicate produces said greater gain;
- and
- f) processing said query with said rewritten selection condition.
A computer readable medium having computer executable instructions stored thereon for performing a method of optimizing processing of a query with a selection condition that includes a number of predicates, the method comprising:
- a) identifying one or more candidate predicates of the selection condition that can be used to factorize the selection condition;
- b) computing a gain from using a candidate predicate to factorize the selection condition;
- c) factorizing a candidate predicate that results in a positive gain from said selection condition to produce a rewritten selection condition;
- and
- d) processing said query with said rewritten selection condition.
A computer readable medium having computer executable instructions stored thereon for performing a method of optimizing processing of a query with a selection condition that includes a number of predicates, the method comprising:
- a) identifying one or more merged predicates produced by the union of overlapping predicates of the selection condition that can be used to factorize the selection condition;
- b) computing a gain from using a candidate merged predicate to factorize the selection condition;
- c) substituting the a merged predicate that results in a positive gain for overlapping predicates used to produce the merged predicate being substituted;
- d) factorizing the merged predicate substituted for overlapping predicates from said selection condition to produce a rewritten selection condition;
- and
- e) processing said query with said rewritten selection condition.
A computer readable medium having computer executable instructions stored thereon for performing a method of optimizing processing of a query with a selection condition that includes a number of predicates, the method comprising:
- a) identifying a set of predicates on a given attribute;
- b) identifying overlapping predicates in the set;
- c) producing merged predicates by the union of overlapping predicates in the set;
- d) identifying one or more merged predicate that produce a greater gain than the overlapping predicates used to form the candidate merged predicates;
- e) adding the one or more candidate merged predicates to said set of predicates;
- f) selecting a predicate from said set that produces the greatest gain;
- g) factorizing the predicate selected from the set from said selection condition to produce a rewritten selection condition;
- and
- h) processing said query with said rewritten selection condition.
A computer readable medium having computer executable instructions stored thereon for performing a method of optimizing processing of a query with a selection condition that includes a number of predicates, the method comprising:
- a) identifying an exact factor predicate that is an exact factor of the selection condition and produces a gain when used to factorize the selection condition;
- b) identifying a merged predicate produced by the union of overlapping predicates of the selection condition that produces a gain when used to factorize the selection condition;
- c) determining which of the exact factor predicate and the merged predicate produces a greater gain when used to factorize the selection condition;
- d) factorizing the exact factor predicate from said selection condition to produce a rewritten selection condition when said exact factor predicate produces said greater gain;
- e) factorizing the merged predicate from said selection condition to produce a rewritten selection condition when said merged predicate produces said greater gain;
- and
- f) processing said query with said rewritten selection condition.
Dependencies are inferred from the claim text.