A database engine and a system running a database engine utilize a dynamic bitmap updating routine to avoid the delay associated with building an entire bitmap. When running a query on a table, the database engine can build a bitmap over a column of the table that helps avoid unnecessary I/O operations to retrieve records. The database engine initializes the bitmap so that all elements have a value of “1”, or active, and proceeds to scan and retrieve the records of the table according to the bitmap using a first process. Any retrieved record is further analyzed to determine if it is part of the result set. Concurrently, a second process is initiated which continually updates the values within the bitmap according to a set of selection criteria. As the first process continues to operate, more and more elements of the bitmap are set to “0”, or inactive, so that the first process can avoid unnecessary I/O operations.