Planet MySQL :: Planet MySQL - Archives - Bitwise operations and indexes

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:

To limit the number of records scanned
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:

Traversing the B-Tree is more slow than a full table scan, since the former is not sequential
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

CREATE TABLE filler (
        id INT NOT NULL PRIMARY KEY AUTO_INCREMENT
) ENGINE=Memory;

CREATE TABLE t_bit (
        id INT NOT NULL PRIMARY KEY,
        ivalue INT UNSIGNED NOT NULL,
        pvalue INT UNSIGNED NOT NULL,
        data VARCHAR(20) NOT NULL,
        stuffing VARCHAR(200) NOT NULL,
        KEY ix_bit_ivalue (ivalue)
) ENGINE=MyISAM;

DELIMITER $$

CREATE PROCEDURE prc_filler(cnt INT)
BEGIN
        DECLARE _cnt INT;
        SET _cnt = 1;
        WHILE _cnt <= cnt DO
                INSERT
                INTO    filler
                SELECT  _cnt;
                SET _cnt = _cnt + 1;
        END WHILE;
END
$$

DELIMITER ;

START TRANSACTION;
CALL prc_filler(1000000);
COMMIT;

INSERT
INTO    t_bit
SELECT  id, value, value, CONCAT('Value ', value), RPAD('', 200, '*')
FROM    (
        SELECT  id, FLOOR(RAND(20091001) * 0xFFFFFFFF) AS value
        FROM    filler
        ) q;

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

id	pvalue	ivalue	data
48638	9536	9536	Value 9536
63935	60976	60976	Value 60976
105238	20192	20192	Value 20192
117644	29156	29156	Value 29156
435300	62924	62924	Value 62924
449691	33508	33508	Value 33508
461927	9964	9964	Value 9964
626034	45356	45356	Value 45356
645275	45136	45136	Value 45136
671981	33796	33796	Value 33796
699265	49996	49996	Value 49996
775233	48340	48340	Value 48340
821626	64796	64796	Value 64796
822145	49996	49996	Value 49996
828424	45608	45608	Value 45608
972209	63640	63640	Value 63640
16 rows fetched in 0.0006s (0.7500s)

id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	t_bit	ALL					1000000	100.00	Using where

select `20091001_bit`.`t_bit`.`id` AS `id`,`20091001_bit`.`t_bit`.`pvalue` AS `pvalue`,`20091001_bit`.`t_bit`.`ivalue` AS `ivalue`,`20091001_bit`.`t_bit`.`data` AS `data` from `20091001_bit`.`t_bit` where ((`20091001_bit`.`t_bit`.`pvalue` | 0x0000ffff) = 0x0000ffff)

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

id	pvalue	ivalue	data
48638	9536	9536	Value 9536
461927	9964	9964	Value 9964
105238	20192	20192	Value 20192
117644	29156	29156	Value 29156
449691	33508	33508	Value 33508
671981	33796	33796	Value 33796
645275	45136	45136	Value 45136
626034	45356	45356	Value 45356
828424	45608	45608	Value 45608
775233	48340	48340	Value 48340
699265	49996	49996	Value 49996
822145	49996	49996	Value 49996
63935	60976	60976	Value 60976
435300	62924	62924	Value 62924
972209	63640	63640	Value 63640
821626	64796	64796	Value 64796
16 rows fetched in 0.0009s (11.8590s)

id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	t_bit	range	ix_bit_ivalue	ix_bit_ivalue	4		1000000	100.00	Using where

select `20091001_bit`.`t_bit`.`id` AS `id`,`20091001_bit`.`t_bit`.`pvalue` AS `pvalue`,`20091001_bit`.`t_bit`.`ivalue` AS `ivalue`,`20091001_bit`.`t_bit`.`data` AS `data` from `20091001_bit`.`t_bit` FORCE INDEX (`ix_bit_ivalue`) where (((`20091001_bit`.`t_bit`.`ivalue` | 0x0000ffff) = 0x0000ffff) and (`20091001_bit`.`t_bit`.`ivalue` >= 0))

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

