Background index bitmapping for faster query performance
View Patent ↗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.
1. A computer-implemented method for executing a query that evaluates one or more records of a table according to predetermined selection criteria, comprising the steps of:
optimizing a query plan for the query by labeling the query as a candidate query for dynamic bitmap updating,
where optimizing the query plan for the query by labeling the query as a candidate query for dynamic bitmap updating further comprises before initializing a bitmap and startinq a first primary task and a second background task, determining if the query is labeled as the candidate query for dynamic bitmap updating;
when the query is labeled as the candidate query for dynamic bitmap updating then executing the steps of:
initializing a bitmap having a plurality of elements, each element of the bitmap corresponding to a record of the table, and each element initialized to an active value;
running the first primary task that individually retrieves each of one or more records from storage according to whether a corresponding element of the bitmap has an active value;
running, concurrently with the first primary task, a second background task that executes a same query as the first primary task and that updates the bitmap by setting an inactive value to the element of the bitmap corresponding to any record that does not satisfy at least a portion of the selection criteria, wherein running the second background task includes:
scanning a column of the table using an index built over the column; the portion of the selection criteria relating to record values within the column;
determining a set of records whose record values within the column do not satisfy the portion of the selection criteria; and
concurrently with the first primary task individually retrieving records from the storage having corresponding active value bitmap elements, changing the corresponding bitmap element to an inactive value for each record within the set of records; and
continuing to run the first primary task until all records from the table, having a corresponding active value bitmap element, have been retrieved from the storage, including accessing the bitmap in the first primary task before at least one element is set to an inactive value by the second background task to determine whether to retrieve a record from the storage.
2. The method according to claim 1 , wherein the step of running the first primary task includes the steps of:
determining if a retrieved record satisfies the selection criteria; and
returning, as part of a query result set, the retrieved record if the selection criteria is satisfied.
3. The method according to claim 1 , wherein the step of running the first primary task includes the steps of:
discarding any record having a corresponding bitmap element which has an inactive value, by not retrieving that record from the storage.
4. The method according to claim 1 , wherein a first order in which the one or more records is retrieved differs from a second order in which the column of the table is scanned.
5. The method according to claim 1 , further comprising the steps of:
collecting statistics relating to performance of executing the query; and
generating a recommendation presented to a user for creating a permanent index based on the statistics.