Selectivity estimation in the presence of alphanumeric correlations

Query optimization is an integral part of relational database management systems. One important task in query optimization is selectivity estimation, that is, given a query P, one needs to estimate the fraction of records in the database that satisfy P. Almost all previous work dealt with the estimation of numeric selectivity, i.e., the query contains only numeric variables. The general problem of estimating alphanumeric selectivity is much more difficult and has attracted attention only very recently, and the focus has been on the special case when only one column is involved. The authors consider the more general case when there are two correlated alphanumeric columns. They develop efficient algorithms to build storage structures that can fit in a database catalog. Results from extensive experiments to test the algorithms, on the basis of error analysis and space requirements, are given to guide DBMS implementors