EXPLAIN EXTENDED

How to create fast database queries

Bitwise operations and indexes

with 2 comments

From Stack Overflow:

Are the following queries efficient in MySQL:

SELECT  *
FROM    table
WHERE   field & number = number
-- to find values with superset of number's bits
SELECT  *
FROM    table
WHERE   field | number = number
-- to find values with subset of number's bits

, if an index for the field has been created?

If not, is there a way to make it run faster?

An index can be used for the following things:

  1. To limit the number of records scanned
  2. To lower the number of row lookups

When doing a full table scan, every record should be fetched and examined. If the table contains say, 1,000,000 records, and each record is 100 bytes long, then 100 Mb worth of data should be processed. These data are usually scanned sequentially.

An index row, on the other hand, contains the key value, the row pointer and some additional information (pointers to the parents and children). On a MyISAM table, each row of the index on an INT column occupies 10 bytes (4 (sizeof(INT)) + 6 (default MyISAM pointer size)) plus some overhead (block headers, leaf pointers etc).

Even if we cannot build a range on the index and need to look over all index values, 10 Mb is far less than 100 Mb.

However, scanning the index has two drawbacks:

  1. Traversing the B-Tree is more slow than a full table scan, since the former is not sequential
  2. When the condition we search for matches the index key, we should follow the pointer to fetch the unindexed values from the table row. This also takes some time.

Both these things can be optimized:

  • Oracle has INDEX FAST FULL SCAN access method. It scans the index rows in their physical order, not logical. The key order is not maintained in such a scan, but we not always need it anyway.

    This makes the index scanning sequential (and taking the constant time)

  • PostgreSQL has bitmap access method. PostgreSQL cannot disregard the index order as Oracle does so it has to traverse the tree anyway. But instead of following the pointer to fetch the values it fills a special bitmap with a bit set for each matching row.

    The order of bits corresponds to the physical order of rows.

    When it's over with setting bits it just reads the bitmap and fetches the rows with the bits set. Since the bits are ordered, the rows fetched are ordered too, so this scan is also sequential. Scanning the bitmap takes constant time (which is usually negligible since bitmaps are very small), pure time for fetching the rows depends on the number of bits set but is no longer than a full scan (since the scan is sequential).

MySQL, however, does neither of these optimizations.


Let's see what the query time depends on:

  • Table scan time is constant. It depends on the row size.
  • Index time varies and depends on the following parameters:

    • Index scan time depends on whether the condition is sargable:

      • Yes, The index scan time depends on the range size.
      • No. The index scan time is constant.
    • Pointer dereference time depends on the number of rows inside the range

Not that the range and the condition are not always the same thing. A condition can be a subset of range.

For instance, for a table with natural numbers a condition like this:

a BETWEEN 0 AND 999 AND a % 100 = 0

will be sargable, but the range and the filter return different subset of values. The range contains 1,000 values, but the filter returns only 10 of them.

MySQL, however, cannot benefit from this difference. It always fetches the row from the table if an unindexed value is used in a SELECT clause, even if the condition uses only the columns covered by the index.

Say, if MySQL uses the index and fetches the value 1, it could look at this value, see that is does not satisfy the condition (1 % 100 <> 0) and avoid using the row pointer to fetch the table record.

But MySQL always fetches the table row, no matter what. It performs an inefficient early table lookup.

Formulae

Summarizing all said above, here are the formulae to calculate the time:

Table scan

Time = T * R

  • T is the number of rows in the table
  • R is the single row scan time

Index scan

Time = R * (K + I + D)

  • R is the number of rows in the index range. If the condition is not sargable, R is equal to T above (all rows should be scanned)
  • K is the key scan time. It depend on the size of the index key. It is almost always less than R above
  • I is the index traversal time (the extra time to find the next index record)
  • D is the row pointer dereference time

While K alone is usually less than R, I and D are quite large, so K + I + D is almost always greater then R.

That means that to benefit from the index, we should make R significantly smaller than T, i. e we should make our condition sargable and the range part selective.

Sample table

Now, let's create a sample table and see the real numbers:

Table creation details

The table has 1,000,000 records with random values in two columns.

The first column, ivalue, is indexed, the second one, pvalue, is not. The values are the same in both columns.

