Creating an index on a timestamp to optimize query

I have a query of the following form:

SELECT * FROM MyTable WHERE Timestamp > [SomeTime] AND Timestamp < [SomeOtherTime]

I would like to optimize this query, and I am thinking about putting an index on timestamp, but am not sure if this would help. Ideally I would like to make timestamp a clustered index, but MySQL does not support clustered indexes, except for primary keys.

• MyTable has 4 million+ rows.
• Timestamp is actually of type INT.
• Once a row has been inserted, it is never changed.
• The number of rows with any given Timestamp is on average about 20, but could be as high as 200.
• Newly inserted rows have a Timestamp that is greater than most of the existing rows, but could be less than some of the more recent rows.

Would an index on Timestamp help me to optimize this query?

No question about it. Without the index, your query has to look at every row in the table. With the index, the query will be pretty much instantaneous as far as locating the right rows goes. The price you'll pay is a slight performance decrease in inserts; but that really will be slight.

You should definitely use an index. MySQL has no clue what order those timestamps are in, and in order to find a record for a given timestamp (or timestamp range) it needs to look through every single record. And with 4 million of them, that's quite a bit of time! Indexes are your way of telling MySQL about your data -- "I'm going to look at this field quite often, so keep an list of where I can find the records for each value."

Indexes in general are a good idea for regularly queried fields. The only downside to defining indexes is that they use extra storage space, so unless you're real tight on space, you should try to use them. If they don't apply, MySQL will just ignore them anyway.

I don't disagree with the importance of indexing to improve select query times, but if you can index on other keys (and form your queries with these indexes), the need to index on timestamp may not be needed.

For example, if you have a table with timestamp, category, and userId, it may be better to create an index on userId instead. In a table with many different users this will reduce considerably the remaining set on which to search the timestamp.

...and If I'm not mistaken, the advantage of this would be to avoid the overhead of creating the timestamp index on each insertion -- in a table with high insertion rates and highly unique timestamps this could be an important consideration.

I'm struggling with the same problems of indexing based on timestamps and other keys. I still have testing to do so I can put proof behind what I say here. I'll try to postback based on my results.

A scenario for better explanation:

1. timestamp 99% unique
2. userId 80% unique

3. category 25% unique

   • Indexing on timestamp will quickly reduce query results to 1% the table size
   • Indexing on userId will quickly reduce query results to 20% the table size
   • Indexing on category will quickly reduce query results to 75% the table size
   • Insertion with indexes on timestamp will have high overhead **
   • Despite our knowledge that our insertions will respect the fact of have incrementing timestamps, I don't see any discussion of MySQL optimisation based on incremental keys.
   • Insertion with indexes on userId will reasonably high overhead.
   • Insertion with indexes on category will have reasonably low overhead.

** I'm sorry, I don't know the calculated overhead or insertion with indexing.

If your queries are mainly using this timestamp, you could test this design (enlarging the Primary Key with the timestamp as first part):

CREATE TABLE perf (
  , ts INT NOT NULL
  , oldPK 
  , ... other columns 
, PRIMARY KEY(ts, oldPK)
, UNIQUE (oldPK)
) ENGINE=InnoDB ;

This will ensure that the queries like the one you posted will be using the clustered (primary) key.

Disadvantage is that your Inserts will be a bit slower. Also, If you have other indices on the table, they will be using a bit more space (as they will include the 4-bytes wider primary key).

The biggest advantage of such a clustered index is that queries with big range scans, e.g. queries that have to read large parts of the table or the whole table will find the related rows sequentially and in the wanted order (BY timestamp), which will also be useful if you want to group by day or week or month or year.

The old PK can still be used to identify rows by keeping a UNIQUE constraint on it.

You may also want to have a look at TokuDB, a MySQL (and open source) variant that allows multiple clustered indices.