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)
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. $\endgroup$