Mysql – Column order for better index

indexinnodbMySQL

let say I have two tables like tbl_parent and tbl_children (just as an example), in the first table I have parent_id, and in the second one I (will) have something like child_id plus the parent_id, plus some other columns.

My question is does it make any sense to make the database columns in tbl_children like parent_id first, following by child_id? Because I will index them, and my WHERE clause should be some thing like WHERE parent_id = x AND child_id = y.

Again this is just an example. I just want to know if column orders could improve the performance on indexed columns or not?

Platform: MySQL, InnoDB, on Integer Values.

Best Answer

No, the column order in the table is not important at all for the performance of any related query or any additional index.

A table T1(a, b) is equivalent to T2(b, a), if the data inside is the same. The order of the columns matter only for an index key, because there the data is ordered after the first column of the key.

PS: let's say on table Table1 (a, b, c, d) an index is created the following way:

CREATE INDEX idx_Table1 ON Table1 (a, b);

This creates an index, which is a data structure additional to a table in the format of a balanced tree (B-Tree) that helps some queries run faster. The index key is that pair formed of the data from columns (a,b) concatenated.

For example a query like:

select a from Table1 where a = 1 and b = 2

would use the index idx_Table1, while a query like:

select a from Table1 where b = 1 and c = 1

would most probably wouldn't use it but would benefit from an index:

CREATE INDEX idx_Table2 ON Table1 (b, a);

Some references:

The MySQL reference page for CREATE INDEX is here.
How MySQL uses indexes: reference page.
A nice book on indexes: Use The Index, Luke.

FACTOR #1

For any given index, what is the key population? In other words, what is the cardinality (distinct count) of all tuples recorded in the index?

FACTOR #2

What storage engine are you using? Are all needed columns accessible from an index?

WHAT'S NEXT ???

Let's take a simple example: a table that holds two values (Male and Female)

Let create such a table with a test for index usage

