Method and database computer system for performing a database query using a bitmap index

A method for performing a database query using a bitmap index in a database having a plurality of bitmap vectors, the method comprising the steps of:

• upon receipt of a query containing a selection condition, creating a filter bitmap based on the query input;
• performing a bitmap scan for the filter bitmap in order to determine at least one value of an existing matching database entry;
• determining a bitmap of the determined at least one value;
• creating a filtered bitmap by combining the filter bitmap with the bitmap of the determined at least one value;
• determining all entries in the database matching the filtered bitmap;
• subtracting the filtered bitmap from the filter bitmap, thus creating a new filter bitmap;
• repeating the steps, starting with the step of performing a bitmap scan based on the new filter bitmap, until the step of subtracting results in an empty bitmap;
• wherein the steps are performed by a database computer system.

A method for performing a database query using a bitmap index in a database having a plurality of bitmap vectors, the method comprising the steps of:

• 1. upon receipt of a query containing a selection condition, creating a first level filter bitmap (r1) based on the query input;
• 2. determining a number of iteration levels 1 to n depending on the number of column stores contained in the database, n being an integer number >1;
• 3. performing a bitmap scan for the first level filter bitmap (r1) in order to determine a value (v1) of an existing matching database entry;
• 4. determining a second level filter bitmap (r2) of the determined value (v1) by combining the first level filter bitmap (r1) with the bitmap of the determined value (v1);
• 4a. repeating the steps of performing a bitmap scan for the xth level filter bitmap (rx) and determining a xth level filter bitmap (rx) until the nth level filter bitmap, with x=2 to n, the nth level filter bitmap constituting a filtered group bitmap (ba);
• 5. determining all entries in the database matching the filtered group bitmap (ba);
• 6. subtracting the filtered group bitmap (ba) from the nth level filter bitmap (rn), thus creating a new nth level filter bitmap;
• 4b. repeating the steps on the nth level, starting with the step of performing a bitmap scan based on the new filter bitmap (rn), until the step of subtracting results in an empty nth level filter bitmap;
• 4c. repeating above steps 6, 4a, 5, 6, 4b for each consecutive lower level filter bitmap (ry), with y=n−1 to 1, until the step of subtracting results in an empty l′ level filter bitmap;
• outputting the entires as a search result for the query.
• wherein the steps are performed by a database computer system.

A database computer system comprising:

• a column or row store database;
• a bitmap index storage;
• a computing means operably connected with the database and the bitmap index storage, the computing means further comprising a processor with an internal memory for performing a database query based on a search query received via the input device;
• the internal memory comprising a computer program with program coding means which are suitable for carrying out, when the computer program is run on a computer, and using a bitmap index in the database having a plurality of bitmap vectors, the bitmap index being stored in the bitmap index storage:
• upon receipt of a database query containing a selection condition, creating a filter bitmap based on the query input;
• performing a bitmap scan for the filter bitmap in order to determine at least one value of an existing matching database entry;
• determining a bitmap of the determined at least one value;
• creating a filtered bitmap by combining the filter bitmap with the bitmap of the determined at least one value;
• determining all entries in the database matching the filtered bitmap;
• subtracting the filtered bitmap from the filter bitmap, thus creating a new filter bitmap;
• repeating the steps, starting with the step of performing a bitmap scan based on the new filter bitmap, until the step of subtracting results in an empty bitmap;
• and
• outputting the entires as a search result for the search query.