id	pvalue	ivalue	data
48638	9536	9536	Value 9536
461927	9964	9964	Value 9964
105238	20192	20192	Value 20192
117644	29156	29156	Value 29156
449691	33508	33508	Value 33508
671981	33796	33796	Value 33796
645275	45136	45136	Value 45136
626034	45356	45356	Value 45356
828424	45608	45608	Value 45608
775233	48340	48340	Value 48340
699265	49996	49996	Value 49996
822145	49996	49996	Value 49996
63935	60976	60976	Value 60976
435300	62924	62924	Value 62924
972209	63640	63640	Value 63640
821626	64796	64796	Value 64796
16 rows fetched in 0.0006s (0.0025s)

id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	t_bit	range	ix_bit_ivalue	ix_bit_ivalue	4		14	100.00	Using where

select `20091001_bit`.`t_bit`.`id` AS `id`,`20091001_bit`.`t_bit`.`pvalue` AS `pvalue`,`20091001_bit`.`t_bit`.`ivalue` AS `ivalue`,`20091001_bit`.`t_bit`.`data` AS `data` from `20091001_bit`.`t_bit` FORCE INDEX (`ix_bit_ivalue`) where (((`20091001_bit`.`t_bit`.`ivalue` | 0x0000ffff) = 0x0000ffff) and (`20091001_bit`.`t_bit`.`ivalue` <= (2 << (floor((log(2,0x0000ffff) + 1)) - 1))))

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

id	pvalue	ivalue	data
296048	4294903570	4294903570	Value 4294903570
272233	4294904070	4294904070	Value 4294904070
113049	4294922862	4294922862	Value 4294922862
341923	4294924662	4294924662	Value 4294924662
509704	4294926970	4294926970	Value 4294926970
553589	4294935894	4294935894	Value 4294935894
796787	4294937658	4294937658	Value 4294937658
95938	4294938382	4294938382	Value 4294938382
698531	4294941690	4294941690	Value 4294941690
715020	4294947058	4294947058	Value 4294947058
274169	4294947378	4294947378	Value 4294947378
816273	4294949106	4294949106	Value 4294949106
255384	4294964734	4294964734	Value 4294964734
13 rows fetched in 0.0005s (0.0025s)

id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	t_bit	range	ix_bit_ivalue	ix_bit_ivalue	4		40	100.00	Using where

select `20091001_bit`.`t_bit`.`id` AS `id`,`20091001_bit`.`t_bit`.`pvalue` AS `pvalue`,`20091001_bit`.`t_bit`.`ivalue` AS `ivalue`,`20091001_bit`.`t_bit`.`data` AS `data` from `20091001_bit`.`t_bit` FORCE INDEX (`ix_bit_ivalue`) where (((`20091001_bit`.`t_bit`.`ivalue` & 0xffff0000) = 0xffff0000) and (`20091001_bit`.`t_bit`.`ivalue` >= (0xffffffff & ~(((2 << floor(log(2,(0xffffffff & ~(0xffff0000))))) - 1)))))

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

id	pvalue	ivalue	data
48638	9536	9536	Value 9536
1 row fetched in 0.0001s (0.9375s)

id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	t_bit	range	ix_bit_ivalue	ix_bit_ivalue	4		51151	100.00	Using where

select `20091001_bit`.`t_bit`.`id` AS `id`,`20091001_bit`.`t_bit`.`pvalue` AS `pvalue`,`20091001_bit`.`t_bit`.`ivalue` AS `ivalue`,`20091001_bit`.`t_bit`.`data` AS `data` from `20091001_bit`.`t_bit` FORCE INDEX (`ix_bit_ivalue`) where (((`20091001_bit`.`t_bit`.`ivalue` | 0x09876543) = 0x09876543) and (`20091001_bit`.`t_bit`.`ivalue` <= (2 << (floor((log(2,0x09876543) + 1)) - 1))))

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.

MySQL Links