Let's try to query the unindexed column:

SELECT  id, pvalue, ivalue, data
FROM    t_bit
WHERE   pvalue | 0x0000FFFF = 0x0000FFFF

View query details

This uses full table scan and completes in 750 ms

Now, same with the indexed column (and the index forced):

SELECT  id, pvalue, ivalue, data
FROM    t_bit FORCE INDEX (ix_bit_ivalue)
WHERE   ivalue | 0x0000FFFF = 0x0000FFFF
        AND ivalue >= 0

View query details

This way it takes 11,82 seconds.

Now we can see that scanning an index records is about 15 times as expensive as scanning a MyISAM table record. That means that the index range should contain at most 6% of records to benefit from the index.

How can we make the condition sargable?

Subset

Let's see what happens when we search for a subet of rows (a bitwise OR).

The result of bitwise OR of the field and the number should give the number back. That means that the bits set to 0 should be the same in field and the number. A field can have anything in bits set to 1 in number.

If we have first N bits set to 0 in number this means that the first N bits should be set to 0 in the field just as well.

But this means that the field should be less or equal to the maximum number with the first bits sets to 0. This number of course should have all other bits set to 1 (that is what makes it the maximum), and, therefore, be by one less than a power of two. And yes, this is a range and an index can be used to limit the number of records to browse.

To calculate this number, we shoud just find this power of two and subtract the 1 from it.

Here's the query:

SELECT  id, pvalue, ivalue, data
FROM    t_bit FORCE INDEX (ix_bit_ivalue)
WHERE   ivalue | 0x0000FFFF = 0x0000FFFF
        AND ivalue <= 2 << FLOOR(LOG(2, 0x0000FFFF) + 1) - 1

View query details

The index limits the range so that only 16 rows are eligible. Since the index range and the filtering condition are the same in this query, all of there records are returned.

The query takes only 2 ms.

Superset

The superset as the name suggests tend to return more values than a subset. Now, the condition is reversed: the field should have a 1 in the bits with a 1 in number, and anything in those with a 0.

This imples that the field should have al least as many leading bits set as the number does:

1111 0110 1011 1010 1010 1011 0101 1010 -- number
1111 ???? ???? ???? ???? ???? ???? ???? -- field

The lower bound of the range can be found by taking a logarithm of the power of two closest to the bitwise complement of the number:

SELECT  id, pvalue, ivalue, data
FROM    t_bit FORCE INDEX (ix_bit_ivalue)
WHERE   ivalue & 0xFFFF0000 = 0xFFFF0000
        AND ivalue >= 0xFFFFFFFF & ~((2 << FLOOR(LOG(2, 0xFFFFFFFF & ~0xFFFF0000))) - 1)

View query details

This takes only 2 ms too.

We see that adding the range condition to the query improves performance it the field is indexed.

Range

But will any range condition improve the performance?

Since we calculated that scanning a row using index access is 15 times as costly as the table scan, the range should have at least 15 times as few records as the table does.

This means that the range is good only for the numbers with at least 4 bits unset at the beginning (for OR queries) or at the end (for AND queries)

Let's check it:

SELECT  id, pvalue, ivalue, data
FROM    t_bit FORCE INDEX (ix_bit_ivalue)
WHERE   ivalue | 0x09876543 = 0x09876543
        AND ivalue <= 2 << FLOOR(LOG(2, 0x09876543) + 1) - 1

View query details

This query takes 0.93 second which is about same efficiency as the full table scan (0.75 second), since exactly 4 bits are unset at the beginning of the number we compare to.

If more bits are set to 0 at the beginning, the index scan is more efficient. If less, then the table scan is more efficient.

Same holds for AND queries too, but the bits should be counted starting from the end.

Written by Quassnoi

October 1st, 2009 at 11:00 pm

Posted in MySQL

2 Responses to 'Bitwise operations and indexes'

Subscribe to comments with RSS

  1. Thank you for you article! I was looking for a simple way to make requests with bitwise operations faster (i’m using an OR subset) and found my answer!

    Jean

    9 Feb 13 at 01:20

  2. someone, buy this guy a beer.

    dang

    14 Jun 14 at 14:03

Leave a Reply