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; after computing an execution plan for a first query of the queries, while accessing the pages to execute the first query, generating distinct page count information by counting a number of distinct pages accessed by the database engine specifically to execute the first query, where the generating is performed by the database engine, the distinct page count is a count of pages accessed during execution of the first query, the distinct page count not including any pages that were not accessed to execute the query, wherein pages accessed multiple times during and for execution of the first query are only counted one time in the distinct page count.