1. A computer implemented method performed by a database engine executing on a computing device, the database engine including a cost function for estimating the respective costs of executing different query plans for executing a requested query, the method comprising: executing queries by accessing pages, the pages comprising storage units managed by the database engine and which store rows of tables managed by the database engine; while accessing the pages to execute a first one of the queries, generating distinct page count information based on information about a number of distinct pages accessed when executing the query, where the generating is performed by the database engine.