MySQL Optimization – How to Optimize Multiple Calls to Procedure

Managed to solve this, these are the steps I followed:

Firstly, I contacted the Amazon RDS team by posting on their discussion forum, they confirmed it was the mysqld process taking up all this CPU - this eliminated a configuration fault with something else running on the physical server

Secondly I tracked down the source of the queries that were running:

SELECT `mytable`.* FROM `mytable` WHERE `mytable`.`foreign_key` = 231273 LIMIT 1 

I originally overlooked this as the cause, because none of these queries seemed to be taking particularly long when I monitored the show processlist output. After exhausting other avenues, I decided it might be worth following up....and I'm glad I did.

As you can see in the show processlist output, these queries were coming from a utlility server, which runs some tactical utility jobs that exist outside of our main application code. This is why they were not showing up as slow or causing issues in our new relic monitoring, because the new relic agent is only installed on our main app server.

Loosely following this guide:

http://www.mysqlperformanceblog.com/2007/02/08/debugging-sleeping-connections-with-mysql/

I was able to trace these queries to a specific running process on our utility server box. This was a bit of ruby code that was very inefficiently iterating through around 70,000 records, checking some field values and using those to decide whether it needs to create a new record in 'mytable.' After doing some analysis I was able to determine, the process was no longer needed so could be killed.

Something that was making matters worse, there seemed to be 6 instances of this same process running at one time due to the way the cron job was configured and how long each one took! I killed off these processes, and incredibly our CPU usage fell from around 100% to around 5%!

Based on reading the query plan you've posted from the explain output, you will probably have difficulty believing the explanation of how this query is actually being processed by the server... but the explanation does illustrate why the performance would not be good.

Since you've asked for the results to be ordered by `rangelength` and since the B-TREE index on (`rangestart`,`rangeend`) is poorly-suited to resolving "x between y and z" expressions, the optimizer has decided to use the index on `rangelength` to determine an order in which it will proceed to read every row, if necessary, in the entire table (type = index), in ascending order as sorted by the index on rangelength (type = index, key = rangelength), until it finds the first row where (extra = using where) the where clause is matched. Since the rows are being read in the desired order-by, the server can stop after the first row... so I would assume this query exhibits substantial variability depending on how much of the table or index has to be scanned to resolve any particular value.

There are two approaches that come to mind to improve this.

Option 1: The first suggestion would be to add an index that includes all three values you're sorting by and selecting by... but not for the usual reasons, because the query isn't going to use it quite like that.

ALTER TABLE ochrange ADD KEY(rangelength,rangeend,rangestart);

This is still far from the ideal index for this query, but it has three advantages over what you have now:

1. it's already sorted by rangelength
2. it narrows down the number of comparisons needed, because for any given rangelength, the rangestart values that are too high can be ignored
3. while it isn't truly a covering index, all of the values of interest in the WHERE clause are found within the index, so the optimizer should be able to qualify or disqualify the rows based on an index scan instead of having to read the table data, and might be able to do more.

Very important note on point 3: I am not saying this index will be used to look up the matching rows, because it can't exactly be used for that. It should at least, however, be used more effectively than the current plan because it contains values we need to use for filtering and because it may also allow out of range values for rangeend to be quickly eliminated, and among the remaining values, it may allow out of range values for rangestart to also be eliminated.

I would also recommend that the where clause be written in a less-ambiguous but logically equivalent form, to potentially make things a little bit easier on the optimizer:

  WHERE 20972128 
BETWEEN `rangestart` AND `rangeend` 
  ORDER BY `rangelength` ASC  LIMIT 1;

...becomes this:

  WHERE rangestart <= 20972128 
    AND rangeend >= 20972128
  ORDER BY rangelength ASC  LIMIT 1;

The (rangestart,rangeend) index, at first glance, seems like it would have been more useful, but a 2-column B-Tree isn't well-suited for finding values between the low and high bounds, like this.

The residential telephone directory is a fitting analogy for a two-column index on (last_name, first_name) and illustrates why this kind of index doesn't provide as much benefit as it would seem to.

In such a directory, given the last name "Smith" and first name "John," it is easy to find all of the people named Smith, and very easy to find first name John accompanying last name Smith. It is quite impossible, though, to use the index in a telephone directory to find all of the people with first name John regardless of last name.

What we're asking of the index in this query, whether written the original way or in my suggested way, is to find all of the rows where 'rangestart' <= 20972128 with accompanying rangeend >= 20972128 in the same row. This would be like trying to find all of the people in a telephone directory with a last name of Smith or any other last name that appears prior to Smith in the directory, and of those people, find those with the first name of John, or any other name that is lexically (alphabetically) "greater than" (after) John. The task would be tedious, and our only consolation is that we don't have to examine any of the pages in the directory that follow Smith, but we have to examine every entry on every preceding page before we can find what we are looking for.

