The best way to calculate variations between 2 datasets?

Question

I am trying to write an application which identifies SQL query patterns. The program will trace all the queries executed in a database. When it identifies a considerable pattern change in the database, it will ask the DBA to tune the database. My tracing data looks like this.

The images show the query execution count from 2 different months. According to the images there is a considerable pattern chnage in query execution. Query2 is executed most of the times in the first dataset and Query3 is executed most of the time in second dataset. I want to mathamatically calcuate this pattern difference. One solution I can think of is calculating the percentage differene of execution count of each query and sum it all. If the value is greater than the predefined thresold I can send a notification to the DBA. Is there a better way to do that? Any data analysis technique that can be applied? Any libraries to do that?

Answer 1

What you are attempting to do is calculate the distance between two discrete probability density functions. The standard way to calculate this distance is via the Kullback-Leibler Divergence. It is defined as such:

$$D(P||Q) = \sum_iP(i)*log(\frac{P(i)}{Q(i)})$$

To be technically correct, this is not a metric in a mathematical sense because it is not symmetric and does not abide by the triangle inequality. But never the less it is a "distance" that is used a lot to compare distributions. From an information theoretical perspective, the KL divergence (given that you're using base 2 for the log) represents the number of bits it would take to encode distribution P as Q.

In your case, you would have to normalize each distribution to ensure that the sum is 1, and then calculate distance via the KL divergence. If you want a real metric you can use the Jensen-Shannon Divergence which is defined as: $${{\rm {JSD}}}(P\parallel Q)={\frac {1}{2}}D(P\parallel M)+{\frac {1}{2}}D(Q\parallel M)$$$$ {\displaystyle M={\frac {1}{2}}(P+Q)} M={\frac {1}{2}}(P+Q)$$

Hope this helps.