Description:
We have a customer_tree table, that is used to assign an ordering to a set of nodes. This is to optimize reads. (We can find a subtree based on the left_order and right_order.)
mysql> show create table customer_tree;
+---------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Table | Create Table |
+---------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| customer_tree | CREATE TABLE `customer_tree` (
`customer_id` int(10) unsigned NOT NULL default '0',
`root_customer_id` int(11) NOT NULL default '0',
`left_order` int(11) NOT NULL default '0',
`right_order` int(11) NOT NULL default '0',
PRIMARY KEY (`customer_id`),
KEY `idx_lo_ro` (`left_order`,`right_order`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1 |
+---------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
We have an index on left_order, right_order:
mysql> show index from customer_tree;
+---------------+------------+-----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+---------------+------------+-----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| customer_tree | 0 | PRIMARY | 1 | customer_id | A | 545585 | NULL | NULL | | BTREE | |
| customer_tree | 1 | idx_lo_ro | 1 | left_order | A | 545585 | NULL | NULL | | BTREE | |
| customer_tree | 1 | idx_lo_ro | 2 | right_order | A | 545585 | NULL | NULL | | BTREE | |
+---------------+------------+-----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
3 rows in set (0.00 sec)
We're wondering why this query takes so long, when we have a lot of data:
550206 records
select customer_id
from customer_tree
where left_order < 5649459 and right_order > 5649469
order by left_order desc limit 1;
It would seem that based on the index idx_lo_ro that it should easily be able to find the position in the index records where left_order < 5649459, and then return immediately after finding a right_order that meets the qualification.
Unfortunately, that query takes many minutes to complete.
However, if we leave out the right_order clause, the query returns instantly:
mysql> select customer_id from customer_tree where left_order < 5649459 order by left_order desc limit 1;
+-------------+
| customer_id |
+-------------+
| 2921623 |
+-------------+
1 row in set (0.02 sec)
So, we thought, maybe the qualifying record in which right_order > 5649469 takes a long time to get to when going through the index records.
So, we looked at the first 10 records that meet the left_order qualification, to see if any of them meet the right_order qualification:
mysql> select customer_id, left_order, right_order from customer_tree where left_order < 5649459 order by left_order desc limit 10;
+-------------+------------+-------------+
| customer_id | left_order | right_order |
+-------------+------------+-------------+
| 2921623 | 5649424 | 5649447 |
| 2759299 | 5649423 | 5649448 |
| 2758301 | 5649422 | 5649449 |
| 2660993 | 5649421 | 5649450 |
| 2659666 | 5649420 | 5649451 |
| 2659102 | 5649419 | 5649452 |
| 2658966 | 5649418 | 5649453 |
| 2658933 | 5649417 | 5649454 |
| 2658911 | 5649416 | 5649455 |
| 3994381 | 5648392 | 5649192 |
+-------------+------------+-------------+
10 rows in set (0.30 sec)
That 10th record meets the qualification.
So, why, does it take so incredibly long, when it only has to go through 10 records to find a left_order and right_order that qualify?
Here's the explain without the right_order clause:
mysql> explain select customer_id, left_order, right_order from customer_tree where left_order < 5649459 order by left_order desc limit 10;
+----+-------------+---------------+-------+---------------+-----------+---------+------+--------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+---------------+-------+---------------+-----------+---------+------+--------+--------------------------+
| 1 | SIMPLE | customer_tree | range | idx_lo_ro | idx_lo_ro | 4 | NULL | 272792 | Using where; Using index |
+----+-------------+---------------+-------+---------------+-----------+---------+------+--------+--------------------------+
1 row in set (0.00 sec)
Here's the explain with the right_order clause:
mysql> explain select customer_id from customer_tree where left_order < 5649459 and right_order > 5649469 order by left_order desc limit 1;
+----+-------------+---------------+-------+---------------+-----------+---------+------+--------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+---------------+-------+---------------+-----------+---------+------+--------+--------------------------+
| 1 | SIMPLE | customer_tree | range | idx_lo_ro | idx_lo_ro | 4 | NULL | 272792 | Using where; Using index |
+----+-------------+---------------+-------+---------------+-----------+---------+------+--------+--------------------------+
1 row in set (0.00 sec)
Same explain.
Tested in 5.0.24, 4.1.21 with both MyISAM & InnoDB tables.
How to repeat:
See description
