5

In order to estimate the fastest function in various cases in a non fully deterministic context, I'm running an experiment calling one or the other at random and recording the duration of the operation on the production server.

I get this kind of table:

enter image description here

(numbers grow larger the more I wait)

A problem in interpreting those results is that the standard deviation is big (i.e. various random conditions led to very dispersed durations).

So I'm looking for a way to estimate when the difference between the sample sets is significative or not, some kind of statistical divergence, or, said otherwise, an estimation of the probability the observed difference isn't just random (Shannon theory maybe? Poisson's law?). If it's an accepted best practice or norm, it would be a bonus.

Please keep in mind that I can't keep in memory all samples (right now I just store the number of operation, the sum of durations and the sum of their squares so that I can compute the standard deviation).

  • 1
    The reasons I asked here and not e.g. stats.stackexchange.com are that 1) I think it should be a familiar problem for benchmarkers while it would be difficult to riguourously and precisely explain to statistics experts and 2) the algorithm to compute this with the minimal storage is a key part of the question – Denys Séguret Apr 22 '16 at 15:47
  • 1
    Your heavy operations there are writes. Writes against any sane, production database will be highly variable. The time it takes for a write to occur depends entirely on how many other operations already have a reader-lock (or writer-lock) on the block or row. The best thing you can do for those particular issues is to isolate your writes, if possible, use only or primarily inserts if possible, and optimize for write ops at the database level if needed. E.g., cluster on an auto-incrementing key, rather than a GUID ... – svidgen Apr 22 '16 at 18:14
  • 1
    Actually, let me take a half-step back. If you can correlate "slower" executions with any sort of server load or concurrent operations, or if the slower executions of an operation, using similar data, are significantly slower than the minimal/ideal execution time, you can be pretty certain it's "random" -- wherein "random" means, something else on the system is blocking the completion of the operation. – svidgen Apr 22 '16 at 18:44
  • 1
    In that case, given you don't have the individual samples to filter out the outliers, I'd consider running your tests again and simply drop (or accumulate the sum and sum of squares separately) any results greater than the average + one standard deviation of the data recorded previously. – Mark Hurd Apr 28 '16 at 10:38
  • 1
    @PSkocik No, you don't need to keep all the data, as you can rewrite the formula to be based, for example, on the sum of values and the sum of their squares. I usually use the Wedford algorithm : en.wikipedia.org/wiki/… – Denys Séguret Sep 28 '17 at 6:48
1

Standard deviation is only useful if you have a normal distribution (or similar). The problem with sampling is that often you have outliers or more than one peak - for example in your case you might have:

  • Queries that are not compiled and do not hit any in-memory table.
  • Queries that are compiled but do not hit in-memory tables.
  • Queries that are compiled and hit in-memory tables.

So potentially you could have three peaks, especially if the DB is memory constrained and the execution order is very relevant.

I would suggest that you draw a distribution graph for the worst offenders to understand how to normalize this data. Removing outliers will reduce the standard deviation.

0

You can:

  1. drop some of the large outliers to figure out a saner standard deviation
  2. run the experiment for longer so that the larger outliers become normal; basically change the scale of the experiment

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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