CONSISTENT AND UNBIASED CARDINALITY ESTIMATION FOR COMPLEX QUERIES WITH CONJUNCTS OF PREDICATES

摘要

A method of selectivity estimation is disclosed 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.