Documentation Source Text

But for larger and more complex queries, such as
multi-way joins with many indices
and subqueries, there can be hundreds, thousands, or millions
of reasonable algorithms for computing the result.
The job of the query planner is to chose a single "best" query plan from
this multitude of possibilities.</p>

<p>The existence of a query planner is what makes SQL database engines
so amazingly useful and powerful.
(This is true of all SQL database engines, not just SQLite.)
The query planner frees the programmer from the chore of selecting
a particular query plan, and thereby allows the programmer to
focus more mental energy on higher-level application issues and on 
providing more value to the end user.  For simple queries where the choice
of query plan is obvious, this is convenient but not hugely important.
But as applications and schemas and queries grow more complex, a
................................................................................
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 to handle IN operators
in the WHERE clause, but those extra loops are not considered here.)

One or more indices might be used on each loop to speed the search,
or a loop might be a "full table scan" using only the original table.
Thus query planning decomposes into two subtasks:</p>
<ol>
<li> Picking the nested order of the various loops
<li> Choosing good indices for each loop
</ol>
<p>Picking the nesting order is generally the more challenging problem.
Once the nesting order of the join is established, the choice of indices
for each loop is normally obvious.</p>
................................................................................
<h3>2.2 The SQLite Query Planner Stability Guarantee</h3>

<p>SQLite will always pick the same query plan for any
given SQL statement as long as:
<ol type="a">
<li>the database schema does not change in significant ways such as 
    adding or dropping indices,</li>
<li>the ANALYZE command is not run, </li>
<li>SQLite is not compiled with [SQLITE_ENABLE_STAT3], and</li>
<li>the same version of SQLite is used.</li>
</ol>
The SQLite stability guarantee means that if all of your queries run 
efficiently
during testing, and if your application does not change the schema,
then SQLite will not suddenly decide to start using a different
................................................................................
in an embedded database like SQLite, and hence SQLite is careful to
ensure that plans do not change unexpectedly after deployment.</p>

<p>The SQLite stability guarantee applies equally to the legacy query planner 
and to the NGQP.</p>

<p>It is important to note that changing versions of SQLite might cause
changes in query plans, as new enhancements are added to the query planner.
The same version of SQLite it will
always pick the same query plan, but if you relink your application to use
a different version of SQLite, then query plans might change.  In rare
cases, an SQLite version change might lead to a performance regression.  
This is one reason
you should consider statically linking your applications against SQLite 
rather than try to use a system-wide SQLite shared library which might 
change without your knowledge or control.</p>

<h2>3.0 A Difficult Case</h2>

<p>
"TPC-H Q8" is a test query from the
<a href="http://www.tpc.org/tpch/">Transaction Processing Performance
................................................................................
being outside of it.</p>

<p>The arrows from the small circles labeled with "*" indicate the cost
of running each loop with no dependencies.  The outer loop must use this
*-cost.  Inner loops have the option of using the *-cost or a cost assuming
one of the other terms is in an outer loop, whichever gives the best
result.  One can think of the *-costs as a short-hand notation indicating
multiple arcs with that cost, one each from each of the other nodes in the
graph.  The graph is is therefore "complete", meaning that there are arcs
(some explicit and some implied) in both directions between every pair of 
nodes in the graph.</p>

<p>The problem of finding the best query plan is equivalent to finding
a minimum-cost path through the graph that visits each node
exactly once.</p>
................................................................................
    N2 (cost: 5.52) <br>
    P (cost: 7.71) <br>
</blockquote>

<p>The second step finds the four shortest paths to visit two nodes 
beginning with one of the four paths from the previous step.  In the
case where two or more paths are equivalent (they have the same set of
visited nodes, though possibly in a different order) then only the
first and lowest-cost path is retained.  We have:</p>

<blockquote>
    R-N1 (cost: 7.03) <br>
    R-N2 (cost: 9.08) <br>
    N2-N1 (cost: 11.04) <br>
    R-P {cost: 11.27} <br>
................................................................................
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 rarely exceeds 10.  
But that is not enough for the TPC-H Q8
problem.  With N=8 on TPC-H Q8 the N3 algorithm finds 
the solution R-N1-C-O-L-S-N2-P with a cost of 29.78.  
That is a big improvement over NN, but it is still
not optimal.  N3 finds the optimal solution for TPC-H Q8 
when N is 10 or greater.</p>

................................................................................
<li> The check-in has a "trunk" tag.
<li> The check-in has a child that has a "trunk" tag.
<li> The check-in has a parent that has a "trunk" tag.
</ol></p>

