5

I'm seeking guidance on how to think through the minimum number of indices you need for a table in which you a performing different combinations of queries on the same set of columns. Ideally, your answer would abstract some rules of thumb from this specific example (if that's possible).

This bulleted list represents three different query conditions commonly performed on my table:

  • WHERE race_type = ? AND recordable_type = ? AND active = ?
  • WHERE race_type = ? AND recordable_id = ? AND recordable_type = ? AND active = ?
  • WHERE user_id = ? AND race_type = ? AND recordable_id = ? AND recordable_type = ? AND active = ?

Note: user_id (int), race_type (varchar), recordable_id (int), recordable_type (varchar), active (boolean)

I could create individual multi-column indices for each of these, but you DB performance experts out there might approach it a different way.

If I need to provide more info in order to get the best answer, please, let me know.

1
  • Please show current table definition (CREATE TABLE...). Is user_id a part of primary key?
    – Devart
    Nov 16, 2011 at 8:37

6 Answers 6

8
+25

If your conditions are hierarchical (like in your example) you can use a combined index. DBMS's have trouble working with multiple indexes at the same time. Although it is possible and they try to make the best out of such situation.

This does not change the fact that you should try to have a specific index for a certain where clause. If more WHEREs' indexes can be combined to a single one, then you free up some space and CPU cycles.

Let's start out by specifying an index for every WHERE:

index1 (race_type, recordable_type, active)
index2 (race_type, recordable_id, recordable_type, active)
index3 (user_id, race_type, recordable_id, recordable_type, active)

In general you can optimize your order by ascending cardinality. Cardinality is the number of possible values that a column will have in your dataset. In your example active is a boolean. (Please note that the fact that boolean can have only two values is not really important. It could be int if you know that it will have only two values: 0 and 1).

The low cardinality of your active field means that with a single lookup we can eliminate half of the possible records (depending on your dataset of course). After this step your first index will look like:

index1 (active, race_type, recordable_type)

Besides cardinality you should pay attention to any logical hierarchy between the fields. Without knowing exactly what these names mean I surmise as a rule of thumb that certain race types will have their own recordables. - This won't eliminate the possibility of a recordable being used with more than one race type of course, but you have to choose an order and this seems to be the more logical one. - So we will use the race_type, recordable_type order.

Now let's take alook at the second index. You introduced recordable_id here. Without knowing your dataset I can safely assume that the cardinality of recordable_id will be biger than recordable_type's. In other words there will be more id's than types. Also I suspect a hierarchy between type and id (smells like one-to-many). So let's put it after the type like:

index2 (active, race_type, recordable_type, recordable_id)

Now it's time to pay attention to an other important angle. Indexes have their own cost on your HDD (esentially free) and CPU cycles when modifying your DB. The subset of any index can be used starting from left to right. index2 essentially contains index1 as it is index1 + recordable_id, so you can just get rid of it and end up with a single one.

Along cometh user_id. As an ID field it suggests high cardinality (many possible values), but note that it is not a rule that the "higher the cardinality the later a filed will be". We rather used cardinality as a beacon to help spot hierarchy-like relation between the fields. (And shrink index sizes).

Does user_id point to the individual contestant who's data we are looking at (many-many possibilities)? Or is it the client who uploaded the data (very few possbilities)? It is hard to tell. You can just append it to our existing index2 and you will end up with a single index that can be used in all three secnarios:

search_index (active, race_type, recordable_type, recordable_id, user_id)

... or it might worth having a second index for this scanario...

Your question is special because you only use = in your where clause. There are many other considerations if you had something like AND (race_type = 1 OR race_type=8) Not to mention > or <. Also if you use ORDER BY that can be factored in into the indexes you use.

2
  • In general you can optimize your order by ascending cardinality (...) The low cardinality of your active field means that with a single lookup we can eliminate half of the possible records - how is that? The higher the cardinality, the more values are eliminated by every equality check.
    – Tgr
    May 19, 2014 at 6:23
  • @Tgr You're right if you are combining the equaity check with some non-indexed operations. However, ordering by low to high cardinality might catch natural hierarchy (dependence) between the fields, and it has no real drawback if your queries are operating within the index. - Then again, these are just general pointers it all depends on the dataset.
    – vbence
    May 21, 2014 at 16:31
3

First step is to use EXPLAIN on the queries you are considering for optimization. MySQL explain will return vital information on which indices will be used to accomplish the query, and will help you optimize your queries.

