Why isn't SELECT DISTINCT on an indexed column instantaneous?

Question

I have a table like this that stores configurations of various programs that are run. It looks something like this:

+--------------+---------------+------+-----+---------+-------+
| Field        | Type          | Null | Key | Default | Extra |
+--------------+---------------+------+-----+---------+-------+
| Date         | date          | YES  | MUL | NULL    |       |
| Program      | varchar(20)   | YES  | MUL | NULL    |       |
| ConfigFile   | int(11)       | YES  |     | NULL    |       |
| Parameter    | varchar(20)   | YES  |     | NULL    |       |
| Value        | varchar(20)   | YES  |     | NULL    |       |
+--------------+---------------+------+-----+---------+-------+

The ConfigFile field contains the number of the config file -- for some of the programs there is more than one config file that can be chosen.

It has a couple of indices, like so:

+-------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name  | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| lists |          1 | Date     |            1 | Date         | A         |     1108060 |     NULL | NULL   | YES  | BTREE      |         |               |
| lists |          1 | Date     |            2 | Program      | A         |     1108060 |     NULL | NULL   | YES  | BTREE      |         |               |
| lists |          1 | Date     |            3 | Parameter    | A         |     1108060 |     NULL | NULL   | YES  | BTREE      |         |               |
| lists |          1 | Program  |            1 | Program      | A         |        4676 |     NULL | NULL   | YES  | BTREE      |         |               |
| lists |          1 | Program  |            2 | Parameter    | A         |      183706 |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

Now let's say I want to know what the parameters for a given program are. It seems like I should be able to do something like this:

SELECT DISTINCT Parameter FROM params WHERE Program = 'MyProgram';

This has the following explain plan:

+----+-------------+--------+------------+------+----------------+---------+---------+-------+-----------+----------+--------------------------+
| id | select_type | table  | partitions | type | possible_keys  | key     | key_len | ref   | rows      | filtered | Extra                    |
+----+-------------+--------+------------+------+----------------+---------+---------+-------+-----------+----------+--------------------------+
|  1 | SIMPLE      | params | NULL       | ref  | Date,Program   | Program | 23      | const | 137203382 |   100.00 | Using where; Using index |
+----+-------------+--------+------------+------+----------------+---------+---------+-------+-----------+----------+--------------------------+

There are something like 15 different choices for Program, and maybe between 10 and 100 values of Parameter for each program.

With my understanding of how a database index works, I'd expect this to complete instantaneously. In particular, I'd expect the underlying data structure to be a binary search tree with 15 nodes, which I search to find the one corresponding to my program; after finding my program, it takes me to second binary search tree with perhaps 100 nodes or fewer, which I'd then simply traverse.

When I actually run the query, though, it winds up taking several minutes.

To me this suggests that there are perhaps multiple copies of the same value in the binary search tree, one per node of the table. Is this what's happening, and, if so, what can I do to mitigate this situation?

I considered having one table with unique triples (Date, Program, Parameter) and having a relation, but I'm not sure how to perform a bulk insert of the data in this situation. And if I'm wrong about why it's so slow then of course this wouldn't even help.

Answer 1

InnoDB's B+Tree secondary indexes don't get formed that way. Think of it this way:

1. For each row, construct a string composed of Program,Parameter,PK.
2. Sort those strings.
3. Lay them out in a BTree.

Note: There was no hint of splitting up by Program. What if 99.9% of the Programs were in Program #5? That would be a rather unbalanced BTree. Handy for your one rare query, but slower for the majority of other queries.

With the nicely balanced B+Tree, your query must:

1. Drill down the BTree to find the first 'row' for Program = 'MyProgram'
2. Walk forward through the leaf nodes of the B+Tree, using the "+" to step from one leaf block to the next.
3. While walking, keep track of each new Parameter.
4. Quit when Program = 'MyProgram' fails.

Notes:

• DISTINCT was easily implemented in my step 3 by understanding how the items are ordered.
• "Using index" says that the index was "covering" -- since you only needed Program and Parameter (and those were the columns in the INDEX). The PK is also implicitly available for "covering".
• The 15 that you provided disagrees with the cardinaliity of "4676". But that just points out that the statistics are sometimes quite far off. (Statistics has no impact on optimization of this query.)

I considered having one table with unique triples (Date, Program, Parameter)

Yes, having such a table would make your query run much faster. But is it worth the maintenance of such?

Another thing that table would let you do is to normalize out those 3 columns into a single MEDIUMINT UNSIGNED (only 3 bytes) instead of perhaps 30 bytes now being used on the average row. Again, would the complexity of the JOINs, etc, outweigh the benifit? It would shrink the disk footprint by perhaps 50%.