Why does MySQL not have hash indices on MyISAM or InnoDB?

Question

I have an application that will only select on equality, and I figure I should use a hash index over a btree index. Much to my dismay, hash indices are not supported on MyISAM or InnoDB. What's up with that?

Answer 1

Many databases don't support hash based indexes at all.

In order for a hash table to be efficient you need to know the number of rows that are likely to be present otherwise the base hash table will be far too large (many empty entries, wasting space and potentially disk IO) or too small meaning that indirection is often used (possibly multiple levels of indirection, or even worse if the hash implementation is single-level you could end up performing a linear search over a fair number of records) at which point things are probably no more efficient then a tree based index anyway.

So to be generally useful (i.e. usually better than the alternative) the index needs to be rebuilt occasionally as data grows (and shrinks) which could add a significant intermittent overhead. This is usually fine with memory based tables as the rebuild is probably going to be pretty fast (as the data is always going to be in RAM and is not likely to be massive in any case), but rebuilding a large index on disk is a very heavy operation (and IIRC mySQL doesn't support live index rebuilds so holds a table lock during the operation).

Hence hash indexes are used in memory tables as there they are generally better performers, but disk based tables don't support them as they could be a detriment to performance not a bonus. There is nothing to stop hash indexes being made available for disk based tables of course, no doubt some databases do support the feature, but presumably they are not implemented in ISAM/InnoDB tables as the maintainers do not consider the feature worth adding (as the extra code to write and maintain is not worth the benefit in those few circumstances that it makes a significant difference). Perhaps if you strongly disagree you could talk to them and make a good case for the implementation of the feature.

If you are indexing large strings then implementing your own pseudo-hash index (by storing a hash of the value as well as the actual value, and indexing that has column) may work, but this is only definitely more efficient for large strings (where computing the hash value and searching the tree index by this value is always likely to be faster then just searching a tree index using the larger values for comparison, and the extra storage used is not going to be significant) so do some performance analysis before implementing this in production.

Answer 2

Here is something interesting:

According to the book MySQL 5.0 Certification Study Guide, Page 433, Section 29.5.1

The MEMORY engine uses HASH by default indexing algorithm.

For laughs, I tried to create an InnoDB table and a MyISAM table with a primary key using HASH in MySQL 5.5.12

mysql> use test
Database changed
mysql> create table rolando (num int not null, primary key (num) using hash);
Query OK, 0 rows affected (0.11 sec)

mysql> show create table rolando\G
*************************** 1. row ***************************
       Table: rolando
Create Table: CREATE TABLE `rolando` (
  `num` int(11) NOT NULL,
  PRIMARY KEY (`num`) USING HASH
) ENGINE=InnoDB DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

mysql> create table rolando2 (num int not null, primary key (num) using hash) engine=MyISAM;
Query OK, 0 rows affected (0.05 sec)

mysql> show create table rolando2\G
*************************** 1. row ***************************
       Table: rolando2
Create Table: CREATE TABLE `rolando2` (
  `num` int(11) NOT NULL,
  PRIMARY KEY (`num`) USING HASH
) ENGINE=MyISAM DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

MySQL did not complain.

UPDATE

Bad News !!! I used SHOW INDEXES FROM. It says the index is BTREE.

The CREATE INDEX syntax MySQL Page states that only MEMORY and NDB storage engines can accommodate the HASH INDEX.

mysql> show indexes from rolando;
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table   | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| rolando |          0 | PRIMARY  |            1 | num         | A         |           0 |     NULL | NULL   |      | BTREE      |         |               |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)

mysql> show indexes from rolando2;
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table    | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| rolando2 |          0 | PRIMARY  |            1 | num         | A         |           0 |     NULL | NULL   |      | BTREE      |         |               |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)

mysql> create table rolando3 (num int not null, primary key (num)) ENGINE=MEMORY;
Query OK, 0 rows affected (0.03 sec)

mysql> show create table rolando3\G
*************************** 1. row ***************************
       Table: rolando3
Create Table: CREATE TABLE `rolando3` (
  `num` int(11) NOT NULL,
  PRIMARY KEY (`num`)
) ENGINE=MEMORY DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

mysql> show indexes from rolando3;
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table    | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| rolando3 |          0 | PRIMARY  |            1 | num         | NULL      |           0 |     NULL | NULL   |      | HASH       |         |               |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)

Some people suggested following the idea in Pages 102-105 of the book "High Performance MySQL : Optimizations, Backups, Replication and More" to emulate the hash algorithm.

Page 105 features this quick-and-dirty algorithm that I like:

SELECT CONV(RIGHT(MD5('whatever value you want'),16),16,10) AS HASH64;

Make a column for this in any table and index this value.

Give it a Try !!!

Answer 3

On a related note, you might find the discussion on index types from the PostgreSQL docs interesting. It's no longer present in recent versions of the docs (due to subsequent optimizations, I take it), but the takeaway might be similar for MySQL (and the reason why hash indexes are only used for heap tables):

http://www.postgresql.org/docs/8.1/static/indexes-types.html

Note: Testing has shown PostgreSQL's hash indexes to perform no better than B-tree indexes, and the index size and build time for hash indexes is much worse. Furthermore, hash index operations are not presently WAL-logged, so hash indexes may need to be rebuilt with REINDEX after a database crash. For these reasons, hash index use is presently discouraged. Similarly, R-tree indexes do not seem to have any performance advantages compared to the equivalent operations of GiST indexes. Like hash indexes, they are not WAL-logged and may need reindexing after a database crash. While the problems with hash indexes may be fixed eventually, it is likely that the R-tree index type will be retired in a future release. Users are encouraged to migrate applications that use R-tree indexes to GiST indexes.

Again, it's (obsolete version of) PostgreSQL-specific, but it should hint that the "natural" index type won't necessarily yield optimal performance.

Answer 4

BTree is not that much slower than Hash for single-row lookup. Since BTree provides very efficient range queries, why bother with anything other than BTree.

MySQL does a very good job of caching BTree blocks, so a BTree-based query rarely has to do I/O, which is the biggest time consumer in any query.