Documentation Source Text

But as applications and schemas and queries grow more complex, a
clever query planner can greatly speed and simplify the work of application
development. 
There is amazing power in being about to tell
the database engine what content is desired, and then let the database
engine figure out the best way to retrieve that content.</p>

<p>Writing a good query planner is an inexact science.
The query planner must work with incomplete information.
It cannot determine how long any particular plan will take
without actually running that plan.  So when comparing two
or more plans to figure out which is "best", the query planner has to make
some guesses and assumption and those guesses and assumptions will 
sometimes be wrong. A good query plan is one that will
find the correct solution often enough that application
programmers only rarely need to get involved.</p>

<h3>2.1 Query Planning In SQLite</h3>

<p>SQLite computes joins using nested loops, 
one loop for each table
in the join.  (Additional loops might be inserted for IN
and OR operators in the WHERE clause.  SQLite considers those too,

    R-N1-C (cost: 13.43) <br>
    R-N1-P (cost: 14.74) <br>
    R-N2-S (cost: 15.08) <br>
</blockquote>

<p>And so forth.  There are 8 nodes in the TPC-H Q8 query, 
so this process repeats a total of 8
times.  In the general case of a K-way join, the storage requirements
is O(N) and the computation time is O(K*N), which is significantly faster
than the O(2<small><sup>K</sup></small>) exact solution.</p>

<p>But what value to choose for N?  One might try N=K.  This makes the
algorithm O(K<small><sup>2</sup></small>) 
which is actually still quite efficient, since the
maximum value of K is 64 and K rarely exceeds 10.