Originally posted by Sandro Psaila
Can anyone suggest way or resources of how i can calculate the computational complexity of select query? i.e. its order O()
If you mean tools that will take some SQL statement (as well as info about the tables it's referring to) and estimate its complexity, I doubt it. A large reason the relational model exists is to give the DBMS widest possible latitude in picking the best algorithm, where "best" is a tradeoff between space complexity (how much RAM, disk, etc is used) and time complexity. (how much CPU time is used) That is to say that there is no straightforward mapping between the logical database value and its physical implementation.
So if you were a query planner, you'd probably want to recast the statement in relational algebra. (And you'd probably try many different permutations.) For each operation, you'd have one or two operands. You could work out the worst case, best case and average case number of rows for each operation. In some expressions, for example a series of cumulative restricts, the order is never going to be worse than O(N). In other cases you can cause the complexity to explode, for example by repeatedly performing cartesian products.
You should have a look at the extensive references in C.J. Date's Introduction to Database Systems, specifically those for chapter 17.