<p>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.</p>

<p>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.</p>

<p>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).</p>

<ul>
<li>Dániel Marx, <em>Tractable hypergraph properties for constraint satisfaction and conjunctive queries</em>, 2010. arxiv:<a href="http://arxiv.org/abs/0911.0801">0911.0801</a></li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2011-04-26T15:23:14.307Z
2011-04-26T21:42:41.867Z
2011-04-26T21:42:41.867Z
András Salamon
<p>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). </p>

CC BY-SA 3.0
2011-04-26T17:56:29.667Z
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
CC BY-SA 3.0
2011-04-26T18:36:32.410Z
@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
CC BY-SA 3.0
2011-05-01T19:19:09.677Z
@Tomek, @imz, well, it is being discussed [on the meta](http://meta.cstheory.stackexchange.com/questions/1128/should-we-discourage-low-rep-users-from-posting-remarks-as-answers) at the moment if we should allow commenting using answers or not.
Kaveh
CC BY-SA 3.0
2011-04-26T12:19:34.283Z
2011-04-26T12:19:34.283Z
mishaz
<p>Another way of answering this question is, "they don't!"  </p>

<p>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.</p>

<p>But, for "typical" DBMS workloads, such queries seem not to arise.</p>

CC BY-SA 3.0
2012-02-06T19:55:49.647Z
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
CC BY-SA 3.0
2011-07-21T17:40:19.577Z
2011-07-21T17:40:19.577Z
tjgreen
<p>Here's a more reality-concerned version of tigreen's answer from the point of a person who actually makes heavy use of (relational) databases: The whole point and complexity of their application is to structure them in a way they'd require as little amount of joins for each and every ever-needed query as possible and that's why they actually <strong>Do Work</strong>.
In other words do not expect databases to solve complex problems for you on their own - they wouldn't, but if used wisely they are a really handy and applicable instrument.</p>

CC BY-SA 3.0
2014-11-20T14:38:33.627Z
2014-11-20T14:38:33.627Z
whoever
<p>Joins are only quadratic over many-to-many relationships. These are relatively rare: in practice, most relationships and joins are 1-to-many, so they will take linear time if indexes/keys are defined. Queries with several many-to-many joins <em>are</em> a serious problem.</p>

CC BY-SA 3.0
2014-11-24T09:43:52.083Z
2014-11-24T09:43:52.083Z
reinierpost
<p>It seems to be known that to find an answer to a query <span class="math-container">$Q$</span> over a relational database <span class="math-container">$D$</span>, one needs time <span class="math-container">$|D|^{|Q|}$</span>, and one cannot get rid of the exponent <span class="math-container">$|Q|$</span>.</p>
<p>As <span class="math-container">$D$</span> can be very large, we wonder why databases work at all in practice.</p>
<p>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 <a href="https://stackoverflow.com/questions/6087275/what-is-the-maximal-size-complexity-of-a-db-query-that-is-tractable-in-practi">what the &quot;maximal&quot; size of the queries that are expected to be effectively answerable by a DB system in practice is</a>.)</p>
<h3>Notes on the exponent <span class="math-container">$|Q|$</span> not `removable'</h3>
<p>To show that the exponent <span class="math-container">$|Q|$</span> is not removable, one can use a query asking whether there exists a clique of size <span class="math-container">$n$</span> in the graph given by the database. To check whether a graph has an <span class="math-container">$n$</span>-clique is an NP-complete problem. Moreover, it is not fixed-parameter tractable, with parameter <span class="math-container">$n$</span>. Details can be found in, e.g., <br />
Libkin, L.: Elements Of Finite Model Theory. Springer (2004)<br />
or<br />
Papadimitriou, C.H., Yannakakis, M.: On the complexity of database queries. J.
Comput. Syst. Sci. 58(3), 407–427 (1999)</p>

CC BY-SA 3.0
2011-04-26T09:08:38.967Z
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
CC BY-SA 3.0
2011-04-26T09:24:55.567Z
@Sadeq, a query that could lead to higher complexity might be a one like this: "find all users that have a password equal to another user's password".
imz -- Ivan Zakharyaschev
CC BY-SA 3.0
2011-04-26T09:28:01.290Z
The last part of the question seem more appropriate for SO. Btw, IIRC remember that Immermann's Descriptive Complexity book had a small discussion at the last chapter that you may want to check.
Kaveh
CC BY-SA 3.0
2011-04-26T09:32:01.477Z
@Kaveh, thanks for the 2 points in your comment. As for the 1st one, I was actually going to reformulate the second part of the Q and pose that as a question for the real-world programmers at http://stackoverflow.net or the real-world DB admins at http://dba.stackexchange.com/ .
imz -- Ivan Zakharyaschev
CC BY-SA 3.0
2011-04-26T10:53:31.137Z
@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
CC BY-SA 3.0
2011-04-26T11:04:10.657Z
@Sadeq: Yes, the "maximal allowed" size of the query (your $k$) is the parameter that is meant in the question.
imz -- Ivan Zakharyaschev
CC BY-SA 3.0
2011-04-26T14:32:12.177Z
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
CC BY-SA 3.0
2011-04-26T15:16:12.823Z
@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](http://www.springerlink.com/content/q8pv2wq35btvj3fq/) useful, as well.
Sadeq Dousti
CC BY-SA 3.0
2011-04-27T03:54:13.917Z
@Sadeq, thanks for the correction. It is good that I used "IIRC". :)
Kaveh
CC BY-SA 3.0
2011-05-01T17:51:16.040Z
@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
<cc.complexity-theory><time-complexity><descriptive-complexity><db.databases>
Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?
imz -- Ivan Zakharyaschev
# Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?

(Asked by: username_0 on 2011-04-26)

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](https://stackoverflow.com/questions/6087275/what-is-the-maximal-size-complexity-of-a-db-query-that-is-tractable-in-practi).)

### 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)

**Tags:** cc.complexity-theory, time-complexity, descriptive-complexity, db.databases
> **Comments:**
> **username_1**: 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.  
> **username_0**: @Sadeq, a query that could lead to higher complexity might be a one like this: "find all users that have a password equal to another user's password".  
> **username_2**: The last part of the question seem more appropriate for SO. Btw, IIRC remember that Immermann's Descriptive Complexity book had a small discussion at the last chapter that you may want to check.  
> **username_0**: @Kaveh, thanks for the 2 points in your comment. As for the 1st one, I was actually going to reformulate the second part of the Q and pose that as a question for the real-world programmers at http://stackoverflow.net or the real-world DB admins at http://dba.stackexchange.com/ .  
> **username_1**: @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.  
> **username_0**: @Sadeq: Yes, the "maximal allowed" size of the query (your $k$) is the parameter that is meant in the question.  
> **username_3**: 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.  
> **username_1**: @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](http://www.springerlink.com/content/q8pv2wq35btvj3fq/) useful, as well.  
> **username_2**: @Sadeq, thanks for the correction. It is good that I used "IIRC". :)  
> **username_4**: @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.  

---

## 5 answers

### Answer by username_4 on 2011-04-26. Score: 16

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](http://arxiv.org/abs/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.


---

### Answer by username_5 on 2011-04-26. Score: 6

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).

> **Comments:**
> **username_0**: 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.)  
> **username_6**: @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.  
> **username_2**: @Tomek, @imz, well, it is being discussed [on the meta](http://meta.cstheory.stackexchange.com/questions/1128/should-we-discourage-low-rep-users-from-posting-remarks-as-answers) at the moment if we should allow commenting using answers or not.  

---

### Answer by username_7 on 2011-07-21. Score: 5

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.

> **Comments:**
> **username_8**: 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.  

---

### Answer by username_9 on 2014-11-20. Score: 4

Here's a more reality-concerned version of tigreen's answer from the point of a person who actually makes heavy use of (relational) databases: The whole point and complexity of their application is to structure them in a way they'd require as little amount of joins for each and every ever-needed query as possible and that's why they actually **Do Work**.
In other words do not expect databases to solve complex problems for you on their own - they wouldn't, but if used wisely they are a really handy and applicable instrument.


---

### Answer by username_10 on 2014-11-24. Score: 0

Joins are only quadratic over many-to-many relationships. These are relatively rare: in practice, most relationships and joins are 1-to-many, so they will take linear time if indexes/keys are defined. Queries with several many-to-many joins *are* a serious problem.


---