USE test
DROP TABLE IF EXISTS mf;
CREATE TABLE mf
(
    id int not null auto_increment,
    gender char(1),
    primary key (id),
    key (gender)
) ENGINE=InnODB;
INSERT INTO mf (gender) VALUES
('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
('M'),('M'),('M'),('M'),('F'),('F'),('M'),('M'),
('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
('F'),('M'),('M'),('M'),('M'),('M'),('M'),('M');
ANALYZE TABLE mf;
EXPLAIN SELECT gender FROM mf WHERE gender='F';
EXPLAIN SELECT gender FROM mf WHERE gender='M';
EXPLAIN SELECT id FROM mf WHERE gender='F';
EXPLAIN SELECT id FROM mf WHERE gender='M';

TEST InnoDB

mysql> USE test
Database changed
mysql> DROP TABLE IF EXISTS mf;
Query OK, 0 rows affected (0.00 sec)

mysql> CREATE TABLE mf
    -> (
    ->     id int not null auto_increment,
    ->     gender char(1),
    ->     primary key (id),
    ->     key (gender)
    -> ) ENGINE=InnoDB;
Query OK, 0 rows affected (0.07 sec)

mysql> INSERT INTO mf (gender) VALUES
    -> ('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
    -> ('M'),('M'),('M'),('M'),('F'),('F'),('M'),('M'),
    -> ('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
    -> ('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
    -> ('F'),('M'),('M'),('M'),('M'),('M'),('M'),('M');
Query OK, 40 rows affected (0.06 sec)
Records: 40  Duplicates: 0  Warnings: 0

mysql> ANALYZE TABLE mf;
+---------+---------+----------+----------+
| Table   | Op      | Msg_type | Msg_text |
+---------+---------+----------+----------+
| test.mf | analyze | status   | OK       |
+---------+---------+----------+----------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT gender FROM mf WHERE gender='F';
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref   | rows | Extra                    |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | mf    | ref  | gender        | gender | 2       | const |    3 | Using where; Using index |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT gender FROM mf WHERE gender='M';
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref   | rows | Extra                    |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | mf    | ref  | gender        | gender | 2       | const |   37 | Using where; Using index |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT id FROM mf WHERE gender='F';
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref   | rows | Extra                    |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | mf    | ref  | gender        | gender | 2       | const |    3 | Using where; Using index |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT id FROM mf WHERE gender='M';
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref   | rows | Extra                    |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | mf    | ref  | gender        | gender | 2       | const |   37 | Using where; Using index |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)

mysql>

TEST MyISAM

mysql> USE test
Database changed
mysql> DROP TABLE IF EXISTS mf;
Query OK, 0 rows affected (0.00 sec)

mysql> CREATE TABLE mf
    -> (
    ->     id int not null auto_increment,
    ->     gender char(1),
    ->     primary key (id),
    ->     key (gender)
    -> ) ENGINE=MyISAM;
Query OK, 0 rows affected (0.05 sec)

mysql> INSERT INTO mf (gender) VALUES
    -> ('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
    -> ('M'),('M'),('M'),('M'),('F'),('F'),('M'),('M'),
    -> ('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
    -> ('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
    -> ('F'),('M'),('M'),('M'),('M'),('M'),('M'),('M');
Query OK, 40 rows affected (0.00 sec)
Records: 40  Duplicates: 0  Warnings: 0

mysql> ANALYZE TABLE mf;
+---------+---------+----------+----------+
| Table   | Op      | Msg_type | Msg_text |
+---------+---------+----------+----------+
| test.mf | analyze | status   | OK       |
+---------+---------+----------+----------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT gender FROM mf WHERE gender='F';
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref   | rows | Extra                    |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | mf    | ref  | gender        | gender | 2       | const |    3 | Using where; Using index |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT gender FROM mf WHERE gender='M';
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref   | rows | Extra                    |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | mf    | ref  | gender        | gender | 2       | const |   36 | Using where; Using index |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT id FROM mf WHERE gender='F';
+----+-------------+-------+------+---------------+--------+---------+-------+------+-------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref   | rows | Extra       |
+----+-------------+-------+------+---------------+--------+---------+-------+------+-------------+
|  1 | SIMPLE      | mf    | ref  | gender        | gender | 2       | const |    3 | Using where |
+----+-------------+-------+------+---------------+--------+---------+-------+------+-------------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT id FROM mf WHERE gender='M';
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | mf    | ALL  | gender        | NULL | NULL    | NULL |   40 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)

mysql>

Analysis for InnoDB

When the data was loaded as InnoDB, please note that all four EXPLAIN plans used the gender index. The third and fourth EXPLAIN plans used the gender index even though the requested data was id. Why? Because id is in the PRIMARY KEY and all secondary indexes have reference pointers back to the PRIMARY KEY (via the gen_clust_index).

Analysis for MyISAM

When the data was loaded as MyISAM, please note that the first three EXPLAIN plans used the gender index. In the fourth EXPLAIN plan, the Query Optimizer decided not to use an index at all. It opted for a full table scan instead. Why?

Regardless of DBMS, Query Optimizers operate on a very simple rule-of-thumb: If an index is being screened as a candidate to be used for performing the lookup and Query Optimizer computes that it must lookup more than 5% of the total number of rows in the table:

a full index scan is done if all needed columns for retrieval are in the selected index
a full table scan otherwise

CONCLUSION

If you do not have proper covering indexes, or if the key population for any given tuple is more than 5% of the table, six things must happen:

Come to the realization that you must profile the queries
Find all WHERE, GROUP BY, and ORDER BY` clauses from those Queries
Formulate indexes in this order
- WHERE clause columns with static values
- GROUP BY columns
- ORDER BY columns
Avoid Full Table Scans (Queries lacking a sensible WHERE clause)
Avoid Bad Key Populations (or at least cache those Bad Key Populations)
Decide on the best MySQL Storage Engine (InnoDB or MyISAM) for the Tables

I have written about this 5% rule of thumb in the past:

May 07, 2012 : MySQL EXPLAIN doesn't show 'use index' for FULLTEXT
Mar 22, 2012 : Why does MySQL choose this execution plan?
Mar 09, 2012 : index not being used
Jan 18, 2012 : MySQL status variable Handler_read_rnd_next is growing a lot
Dec 27, 2011 : MySQL - fastest way to ALTER TABLE for InnoDB
Jul 29, 2011 : MySQL Query Optimization : Indexing and Pagination
Jul 12, 2011 : MySQL very slow query when changing one WHERE field despite no index/key

UPDATE 2012-11-14 13:05 EDT

I took a look back at your question and at the original SO post. Then, I thought about my Analysis for InnoDB I mentioned before. It coincides with the person table. Why?

For both tables mf and person

Storage Engine is InnoDB
Primary Key is id
Table access is by secondary index
If table was MyISAM, we would see a completely different EXPLAIN plan

Now, look at the query from the SO question : select * from person order by age\G. Since there is no WHERE clause, you explicitly demanded a full table scan. The default sort order of the table would be by id (PRIMARY KEY) because of its auto_increment and the gen_clust_index (aka Clustered Index) is ordered by internal rowid. When you ordered by the index, keep in mind that InnoDB secondary indexes have the rowid attached to each index entry. This produces the internal need for full row access each time.

Setting up ORDER BY on an InnoDB table can be a rather daunting task if you ignore these facts about how InnoDB indexes are organized.

Going back to that SO query, since you explicitly demanded a full table scan, IMHO the MySQL Query Optimizer did the correct thing (or at least, chose the path of least resistance). When it comes to InnoDB and the SO query, it is far easier to perform a full table scan and then some filesort rather than doing a full index scan and a row lookup via the gen_clust_index for each secondary index entry.

I am not an advocate of using Index Hints because it ignores the EXPLAIN plan. Notwithstanding, if you really know your data better than InnoDB, you will have to resort to Index Hints, especially with queries that have no WHERE clause.

UPDATE 2012-11-14 14:21 EDT

According to the book Understanding MySQL Internals

enter image description here

Page 202 Paragraph 7 says the following:

The data is stored in a special structure called a clustered index, which is a B-tree with the primary key acting as the key value, and the actual record (rather than a pointer) in the data part. Thus, each InnoDB table must have a primary key. If one is not supplied, a special row ID column not normally visible to the user is added to act as a primary key. A secondary key will store the value of the primary key that identifies the record. The B-tree code can be found in innobase/btr/btr0btr.c.

This is why I stated earlier : it is far easier to perform a full table scan and then some filesort rather than doing a full index scan and a row lookup via the gen_clust_index for each secondary index entry. InnoDB is going to do a double index lookup every time. That sounds kind of brutal, but that's just the facts. Again, take into consideration the lack of WHERE clause. This, in itself, is the hint to the MySQL Query Optimizer to do a full table scan.

Sql-server – Are these indexes redundant

In this case, yes, they appear to be redundant. The second index will satisfy any queries that would benefit from the first one. Also, both indexes appear to contain the same columns, so rows within the index leaf pages should be about the same size in either. Your non-leaf index pages will be a bit larger with more key columns, but that probably won't amount to a significant size increase, unless the index rows are quite large and only fit a few per page.

It's important to consider the size of the index rows when deciding if an index is truly redundant. If you have an index on a couple of int columns, a decimal, and a datetime, the rows will be much smaller than if you have another index on those same columns plus a character column that averages a couple hundred bytes. Any analytical queries that would aggregate a large number of rows would benefit from the index that has rows much more densely packed on the data pages, even though either index could technically satisfy the query.

So, make sure you consider the difference in average row size, and whether or not that has any performance implications before you go dropping any redundant-looking indexes.