Measuring the complexity of SQL statements

user_26339 0
Viewed 23513

The complexity of methods in most programming languages can be measured in cyclomatic complexity with static source code analyzers. Is there a similar metric for measuring the complexity of a SQL query?

It is simple enough to measure the time it takes a query to return, but what if I just want to be able to quantify how complicated a query is?

[Edit/Note] While getting the execution plan is useful, that is not necessarily what I am trying to identify in this case. I am not looking for how difficult it is for the server to execute the query, I am looking for a metric that identifies how difficult it was for the developer to write the query, and how likely it is to contain a defect.

[Edit/Note 2] Admittedly, there are times when measuring complexity is not useful, but there are also times when it is. For a further discussion on that topic, see this question.

static-analysis cyclomatic-complexity sql
13 Answers

Here is an idea for a simple algorithm to compute a complexity score related to readability of the query:

  1. Apply a simple lexer on the query (like ones used for syntax coloring in text editors or here on SO) to split the query in tokens and give each token a class:
    • SQL keywords
    • SQL function names
    • string literals with character escapes
    • string literals without character escape
    • string literals which are dates or date+time
    • numeric literals
    • comma
    • parenthesis
    • SQL comments (--, /* ... */)
    • quoted user words
    • non quoted user words: everything else
  2. Give a score to each token, using different weights for each class (and differents weights for SQL keywords).
  3. Add the scores of each token.
  4. Done.

This should work quite well as for example counting sub queries is like counting the number of SELECT and FROM keywords.

By using this algorithm with different weight tables you can even measure the complexity in different dimensions. For example to have nuanced comparison between queries. Or to score higher the queries which use keywords or functions specific to an SQL engine (ex: GROUP_CONCAT on MySQL).

The algorithm can also be tweaked to take in account the case of SQL keywords: increase complexity if they are not consistently upper case. Or to account for indent (carriage return, position of keywords on a line)

Note: I have been inspired by @redcalx answer that suggested applying a standard formatter and counting lines of code. My solution is simpler however as it doesn't to build a full AST (abstract syntax tree).

user_3281150

In programming languages we have several methods to compute the time complexity or space complexity.

Similarly we could compare with sql as well like in a procedure the no of lines you have with loops similar to a programming language but unlike only input usually in programming language in sql it would along with input will totally depend on the data in the table/view etc to operate plus the overhead complexity of the query itself.

Like a simple row by row query

   Select * from table ; 
  // This will totally depend on no of 
       records say n hence O(n)

   Select max(input) from table;
   // here max would be an extra 
   overhead added to each 
   Therefore t*O(n) where t is max 
   Evaluation time
user_104974830
user_18665960

It's reasonably enough to consider complexity as what it would be if you coded the query yourself. If the table has N rows then,

  1. A simple SELECT would be O(N)
  2. A ORDER BY is O(NlogN)
  3. A JOIN is O(N*M)
  4. A DROP TABLE is O(1)
  5. A SELECT DISTINCT is O(N^2)
  6. A Query1 NOT IN/IN Query2 would be O( O1(N) * O2(N) )
user_85154720
Related