Where are my bits? Custom Oracle Bitmap Indexing

Stephane Come
Jul 27, 2017 · 4 min read

I was recently working on a query to search a multiple choices medical survey database. In this scenario, the end user could provide any combination of answers and the query would need to find all the matching combinations out of a set of millions of records. The only caveat was that I couldn’t make any structural changes to the existing data model, but was allowed to add additional supporting objects or indexes as deemed necessary.

The data model was fairly simple. A main table of all surveys, a table of all answers and a lookup table with all predefined questions and answers. Using all available out of the box Oracle indexing methods and/or table scans, joins, etc. the best query was always returning between 4 and 6 seconds. I wasn’t really thrilled about the performance and started to think there must be a better way — and there was… by a factor of 100.

The Aha moment came while I was designing lessons in coding micro-controllers and electronics for kids ages 9–12. In these lessons, I outline some basic types of computing logic using a comic book format. When working with micro-controllers, you have to set and clear bits in various registers and minimize your memory usage. In this environment, your entire code base needs to fit in 4K or 8K of flash space and your variables in 256 bytes of RAM. Quite different from my day job. Yet by applying the same basic principles and methods, I was able to make my Oracle queries much more efficient. Keep reading to find out how.

Programming an AVR micro-controller with kids

Setting the bits

What if… I mapped each response from the existing lookup table into a single logical bit. Each predefined response would be assigned a particular bit position for the specific question/answer. For example, let’s take question #3, Training Status. This question has 3 possible answers as shown below:

Mapping rows into single bits

By assigning each answer to a bit, we can now store the actual answer as a single 32 bit integer in a new table (instead of multiple rows). Say, the answer was 885, the value to store would be 4. For multiple choice answers, we can simply add all the bits into a single integer. If all 3 answers were selected, the value to store would be 7.

By converting all the answers into bits and storing the values into 32 bit integers, the complete set of answers uses only 1,680 blocks in the database as opposed to the current 28,200 blocks (or 13MB vs. 231MB).

Searching for bits

The real efficiency (besides storage) comes down in the execution of the queries searching for the matching surveys. To find a survey, we simply need to scan the entire table and return any rows having these specific bits set.

Here is a view of how the answers are stored. Each bit set will be added to the total for the question (single column) and a single numerical value is stored. In the example below, the license identifier 898695 stores the integer value of 715,827,880 and contains 14 answers for question #3.

When searching the survey using this custom bitmap index, we are looking for any combination where the two bits are set using Oracle’s BITAND operator. In the above example, we were looking for any all licenses having their answer bits 4 and 8 set regardless of the other ones. An efficient match is made by applying our BITAND filter.

When FTS stands for FAST

The final SQL statement is built dynamically. Each search criteria is an additional “AND” clause added to the SQL predicate. Because of the full table scan (FTS) nature of the execution, the response time to scan 1,680 blocks is constant and averages less than 50ms regardless of the number of matches.

Using indexes is not always the best and fastest method. Full table scans have their strengths when used properly.

I’ve always been fascinated by Oracle performance tuning since I started with Oracle 6.0. The optimizer has come a long way since its introduction in my early days as a database administrator. Yet, there is no replacement for good database design in the first place if you want your application to be fast.

Thank you for reading. If you enjoyed this article, it would mean the world if you could like/comment on it. If you want to teach your kids coding and electronics like the old days and think like this article, check out my work at PodPi.com.

Stephane Come

Written by

An adventure from the resistor to the Cloud.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade