5

Suppose I have a query like:

SELECT *
FROM table_a
    JOIN table_b USING (id)
WHERE table_b.column = 1

I have an index on id and an index on column but often I add a composite index with both that can improve efficiency of queries like this. My question is concerning the order of the columns in the index. By trial and error I've found that sometimes the DBMS prefers the joined index first and sometimes it prefers the WHERE index first.

In the above query is there a hard, fast rule I can abide by to know which key order will work best?

Typically I just add both indexes, run EXPLAIN on the query and check to see which is preferred, then remove the other one. But this process feels like it could be improved by a better understanding of the logic involved in determining index order.

0
4

A good rule of thumb is to make the leading column in a compound index as selective as possible. A good way to imagine this is with the phone-book analogy: Imagine you need to find someone in the phone book, and there are two indexes... the first is Lastname, Firstname. The second is FirstName, LastName. Which index would you use to find someone named John Xylophone? Surely you'd use the LastName, Firstname index since there are very few Xylophone entries, and it will take a lot less time than looking through all the John entries for one with the last name of Xylophone.

So, if id is highly selective, and column has low selectivity, you'd want the index to be (id, column), however if column has high selectivity, and id has low selectivity, you'd probably benefit from having the index defined as (column, id).

You might see an index on (column, id) being used if you are joining two tables on id with where column = x when x results in a substantially reduced number of rows needing to be joined.

6
  • @MaxVernon - You are half wrong. When both parts are tested with '=', selectivity is irrelevant. Even your example is flawed. A BTree index is drilled down via all the keys simultaneously, not in two steps.
    – Rick James
    May 15 '18 at 20:30
  • @Rick - this was an attempt to simplify the problem domain into lay terminology that is simple to understand and remember. I've been wrong before. I'm reading your excellent article now.
    – Hannah Vernon
    May 16 '18 at 15:54
  • @RickJames Selectivity is the most obvious criteria. The other one is the type of the indexed field. Strings mangled with charsets and collations can be significantly slower than ints due to the more complex comparation. Especially combined with %LIKE%. Another factor is the length of tables combined with type of relation. When tables related as 1:1 are joined the longer one should be joined to the shorter FROM few JOIN lot ON.. but it depends.
    – Kondybas
    May 18 '18 at 17:07
  • 2
    @Kondybas - Sorry, but I think that most of what you say is either misleading or wrong. Selectivity is irrelevant in composite indexes. Collations (etc) are slightly slower; fetching the rows is the big cost. %like% is bad mostly because of the leading wildcard. Table length is only slightly difference: example--The depth of a trillion-row index is only twice that of a million-row index.
    – Rick James
    May 18 '18 at 19:09
  • 1
5

For this query

SELECT *
FROM table_a
    JOIN table_b USING (id)
WHERE table_b.column = 1

The optimal way is execute it is

  1. The WHERE clause provides some filtering, so let's make use of it. That is, have an index on table_b starting with column. (Later we'll discuss whether to make it composite.) So, the Optimizer will use that index to find row(s) of table_b.
  2. For each of those rows, JOIN to table_a. (Note that JOIN, not LEFT JOIN is being used; LEFT JOIN is a different story.)
  3. To reach into table_a, an index starting with id is needed. (Note: USING(id) means table_a.id = table_b.id.)

So far, we have

b:  INDEX(column)
a:  INDEX(id)   -- though it probably exists as PRIMARY KEY(id)

Covering?

We don't know what other columns there are in the two tables. If there are very few columns, then it might be tempting to build a "covering" index. This is an index that contains all the columns needed anywhere in the SELECT. The benefit is some performance speedup by looking only in the index's BTree and not having to touch the data BTree.

For table_b, it would be tempting to say INDEX(column, id). That would be good (and 'covering') if there were only those two columns. But there are probably more columns. So, probably INDEX(column) is all that is worth doing.

For table_a, I assume that id is the PRIMARY KEY (which is, by definition, unique and an index). So nothing more is needed there.

Bottom line: Use the two single-column indexes listed above.

And this example does not exemplify anything about "composite" indexes. For more on that, see

Cardinality & Range
Cardinality and Composite
Single-column index
Indexing cookbook

but often I add a composite index with both that can improve efficiency of queries like this...

Better Example

As I said, your example does not exemplify the question. So, I'll try to answer "When should I use a composite index"? There are many cases (see the links); I'll give you a simple case.

WHERE x = 1
  AND y > 2

The relevant characteristics are:

  • x and y are in the same table. (Can't build an index across two tables.)
  • AND is used. (OR can't be optimized.)
  • One of the tests is with =. (Composite won't help if both are ranges.)
  • y is a "range" (examples: y>2, y LIKE 'm%', y BETWEEN ... AND ...).

The general rule is:

  1. Put all the = columns first (x in my example)
  2. Put one range column last (y)

That is, you must order it INDEX(x,y).

For WHERE x = 1 AND y = 2 (both =), it does not matter whether you have INDEX(x,y) or INDEX(y,x) .

Another tidbit: With ENGINE=InnoDB, the PRIMARY KEY column(s) are implicitly tacked onto each secondary key. Hence, your INDEX(column) is the same as INDEX(column, id). But this fact does not play a role in this discussion.

I realize that I am disagreeing with other Answers here (and elsewhere), but I stand my ground.

2

In the above query is there a hard, fast rule I can abide by to know which key order will work best?

In the example you have given, your best bet is not to have a composite index at all if you are free to change the join order:

create table table_a(id integer, dummy_a integer);
create index index_a on table_a(id);
create table table_b(id integer, col integer, dummy_b integer);
create index index_b on table_b(col);
explain select * from table_b join table_a using(id) where table_b.col=1;
id | select_type | table   | partitions | type | possible_keys | key     | key_len | ref                                    | rows | filtered | Extra      
-: | :---------- | :------ | :--------- | :--- | :------------ | :------ | :------ | :------------------------------------- | ---: | -------: | :----------
 1 | SIMPLE      | table_b | null       | ref  | index_b       | index_b | 5       | const                                  |    1 |   100.00 | Using where
 1 | SIMPLE      | table_a | null       | ref  | index_a       | index_a | 5       | fiddle_YRFDITQONPXNRMDBQSYV.table_b.id |    1 |   100.00 | null       

db<>fiddle here

4
  • But you do have a composite index -- The PK id is implicitly tacked onto index_b. And using table_b and index_b is the optimal way to start this query execution.
    – Rick James
    May 18 '18 at 19:25
  • You need more columns to avoid confusion with "covering", and to help differentiate whether "composite" is beneficial.
    – Rick James
    May 18 '18 at 20:05
  • Hi Rick, can you prove this statement "The PK id is implicitly tacked onto index_b" with a dbfiddle? I don't think there is a PK on either table I created. I've made an edit regarding your point about extra columns to avoid confusion with covering, thanks. May 20 '18 at 10:39
  • It's been irritating that there is little 'proof'. Run EXPLAIN FORMAT=JSON SELECT ..., then observe the key_parts. However, the 'hidden' PK when you don't have a PK does not show up even there.
    – Rick James
    May 20 '18 at 15:57

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.