1

The table is simple:

CREATE TABLE `t1` (
  `ID` int NOT NULL AUTO_INCREMENT,
  `name` int DEFAULT '1',
  `LastName` int DEFAULT '0',
  UNIQUE KEY `idx_ID` (`ID`) USING BTREE,
  KEY `idx_name` (`name`)
) ENGINE=InnoDB;

DELIMITER $$
DROP PROCEDURE IF EXISTS populate_t1;
CREATE PROCEDURE populate_t1(IN num INT)
BEGIN
    DECLARE COUNT INT DEFAULT 0;
    WHILE COUNT < num DO
        INSERT INTO t1(`name`,`LastName`) VALUES(round(rand()+5, 0), round(rand()*10000, 0));
        SET COUNT = COUNT + 1;
    END WHILE;
END $$
DELIMITER ;

CALL populate_t1(1000000);
CREATE INDEX idx_name ON t1 (`name`);
OPTIMIZE TABLE t1;

The column name has very low selectivity (i.e., only 2 distinct values). Query

> SELECT * FROM t1 WHERE Name=5;
> OK, 499845 records, Time: 0.840s

would be slower than the query which use a full table scan

> DROP INDEX idx_name ON t1;
> OK 
> SELECT * FROM t1 WHERE Name=5;
> OK, 499845 records, Time: 0.258s

This performance drop is expected, but I want to figure out why.

I know that the index is like an English dictionary index in the first several pages of an English dictionary. And the index is stored in a B+tree in my example I suppose. So with an index on column name, MySQL would know which rows satisfy name=5. Then MySQL fetches these rows into the result set. I think the process above would be quicker than scanning the whole table (but I am wrong). So what I want to ask is which process makes (e.g., loading index from disk to memory, searching in the B+tree, etc.) the index scan slower than the full table scan.

Further, I know that if the table is larger, the performance difference would be larger (I still want to know why).

I would be very grateful for your help!
Thanks!

4

Access to a row using a non-clustered index, which idx_name is, requires extra random I/O: b-tree lookup finds the clustered (primary key) index value, then you need to go and fetch the actual row from the clustered index.

The alternative is a sequential scan of the clustered index itself, which does not incur that extra I/O cost and is also simply more efficient by being sequential, not random.

| improve this answer | |
  • Gotit. Thank you very much for the reply! – haochen he Oct 15 at 16:05
  • I should add that a proper query optimizer would not pick a low cardinality index for access exactly for this reason. MySQL apparently has some ways to go in this department. – mustaccio Oct 15 at 16:07
  • The query optimizer estimates the complexity, but may still fail sometimes: MySQL#73386. But when we observe the optimizer chose a sub-optimal query plan, I find it is difficult to know if it is caused by a bug or is expected behavior. Actually, the initial thought of asking this question is that I want to find some bugs in which the optimizer falsely chooses a sub-optimal plan. – haochen he Oct 15 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.