Seek paginated query gets progressively slower on a big table

I have a biggish table of events. (5.3 million rows at the moment). I need to traverse this table mostly from the beginning to the end in a linear fashion. Mostly no random seeks. The data currently includes about 5 days of these events.

Due to the size of the table I need to paginate the results, and the internet tells me that "seek pagination" is the best method.

However this method works great and fast for traversing the first 3 days, after this mysql really begins to slow down. I've figured out it must be something io-bound as my cpu usage actually falls as the slowdown starts.

I do belive this has something to do with the 2-column sorting I do, and the usage of filesort, maybe Mysql needs to read all the rows to sort my results or something. Indexing correctly might be a proper fix, but I've yet been unable to find an index that solves my problem.

The compexifying part of this database is the fact that the ids and timestamps are NOT perfectly in order. The software requires the data to be ordered by timestamps. However when adding data to this database, some events are added 1 minute after they have actually happened, so the autoincremented ids are not in the chronological order.

As of now, the slowdown is so bad that my 5-day traversal never finishes. It just gets slower and slower...

I've tried indexing the table on multiple ways, but mysql does not seem to want to use those indexes and EXPLAIN keeps showing "filesort". Indexing is used on the where-statement though.

The workaround I'm currently using is to first do a full table traversal and load all the row ids and timestamps in memory. I sort the rows in the python side of the software and then load the full data in smaller chunks from mysql as I traverse (by ids only). This works fine, but is quite unefficient due to the total of 2 traversals of the same data.

The schema of the table:

CREATE TABLE `events` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `server` varchar(45) DEFAULT NULL,
  `software` varchar(45) DEFAULT NULL,
  `timestamp` bigint(20) DEFAULT NULL,
  `data` text,
  `event_type` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `index3` (`timestamp`,`server`,`software`,`id`),
  KEY `index_ts` (`timestamp`)
) ENGINE=InnoDB AUTO_INCREMENT=7410472 DEFAULT CHARSET=latin1;

The query (one possible line):

SELECT software,
       server,
       timestamp,
       id,
       event_type,
       data
FROM   events
WHERE  ( server = 'a58b'
         AND ( software IS NULL
                OR software IN ( 'ASD', 'WASD' ) ) )
       AND ( timestamp, id ) > ( 100, 100 )
       AND timestamp <= 200
ORDER  BY timestamp ASC,
          id ASC
LIMIT  100;

The query is based on https://blog.jooq.org/2013/10/26/faster-sql-paging-with-jooq-using-the-seek-method/ (and some other postings with the same idea). I belive it is called "seek pagination with seek predicate". The basic gist is that I have a starting timestamp and ending timestamp, and I need to get all the events with the software on the servers I've specifed OR only the server-specific events (software = NULL). The weirdish ( )-stuff is due tho python constructing the queries based on the parameters it is given. I left them visible if by a small chance they might have some effect.

I'm excepting the traversal to finish before the heat death of the universe.

Solution

First change

AND ( timestamp, id ) > ( 100, 100 )

AND (timestamp > 100 OR timestamp = 100 AND id > 100)

This optimisation is suggested in the official documentation: Row Constructor Expression Optimization

Now the engine will be able to use the index on (timestamp). Depending on cardinality of the columns server and software, that could be already fast enough.

An index on (server, timestamp, id) should improve the performance farther.

If still not fast enough, i would suggest a UNION optimization for

AND (software IS NULL OR software IN ('ASD', 'WASD'))

That would be:

(
    SELECT software, server, timestamp, id, event_type, data
    FROM events
    WHERE server = 'a58b'
      AND software IS NULL
      AND (timestamp > 100 OR timestamp = 100 AND id > 100)
      AND timestamp <= 200
    ORDER BY timestamp ASC, id ASC
    LIMIT 100
) UNION ALL (
    SELECT software, server, timestamp, id, event_type, data
    FROM events
    WHERE server = 'a58b'
      AND software = 'ASD'
      AND (timestamp > 100 OR timestamp = 100 AND id > 100)
      AND timestamp <= 200
    ORDER BY timestamp ASC, id ASC
    LIMIT 100
) UNION ALL (
    SELECT software, server, timestamp, id, event_type, data
    FROM events
    WHERE server = 'a58b'
      AND software = 'WASD'
      AND (timestamp > 100 OR timestamp = 100 AND id > 100)
      AND timestamp <= 200
    ORDER BY timestamp ASC, id ASC
    LIMIT 100
)
ORDER BY timestamp ASC, id ASC
LIMIT 100

You will need to create an index on (server, software, timestamp, id) for this query.