Still, Option #1, adding a new index, seems worth a try. After testing with that index, it could also be worthwhile to add yet another index, this one on (rangelength,rangestart,rangeend), to see which one the optimizer prefers to use. Hopefully it will use one of them, and depending on the data in the table and the values in the query, it might alternate and it might not.

Option #2 is apparently a little bit "outside the box" in some people's minds, but it is a solution that I use for finding the specific block of IP addresses (IPv4 addresses are essentially INT UNSIGNED, with low/high boundaries) where a particular IP address lies, for geocoding. I caught some grief for suggesting this technique once over on Stack Overflow, but I can only conclude that the people voicing objections were simply "thinking small" because I really see no reason that this isn't an excellent solution. The topic I am referring to is spatial indexes. I assume the objections I encountered were based on the assumption that MySQL's Spatial Extensions were originally intended for manipulating geospatial data... but to limit their use to only latitude and longitude is not justified at all.

Spatial indexes in MySQL are implemented as R-Trees.

The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" in R-tree is for rectangle. Since all objects lie within this bounding rectangle, a query that does not intersect the bounding rectangle also cannot intersect any of the contained objects. At the leaf level, each rectangle describes a single object; at higher levels the aggregation of an increasing number of objects. This can also be seen as an increasingly coarse approximation of the data set.

^{— http://en.wikipedia.org/wiki/R-tree}

We are trying to find the position in a "space" of values where a particular value exists, so it makes sense to utilize an index structure designed to resolve which "spaces" a particular object fits inside... a spatial index.

Technically, the rangstart/rangeend continuum is a one-dimensional space, since it is made up of points within ranges that all exist on a continuous line, though I personally find it easier to explain if each pair of (rangestart, rangeend) is illustrated as a box, from (min,min) to (max,min) to (max,max) to (min,max) and back down to (min,min) again. It's easy from this example to see that if we have an index structure that can quickly determine which sets of boxes our particular point in space does or doesn't exist in, then we can quickly traverse that index to find the right spot. In this case, we'd have to find the right sets of boxes and then find the smallest box among those boxes (assuming my guess about the nature of the content of "rangelength" is correct) where our little point (effectively a "box" with 0 height and 0 width) fits in.

Rather than duplicate work that's already been done, I'll refer to Jeremy Cole's write-up of the subject:

http://blog.jcole.us/2007/11/24/on-efficiently-geo-referencing-ips-with-maxmind-geoip-and-mysql-gis/

I approach this slightly differently, but the principles are all there, and once you understand what's happening here, I suspect you will see this as a good fit for what you're trying to do and may implement it slightly differently than either of us.

But one final point about spatial indexes. Here's an example of my query where the spatial column is called 'node_polygon' and is of type GEOMETRY:

SELECT ...
  FROM geo_block b
 WHERE MBRContains(b.node_polygon,POINT(in_ip_unsigned,in_ip_unsigned))

I mention this query structure because it illustrates an important point. It is almost always the case that when you use a column as an argument to a function in the WHERE clause, that is bad design because it prevents indexes from being used to resolve the expression and will cause a full table scan or something analogous to it.

WHERE YEAR(birthday) = 1973;                                # bad
WHERE birthday >= '1973-01-01' AND birthday < '1974-01-01'; # good

The former expression has to evaluate YEAR() for the 'birthday' column in every row, while the latter expression can take advantage of an index on 'birthday' and do a range scan.

Spatial indexes are different, because the MBRContains() and MBRWithin() functions are understood by the optimizer to mean that the column and the constant should be evaluated with respect to the range that the constant identifies within the spatial index. These "functions" are rare examples of functions that still allow the optimizer to realize that it knows a better way to resolve the query than to evaluate the function against each row.

In my application, I don't need ordering, because the table is constrained such that no two entries can touch or overlap -- every given IP address either fits into exactly one block, or fits into no blocks at all. In your case, you still presumably need to order by rangelength, and what I would try, depending on whether you build the geometry structures lines or boxes, would be testing your performance while ordering by an appropriate geometry function, such as Area() or Glength(), to directly compare the size of the range, as opposed to using the rangelength column. I don't know which will perform better, geometric functions or ordering by the existing column rangelength.

Side note, as pointed out in comments, you should also not quote the integer that you're using in the where clause, since it's matching against an integer column and by quoting it you're causing an implicit cast of one thing to the other thing (either the literal is being cast to an integer or each value of rangestart/rangeend is being cast to a string) for comparison. The server is probably doing the right thing and casting the string to an integer but it would be better to query with the same data type as you're matching.