Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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?

share|improve this question

migrated from stackoverflow.com May 19 '11 at 9:33

This question came from our site for professional and enthusiast programmers.

    
Mysql also doesn't support function-based indexes, bitmap indexes, etc etc. Just because it is mysql ;-) –  zerkms May 17 '11 at 6:00
1  
i just figured that hash indexes were so...fundamental...i assume there's specific implementation-related reason. –  Alex May 17 '11 at 6:04
1  
@Alex: I bet that reason is "laziness" and "bureaucracy" but let's wait for answers )) –  zerkms May 17 '11 at 6:14
4  
    
I added a nice HASH algorithm from the High Performance MySQL Book to the end of my answer. –  RolandoMySQLDBA May 17 '11 at 19:07
add comment

4 Answers 4

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 !!!

share|improve this answer
2  
Before using the pseudo-hash-index technique in production, perform some performance analysis on it. For large strings it can make a big difference but you end up navigating a tree index in the end anyway, and you have extra compares to do to find the right row from those found matching the hash, so for small values computing the hash values and storing them just isn't worth it. This isn't really a hash index at all, you are simply reducing the work done walking the tree (as each compare is considering less bytes, for instance comparing 8 byte INTs instead of x00 bytes strings). –  David Spillett May 19 '11 at 13:58
    
@David Spillett In this, I totally have to agree with you. Other indexing stratagies are also suggested in the same book in Chapter 11 "Indexing Strategies for High Performance". As an additional boost to my answer, the book actually mentions using a clustered index which stores the row and the BTree Index in the same structure. This may be speed up the reduced work you mentioned. Unfortunately, the hoops you have to jump through that you just mentioned are somewhat unavoidable. A +1 from me on your comment nonetheless, sir !!! In fact, +1 for your answer as well. –  RolandoMySQLDBA May 19 '11 at 14:46
    
@RolandoMySQLDBA Can you elaborate more on the part on "custom hashing", the last paragraph doesn't seem to give much clue... –  Pacerier Jul 6 '12 at 8:36
add comment

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.

share|improve this answer
    
Is there any way to allow re-hashing (rebuilding) to be done side-by-side without locking the entire table? –  Pacerier Jul 6 '12 at 8:40
    
@Pacerier: not that I know of with MySQL (though they could have added the feature since I last used it, so check the documentation). Even where a DBMS supports online index creation/rebuilding it isn't the default option. What gets locked will vary to: some will hold a write lock on the table to other transactions are not delayed if they are only reading, some DMBSs will take out a full table lock. If you need online rebuilding, check the documentation each DBMS before choosing which to use. –  David Spillett Jul 7 '12 at 11:49
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.