The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Mar. 31, 2009
Filed:
Jul. 13, 2006
Peter Jay Haas, San Jose, CA (US);
Marcel Kutsch, Cologne, DE;
Volker Gerhard Markl, San Jose, CA (US);
Nimrod Megiddo, Palo Alto, CA (US);
Peter Jay Haas, San Jose, CA (US);
Marcel Kutsch, Cologne, DE;
Volker Gerhard Markl, San Jose, CA (US);
Nimrod Megiddo, Palo Alto, CA (US);
International Business Machines Corporation, Armonk, NY (US);
Abstract
The present invention provides a method of selectivity estimation in which preprocessing steps improve the feasibility and efficiency of the estimation. The preprocessing steps are partitioning (to make iterative scaling estimation terminate in a reasonable time for even large sets of predicates), forced partitioning (to enable partitioning in case there are no 'natural' partitions, by finding the subsets of predicates to create partitions that least impact the overall solution); inconsistency resolution (in order to ensure that there always is a correct and feasible solution), and implied zero elimination (to ensure convergence of the iterative scaling computation under all circumstances). All of these preprocessing steps make a maximum entropy method of selectivity estimation produce a correct cardinality model, for any kind of query with conjuncts of predicates. In addition, the preprocessing steps can also be used in conjunction with prior art methods for building a cardinality model.