2
$\begingroup$

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.

enter image description here enter image description here

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?

| improve this question | |
$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Just one question, is it feasible to simply calculate the vector different using the standard euclidean distance formula? $\endgroup$ – Syed Ali Hamza Jan 7 '17 at 19:48
  • 1
    $\begingroup$ In theory you could use any distance. KL is interesting because it has a interpretation in information theory. It is also used a lot to compare distributions in various fields. $\endgroup$ – Armen Aghajanyan Jan 8 '17 at 2:43

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.