# Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?

It seems to be known that to find an answer to a query $Q$ over a relational database $D$, one needs time $|D|^{|Q|}$, and one cannot get rid of the exponent $|Q|$.

As $D$ can be very large, we wonder why databases work at all in practice.

Is it just a matter of the usual queries not being large at all in the real-world applications? (Then it is interesting to know what the usual size of the queries posed to relational database systems is, and what the "maximal" size of the queries that are expected to be effectively answerable by a DB system in practice is.)

### Notes on the exponent $|Q|$ not removable'

To show that the exponent $|Q|$ is not removable, one can use a query asking whether there exists a clique of size $n$ in the graph given by the database. To check whether a graph has an $n$-clique is an NP-complete problem. Moreover, it is not fixed-parameter tractable, with parameter $n$. Details can be found in, e.g.,
Libkin, L.: Elements Of Finite Model Theory. Springer (2004)
or
Papadimitriou, C.H., Yannakakis, M.: On the complexity of database queries. J. Comput. Syst. Sci. 58(3), 407–427 (1999)

-
Ordinary queries (like SELECT * FROM users WHERE username="abc" AND passwrod="xyz"`) are simple searches, which take O(|D|) to run. If there's an index on relevant database fields, it will take O(log |D|). I'm not into databases, but I don't think more complicated queries would take exponential time. –  Sadeq Dousti Apr 26 '11 at 9:08
@imz: In your example, the complexity is $O(|D|^2)$, which is still polynomial. It seems that, if there are k joins in the query, the complexity is $O(|D|^{k+1})$. This is a polynomial for fixed k, but I think for large k, running the query will be very slow in practice. Hence one must avoid too many joins at all costs. –  Sadeq Dousti Apr 26 '11 at 10:53
The time complexity is exponential in the length of a query in the worst case. This does not contradict that some long queries are fast. Database practitioners know which queries run fast in typical database engines, and they do not rely on the worst-case bound in terms of the length of the query anyway. –  Tsuyoshi Ito Apr 26 '11 at 14:32
@Kaveh: "Immerman's Descriptive Complexity book had a small discussion at the last chapter": Very good suggestion. Nitpicking: It is discussed in the penultimate chapter. @imz: You may find the paper Expressive Power of SQL useful, as well. –  Sadeq Dousti Apr 26 '11 at 15:16
@imz: "Does this graph have an n-clique" is not that common a query in practice. Most queries are more like the ones @Sadeq suggests, and have a strongly tree-like structure. Moreover, for really large databases even a completely linear query is too expensive, and one has to work with a sketch of the database. –  András Salamon May 1 '11 at 17:51

There are large classes of queries which are "easy", even in the worst case. In particular, if the class of queries contains conjunctive queries only and each query has bounded width (for instance treewidth, treewidth of its incidence graph, fractional hypertree width, or submodular width) then the query can be answered by using something like a join tree, together with brute force enumeration for the local parts of the query that deviate from the tree. This requires polynomial time, with the degree of the polynomial determined by the width parameter.

It seems that many queries encountered in practice are both conjunctive and have small width. So the polynomial runtime has low degree in this case.

Dániel Marx presented a paper at STOC 2010 on submodular width recently, the full version of which includes a nice summary of the various notions of width and how the CSP formulation relates to the database formalism (the conference version lacks this).

• Dániel Marx, Tractable hypergraph properties for constraint satisfaction and conjunctive queries, 2010. arxiv:0911.0801

This is not a complete answer, since it does not deal with the "typical" complexity of database queries, but even with worst-case analysis there are easy queries.

-
that one was at STOC 2010! ;) –  Daniel Apon Apr 26 '11 at 16:35
@Daniel: you are right, thanks for spotting the glitch. –  András Salamon Apr 26 '11 at 21:43

One can use queries Q_n to check whether a graph, represented as a database, contains a clique with n elements. To check whether a graph has a clique is an NP-complete problem. Moreover, it is not fixed-parameter tractable, with parameter n (which means D^n).

-
Please post additional explanations concerning the background of the question either as a "comment" (not an "answer")--with the "Add Comment" button below the question, or as an edit suggestion--with the "edit" link below the question. "Answers" are not for any discussions and additions to the question. (Participating here should be more convenient if you register as a non-anonymous user; then it's easier to track who said what in the discussions.) –  imz -- Ivan Zakharyaschev Apr 26 '11 at 17:56
@imz: He put it as an answer because he doesn't have a privilege to comment. One need to have at least 50 rep. to be able to comment everywhere. –  Tomek Tarczynski Apr 26 '11 at 18:36
@Tomek, @imz, well, it is being discussed on the meta at the moment if we should allow commenting using answers or not. –  Kaveh May 1 '11 at 19:19

Another way of answering this question is, "they don't!"

If you give a typical DBMS implementation a query containing a very large number of joins, it won't even make it past the planning/optimization phase (let alone evaluation), even if the query is acyclic or otherwise has very simple structure such as András alludes to above.

But, for "typical" DBMS workloads, such queries seem not to arise.

-
For complex queries the result of optimization phase is randomly chosen plan. This is not as bad as it sounds, because the execution path might still be "good enough", and there are many more reasons why optimization is hard beyond combinatorics of the number of joins. –  Tegiri Nenashi Feb 6 '12 at 19:55