Incremental cardinality estimation for a set of data values

摘要

A method for incrementally maintaining column cardinality estimates in database management systems. In one embodiment, the system includes system catalog table containing a cardinality estimate for a column that is extended to include an appropriate data structure. A modified linear counting technique is used in a first embodiment of a method for column cardinality estimation. The cardinality estimate is produced by an initial scan of the data but is then further maintained without requiring a full scan of the data. Data changes are reflected incrementally in modifications to the initial cardinality estimate, keeping the cardinality statistics more current with respect to the database condition. The technique of the invention typically provides a capability for a database management system to produce more efficient search plans providing more effective responses to user queries through the use of improved cardinality statistics.