Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?
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.