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 &quot;maximal&quot; 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)
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.