In my experience I have seen tables take on any number of composite index permutations, it's really based on your application and which queries you will be issuing the most.

You should also consider changing your varchar columns to ids linking to lookup tables. It will add some extra schema to your database but you get the following benefits:

  1. If you ever need to change the value of the column, you only have to change one row, vs thousands.

  2. All columns you are considering for indices will be numeric, which by nature will be faster than varchars, and will give more overhead before reaching the maximum index length limit.

2

imho

alter table your_table
add index ( race_type, recordable_type, active, user_id, recordable_id);
// watch-out the max length allowed for an index

the common found columns are race_type, recordable_type, active,
and I think by building an index will all 5 columns will fit all search patterns.

please let me know if the proposal does not work well

1

Mysql uses left most indexes, that means that, if index is complex(contains more that one column) query traverses index from left to right in index column list, if there is void(query's where or join statement doesn't have than further index columns won't be used)

quick tip, for fields with few possible values you can write query, that it overcounts all posible values which means that right more columns of index still can be used(ex., where (active = 0 or active = 1) and ...)

1

In your case proper index is user_id + race_type + recordable_id + recordable_type + active in any order. That was easy. You asked about general approach? Here it is.

Understanding indexes is very important. The theem is complex, so my answer is big. I suggest reading my answer and exmaples, than docs.

All columns used in where, order and group by should have indexes. Mysql uses binary trees for indexing. That means, that indexes can be used partialy from left to right without gaps. E.g. we have compound index over (a, b). So: WHERE a = 1 AND b = 1 - uses full index, WHERE a = 1 - uses half of index - binary tree indexes can be used partialy from the left, WHERE b = 1 - uses fullscan (no index can be used), WHERE (a = 0 OR a = 1) AND b = 1 - uses fullscan (mysql does not support several searching branches).

Some queries can not use indexes at all. E.g. queries with "OR" statement (binary tree indexes are сonsequent). Or col LIKE '%...%' - binary indexes can only be used partialy from the left.

Algorythm of applying proper indexes: get all unique column names you use in "WHERE". Take all unique column names from order and group by in the way they appear in query and add to fields from "WHERE" (add from the right). Than minify indexes, so they can still be used by mysql.

You don't have any orders in your queries, but orders also need indexes. So I made your example a bit more complicated:

  • WHERE race_type = ? AND recordable_type = ? AND active = ? ORDER BY race_type
  • WHERE race_type = ? AND recordable_id = ? AND recordable_type = ? AND active = ? ORDER BY date DESC,
  • WHERE user_id = ? AND race_type = ? AND recordable_id = ? AND recordable_type = ? AND active = ? ORDER BY date ASC

    1. Indexes from "WHERE": "race_type + recordable_type + active", "race_type + recordble_id + recordable_type + active" and "user_id + race_type + recordable_id + recordable_type + active".

    2. Adding indexes from sorts:

      • race_type + recordable_type + active + race_type
      • race_type + recordble_id + recordable_type + active + date
      • user_id + race_type + recordable_id + recordable_type + active + date
    3. Minify indexes:

      • recordable_type + active + race_type (used both for "WHERE" and "ORDER")
      • recordable_type + active + race_type + recordble_id + date (transposed two columns, but leaved "date" at the end for sorting)
      • no changes (we can not move "user_id" after "date" and try to include previous index in this one)

See, index #1 is included in index #2, so throw index #1 away. Finaly we have two indexes:

  • recordable_type + active + race_type + recordble_id + date
  • user_id + race_type + recordable_id + recordable_type + active + date

Don't forget to index by algorythm columns used in update and delete queries.

0

You have these fields in WHERE conditions: user_id, race_type, recordable_id, recordable_type and active. Some of them may be repeated the specified in condition.

I ordered them in a following way:

* WHERE race_type = ? AND recordable_type = ? AND active = ?
* WHERE race_type = ? AND recordable_type = ? AND active = ? AND recordable_id = ?
* WHERE race_type = ? AND recordable_type = ? AND active = ? AND recordable_id = ? AND user_id = ?

It allows us to create one composite index:

ALTER TABLE table_name
  ADD INDEX IX_table_name (race_type, recordable_type, active, recordable_id, user_id);

If the table has another indexes or primary key, add a USE INDEX clause to use named index:

SELECT * FROM table_name USE INDEX IX_table_name
WHERE
  race_type = ? AND recordable_type = ? AND active = ? AND recordable_id = ? AND user_id = ?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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