How to setup complex multi-column index for massive table

Question

I've searched what I could search on Google, SO, etc and haven't found an answer that would seem to fit what I'm looking for. I'm hesitant to make a post about this as I'm sure the answer is out there somewhere, I just haven't been able to find it :-\

I have setup a table in MySQL that I really could use some insight on. I have an existing index and it works pretty well in some cases, and others it takes 20+ seconds to run. Let me give you some background.

It's a MyISAM table with fixed rows (every column is an INT(11) ) and this table currently has 150,000,000 rows on it (10.2 GB total). I use this to track analytics run on the web software we use as other open source alternatives (like Piwik) were simply overkill and we needed direct access to the "stuff". That aside here's the basic structure of the table. (again all INT(11) as I read and understood that indexes with the same type and length are most effective).

id    region_id location_id action_id visitor_id ts        url_id employee_id

And here's the following range of values for each column.

150M  <20       <3000      <10       <40M        unix_time <20k   <200k

The query that I am trying to run is basically to get a distinct count of all the visitors that did a certain action for a location during a particular time. (in other words, must have location, action, and ts in the query)

SELECT COUNT(DISTINCT visitor_id) FROM table WHERE location_id = # AND region_id = # AND action_id = # AND ts BETWEEN x AND y

I have a multi-column index on location, region, action, ts and this query can take 20 to 30 seconds to execute. I also have one other index that is simple visitor_id, ts, and that one doesn't show any issues I assume because visitor_id has such a high cardinality. EXPLAIN SELECT shows I'm hitting the index and it seems to do as well as it could do.

id select_type table   type  possible_keys       key      key_len ref  rows  Extra
1  SIMPLE      table   range visitor_id,location location 13      NULL 23964 Using where

A few days ago that index used to be region, location, ts (no action) and I did some experimenting on my own. I filled up a table with dummy data up to 55,000,000 rows just to see what kind of indexes would give me an improvement, although the index I just barely tried worked great at 55,000,000 rows, it doesn't really improve much at 150,000,000 rows.

Another thing I've tried is that this query is actually pulling the days for a report, as in "Get all the visitors between day x and y, or the last 90 days". I tried making another column some time ago that just stored the unix time stamp equivalent to just represent the day (so the cardinality for the index would be substantially smaller). Oddly enough, the only thing that really seemed to do was increase the table size by adding a column, not really helping out with anything else (but this was also months ago probably around the 50,000,000 row mark, maybe the difference wasn't a big deal back then)

I know that you generally are supposed to have the index go from high-cardinality to a lower cardinality. I also know that MySQL blows up on ranged queries, and the rest of the index is useless if I put the ts at the beginning of the index.

The question that I turn to you for help for is what can I do so that I can improve the time it takes for this query to run? Am I really to the point where I need to break this table apart every 50M rows or so? Is there no index that can save that table or am I really bad at understanding how to setup an index? I'm open to other alternatives as well that may seem unorthodox, but at least will get the query time down.

Update

Since the posting of this question, the table now has nearly 159M rows. It looks like currently it's growing at about 10 million a month which will of course exponentially grow more. At this point with this crazy growth, am I better off splitting up the table into months or something equivalent?

Updated Update 10/5/17

Table is now 800 million and still going strong with really fast queries. Table is about 80GB with the data bing 30GB and the indexes being 50GB

Answer 1

To answer your second question:

MySQL does not have a parallel query execution engine, so even if you partition the query, you are still single threaded. This will eventually kill your scale.

However, you could partition the table by visitor_id. This would allow you to run several queries (one per partition) in parallel, all of them form:

SELECT COUNT(DISTINCT visitor_id) 
FROM table WHERE location_id = # 
AND region_id = # 
AND action_id = # AND ts BETWEEN x AND y
AND visitor_id BETWEEN <partition_start> and <partition_end>

The output of these parallel queries (which you could store in a temp table as they run) is trivially combinable into the final result by simply adding the distinct counts together.

This is very similar to sharding, but instead of doing it across machines, you are doing it on the same table. By picking a good hash function to generate visitor_id (for example, a modulo or bit reversal if the original id is generated with a AUTO_INCREMENT) you can ensure that all partitions are approximately equal sized.

The reason you want to partition by visitor_id and not one of the other columns is that it makes the DISTINCT additive across partitions. For example, consider a table with two partitions. One holds visitor_id 0-99 in one holds and 100-199. You can now express two queries that can run in parallel:

INSERT INTO TempResult(visitor_id)
SELECT COUNT(DISTINCT visitor_id) 
    FROM table WHERE location_id = # 
    AND region_id = # 
    AND action_id = # AND ts BETWEEN x AND y
    AND visitor_id BETWEEN 0 and 99

And this one in parallel:

INSERT INTO TempResults (visitor_id)
SELECT COUNT(DISTINCT visitor_id) 
    FROM table WHERE location_id = # 
    AND region_id = # 
    AND action_id = # AND ts BETWEEN x AND y
    AND visitor_id BETWEEN 100 and 199

Because you know the visitor_id is not overlapping between partitions, the final result is:

SELECT SUM(visitor_id) FROM TempResults

You would of course need to pick the partition boundaries in such a way that partitions have approximately the same size.

I will let ypercube file the answer to the indexing question as this is the one that deserves the reward.