<p>
The first condition causes all of the trunk check-ins to be displayed and
the second and third cause check-ins that merge into or are derived from
the trunk to also be included.
The three conditions are implemented by the three OR-connected
EXISTS statements in the WHERE clause of the query.
The slowdown that occurred with the NGQP was caused by the second and
third conditions.  The problem is the same in each, so we will examine
just the second one.
The subquery of the second condition can be rewritten (with minor
................................................................................
and comment the use of CROSS JOIN carefully so that you can take it out
later if possible.  Avoid using CROSS JOIN early in the development
cycle as doing so is a premature optimization, which is well known to
be <a href="http://c2.com/cgi/wiki?PrematureOptimization">the root of
all evil</a>.</p>

<li><p><b>Use unary "+" operators to disqualify WHERE clause terms.</b>
If the query planner insists of selecting a poor-quality index for a particular
query when a much higher-quality index is available, then
[upluscontrol | careful use of unary "+" operators] in the WHERE clause
can force the query planner away from the poor-quality index.
Avoid using this trick if at all possible, and especially avoid it
early in the application development cycle.  Beware that
adding a unary "+" operator to an equality expression might change
the result of that expression if 

But for larger and more complex queries, such as
multi-way joins with many indices
and subqueries, there can be hundreds, thousands, or millions
of reasonable algorithms for computing the result.
The job of the query planner is to chose a single "best" query plan from
this multitude of possibilities.</p>


<p>Query planner are what make SQL database engines so amazingly useful and powerful.
(This is true of all SQL database engines, not just SQLite.)
The query planner frees the programmer from the chore of selecting
a particular query plan, and thereby allows the programmer to
focus more mental energy on higher-level application issues and on 
providing more value to the end user.  For simple queries where the choice
of query plan is obvious, this is convenient but not hugely important.
But as applications and schemas and queries grow more complex, a
................................................................................
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,
but for simplicity we will ignore them in this essay.)
One or more indices might be used on each loop to speed the search,
or a loop might be a "full table scan" that reads every row in the
table.  Thus query planning decomposes into two subtasks:</p>
<ol>
<li> Picking the nested order of the various loops
<li> Choosing good indices for each loop
</ol>
<p>Picking the nesting order is generally the more challenging problem.
Once the nesting order of the join is established, the choice of indices
for each loop is normally obvious.</p>
................................................................................
<h3>2.2 The SQLite Query Planner Stability Guarantee</h3>

<p>SQLite will always pick the same query plan for any
given SQL statement as long as:
<ol type="a">
<li>the database schema does not change in significant ways such as 
    adding or dropping indices,</li>
<li>the ANALYZE command is not rerun, </li>
<li>SQLite is not compiled with [SQLITE_ENABLE_STAT3], and</li>
<li>the same version of SQLite is used.</li>
</ol>
The SQLite stability guarantee means that if all of your queries run 
efficiently
during testing, and if your application does not change the schema,
then SQLite will not suddenly decide to start using a different
................................................................................
in an embedded database like SQLite, and hence SQLite is careful to
ensure that plans do not change unexpectedly after deployment.</p>

<p>The SQLite stability guarantee applies equally to the legacy query planner 
and to the NGQP.</p>

<p>It is important to note that changing versions of SQLite might cause
changes in query plans.
The same version of SQLite it will
always pick the same query plan, but if you relink your application to use
a different version of SQLite, then query plans might change.  In rare
cases, an SQLite version change might lead to a performance regression.  
This is one reason
you should consider statically linking your applications against SQLite 
rather than use a system-wide SQLite shared library which might 
change without your knowledge or control.</p>

<h2>3.0 A Difficult Case</h2>

<p>
"TPC-H Q8" is a test query from the
<a href="http://www.tpc.org/tpch/">Transaction Processing Performance
................................................................................
being outside of it.</p>

<p>The arrows from the small circles labeled with "*" indicate the cost
of running each loop with no dependencies.  The outer loop must use this
*-cost.  Inner loops have the option of using the *-cost or a cost assuming
one of the other terms is in an outer loop, whichever gives the best
result.  One can think of the *-costs as a short-hand notation indicating
multiple arcs, one from each of the other nodes in the
graph.  The graph is is therefore "complete", meaning that there are arcs
(some explicit and some implied) in both directions between every pair of 
nodes in the graph.</p>

<p>The problem of finding the best query plan is equivalent to finding
a minimum-cost path through the graph that visits each node
exactly once.</p>
................................................................................
    N2 (cost: 5.52) <br>
    P (cost: 7.71) <br>
</blockquote>

<p>The second step finds the four shortest paths to visit two nodes 
beginning with one of the four paths from the previous step.  In the
case where two or more paths are equivalent (they have the same set of
visited nodes, though possibly in a different order) only the
first and lowest-cost path is retained.  We have:</p>

<blockquote>
    R-N1 (cost: 7.03) <br>
    R-N2 (cost: 9.08) <br>
    N2-N1 (cost: 11.04) <br>
    R-P {cost: 11.27} <br>
................................................................................
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.  
But that is not enough for the TPC-H Q8
problem.  With N=8 on TPC-H Q8 the N3 algorithm finds 
the solution R-N1-C-O-L-S-N2-P with a cost of 29.78.  
That is a big improvement over NN, but it is still
not optimal.  N3 finds the optimal solution for TPC-H Q8 
when N is 10 or greater.</p>

................................................................................
<li> The check-in has a "trunk" tag.
<li> The check-in has a child that has a "trunk" tag.
<li> The check-in has a parent that has a "trunk" tag.
</ol></p>

<p>
The first condition causes all of the trunk check-ins to be displayed and
the second and third cause check-ins that merge into or fork from
the trunk to also be included.
The three conditions are implemented by the three OR-connected
EXISTS statements in the WHERE clause of the query.
The slowdown that occurred with the NGQP was caused by the second and
third conditions.  The problem is the same in each, so we will examine
just the second one.
The subquery of the second condition can be rewritten (with minor
................................................................................
and comment the use of CROSS JOIN carefully so that you can take it out
later if possible.  Avoid using CROSS JOIN early in the development
cycle as doing so is a premature optimization, which is well known to
be <a href="http://c2.com/cgi/wiki?PrematureOptimization">the root of
all evil</a>.</p>

<li><p><b>Use unary "+" operators to disqualify WHERE clause terms.</b>
If the query planner insists on selecting a poor-quality index for a particular
query when a much higher-quality index is available, then
[upluscontrol | careful use of unary "+" operators] in the WHERE clause
can force the query planner away from the poor-quality index.
Avoid using this trick if at all possible, and especially avoid it
early in the application development cycle.  Beware that
adding a unary "+" operator to an equality expression might change
the result of that expression if