Documentation Source Text

hd_keywords {next generation query planner}
</tcl>
<h1 align="center">The Next Generation Query Planner</h1>

<h2>1.0 Executive Summary</h2>

<p>Given an SQL statement, the task of the "query planner" is to figure
out the best algorithm to use to accomplish that statement.
Beginning with SQLite version 3.8.0, the query planner component has been
rewritten so that it runs faster and generates better query plans.  The
rewrite is called the "next generation query planner" or "NGQP".
</p>

<p>This article overviews the importance of query planning, describes some
of the problems inherent to query planning, and outlines how the NGQP
................................................................................
providing more value to the end user.  For simple queries where the choice
of query plans is obvious, this may not seem like a big deal.
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 leave the database
engine to worry over the details of how to best 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 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>The query engine in SQLite computes joins using nested loops, 
one loop for each table
in the join (plus possibly additional loops for IN operators in the
WHERE cause).
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 the task of query planner
breaks down 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>

<tcl>hd_fragment qpstab {query planner stability guarantee}</tcl>
<h3>2.2 The SQLite Query Planner Stability Guarantee</h3>

<p>SQLite will always pick the exact 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>
................................................................................
This 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 new and different
query plan once your application is in the field, and thereby possibly
causing a performance problem.  If your application works in the lab, it
will continue working the same way after deployment.</p>

<p>Enterprise-class SQL database engines do not normally make this guarantee.

In client/server SQL database engines, the server normally keeps running 
statistics on the sizes of tables and on the quality of indices and uses

those statistics to aid in query planning.  As content is added, deleted,
or changed in the database, these statistics will evolve and may cause the
query planner to suddenly start using a different query plan for some
particular query.  Usually the new plan will be better for the
evolving structure of the content.  But sometimes the new query plan will
cause a performance reduction.  With a client/server database engine, there
is typically a Database Administrator (DBA) on hand to deal with these 
rare problems as they come up.  But DBAs are not available to fix problems 
in an embedded database like SQLite, and hence SQLite goes to great care 
to make sure that 
query plans do not change unexpectedly after deployment.</p>

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

<p>It is important to note that any particular version of SQLite 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, this 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 An Insurmountable Problem</h2>

<p>
"TPC-H Q8" is a test query from the
<a href="http://www.tpc.org/tpch/">Transaction Processing Performance
Council</a>.  The query planners in SQLite versions 3.7.17 and earlier 
do not choose good plans for TPC-H Q8.  And it has been determined that 
no amount
................................................................................
of tweaking of the legacy query planner will fix that.  In order to find
a good solution to the TPC-H Q8 query, and to continue improving the 
quality of SQLite's query planner, it became necessary to redesign the
query planner.  This section tries to explain why this redesign was
necessary and how the NGQP is different and addresses the TPC-H Q8 problem.
</p>

<h3>3.1 The Query</h3>

<p>
TPC-H Q8 is an eight-way join.
As observed above, the main task of the query planner is
to figure out the best nesting order of the eight loops in order to minimize
the work needed to complete the join.
A simplified model of this problem for the case of TPC-H Q8 is shown
by the following (hand drawn) diagram:
</p>

<center>
<img src="images/qp/tpchq8.gif">
</center>

<p>
................................................................................
GROUP BY, or DISTINCT clause. So for TPC-H Q8,
the graph above is a reasonable representation of what needs to be computed.
The general case involves a lot of extra complication, which for clarity
is neglected in the remainder of this article.</p>

<h3>3.3 Finding The Best Query Plan</h3>

<p>Since its inception, SQLite has always used the rough equivalent of
the "Nearest Neighbor" or "NN" heuristic when searching for the best query plan.
The NN heuristic makes a single traversal of the graph, always chosing
the lowest-cost arc as the next step.  
The NN heuristic works surprisingly well in most cases.
And NN is fast, so that SQLite is able to quickly find good plans
for even large 64-way joins.  In contrast, other SQL database engines that
do more extensive searching tend to bog down when the
................................................................................
formula for selecting N might change in subsequent releases.</p>

<tcl>hd_fragment hazards {hazards of upgrading to the NGQP}</tcl>
<h2>4.0 Hazards Of Upgrading To NGQP</h2>

<p>For most applications, upgrading from the legacy query planner to the NGQP
is a no-brainer.  Just drop in the newer version of SQLite and recompile and
the application will run faster.  There are no API changes or changes
to compilation procedures.</p>

<p>But as with any query planner change, upgrading to the NGQP does carry
a small risk of introducing performance regressions.  The problem here is
not that the NGQP is incorrect or buggy.  More likely,
the legacy query planner merely stumbled over a better query plan
by stupid luck and the NGQP is not quite so lucky.</p>
................................................................................
<p>Fossil is both the version-control system for SQLite and also a test
platform for SQLite.  Whenever changes or enhancements are made to SQLite, 
Fossil is one of the first applications to test and evaluate those
changes.  So Fossil was an early adopter of the NGQP.  And NGQP caused a
performance issue in Fossil, as described in the sequel.</p>

<p>One of the many reports that Fossil makes available is a timeline of
changes to a single branch showing all merges in and out of that branch.
See [http://www.sqlite.org/src/timeline?nd&n=200&r=trunk] for a typical

example of such a report.  Generating such a report normally takes just
a few milliseconds.  But after upgrading to the NGQP we noticed that
this one report was taking closer to 10 seconds for the trunk of the
repository.</p>

<p>The core query used to generate the branch timeline is shown below.
(Readers are not expected to understand the details of this query.
................................................................................
                   WHERE tagid=11 AND tagtype>0 AND pid=blob.rid)
        OR EXISTS(SELECT 1 FROM plink JOIN tagxref ON rid=pid
                   WHERE tagid=11 AND tagtype>0 AND cid=blob.rid))
 ORDER BY event.mtime DESC
 LIMIT 200;
</pre></blockquote>

<p>This query is only a two-way join, but it contains four subqueries,
one in the result set and three more in the WHERE clause.  This query is not
especially complicated, but even so it replaces hundreds or 
perhaps thousands of lines of procedural code.</p>

<p>The gist of the query is this:  Scan down the EVENT table looking
for the most recent 200 check-ins that satisfy one of three conditions:

<ol>
<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>


These three conditions are implemented by the three OR-connected
EXISTS statements in the WHERE clause of the query.</p>

<p>The slowdown that occurred with the NGQP was caused by the last two
of the three conditions.  We will examine the middle condition
more closely.</p>

<p>The subquery of the second condition can be rewritten (with minor
and immaterial simplifications) as follows:</p>

<blockquote><pre>
SELECT 1
  FROM plink JOIN tagxref ON tagxref.rid=plink.cid
 WHERE tagxref.tagid=$trunk
   AND plink.pid=$ckid;
................................................................................
);
CREATE INDEX tagxref_i1 ON tagxref(tagid, mtime);
</pre></blockquote>

<p>There are only two reasonable ways to implement this query.
(There are many other possible algorithms, but none of the
others are contenders for being the "best" algorithm and are thus
ignored here.)<p.

<ol>
<li value=1><p>
Find all children of checkin $ckid and test each one to see if
it has the $trunk tag.
<li value=2><p>
Find all checkins with the $trunk tag and test each one to see if
it is a child of $ckid.
</ol>

<p>
Intuitively, we humans understand that algorithm (1) is best.
Each check-in is only likely to have a handful of children (having one child is
most common case) and each one of those children can be checked for the
$trunk tag in logarithmic time.  And, indeed, algorithm (1) is the
faster choice in practice.  But the NGQP is not equipped with intuition.  The
NGQP has to use hard math, and algorithm (2) works out to be slightly
better mathematically.  This is because, in the absence of other information,
the NGQP must assume that the indices PLINK_I1 and TAGXREF_I1 are of
equal quality and are equally selective.  Algorithm (2) uses one field
of the TAGXREF_I1 index and both fields of the PLINK_I1 index whereas
algorithm (1) only uses the first field of each index.  Since 
algorithm (2) uses more index material, the NGQP is correct
to judge it to be the better algorithm.  The scores are close and
algorithm (2) just barely squeaks ahead of algorithm (1).  But
algorithm (2) really is the correct choice here.
</p>

<p>
Unfortunately, algorithm (2) is many times slower than algorithm (1) in
this application.
</p>

<p>
The problem is that the indices are not of equal quality.
A check-in is likely to only have one child check-in.  There might be two
or three in some cases, but the usual number will be one.  So the first
................................................................................
(2013-06-24) on the SQLite repository, roughly 38 out of every 100 rows
in the TAGXREF table assign "trunk" tags to checkins.  Hence searching on just
the first field of the TAGXREF_I1 index is practically useless.
</p>

<p>
The NGQP has no way of knowing that TAGXREF_I1 is almost useless in this
query, unless we have run [ANALYZE] on the database.  After [ANALYZE] is
run, statistics on the quality of the various indices are stored in the
SQLITE_STAT1 table.  Having access to this statistical information,
the NGQP easily choses algorithm (1) as the best algorithm, by a wide
margin.</p>

<p>Why didn't the legacy query planner choose algorithm (2)?
Easy: because the nearest neighbor greedy algorithm used by the legacy
query planner never even considered algorithm (2).
Algorithm (1) was the only option that the legacy
query planner gave any thought to.  And hence

the legacy query planner just happened to make the faster choice by









stupid luck.</p>






<h3>4.2 Fixing The Problem</h3>

<p>Running [ANALYZE] on the repository database immediately fixed the
performance problem.  However, we want Fossil to be robust and to always
work quickly regardless of whether or not its repository has been analyzed.
For this reason, the query was modify to use the CROSS JOIN operator 
instead of simply JOIN.  SQLite will not reorder the tables of a CROSS JOIN.
This is a feature designed specifically to allow knowledgeable programmers
to enforce a particular loop nesting order.  Once the join
was changed to CROSS JOIN (the addition of a single keyword) the NGQP was
forced to chose the faster algorithm (1) regardless of whether or not
statistical information had been gathered using ANALYZE.</p>

<p>The previous sentence called algorithm (1) "faster", but this
is not strictly true.  Algorithm (1) is faster in common repositories, but
it is possible (in theory) to construct a repository composed mostly of
new branches, one check-in per branch, with many branches originating from
the same parent.  In that case, TAGXREF_I1 would become more selective
than PLINK_I1 and algorithm (2) really would be the faster choice.
However such branch-heavy repositories are unlikely to appear in actual
practice.</p>

hd_keywords {next generation query planner}
</tcl>
<h1 align="center">The Next Generation Query Planner</h1>

<h2>1.0 Executive Summary</h2>

<p>Given an SQL statement, the task of the "query planner" is to figure
out the best algorithm to accomplish that statement.
Beginning with SQLite version 3.8.0, the query planner component has been
rewritten so that it runs faster and generates better query plans.  The
rewrite is called the "next generation query planner" or "NGQP".
</p>

<p>This article overviews the importance of query planning, describes some
of the problems inherent to query planning, and outlines how the NGQP
................................................................................
providing more value to the end user.  For simple queries where the choice
of query plans is obvious, this may not seem like a big deal.
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 leave the database
engine to work 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 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>The query engine in 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>

<tcl>hd_fragment qpstab {query planner stability guarantee}</tcl>
<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>
................................................................................
This 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 new and different
query plan once your application is in the field, and thereby possibly
causing a performance problem.  If your application works in the lab, it
will continue working the same way after deployment.</p>

<p>Enterprise-class client/server SQL database engines do not normally 
make this guarantee.
In client/server SQL database engines, the server will keeps continuously
updated statistics on the sizes of tables and on the quality of indices 
and the query planner those statistics to aid in selecting the best plans.
As content is added, deleted, or changed in the database, the statistics 
will evolve and may cause the query planner to begin using a different 

query plan for some particular query.  Usually the new plan will be better 
for the evolving structure of the data.  But sometimes the new query plan will
cause a performance reduction.  With a client/server database engine, there
is typically a Database Administrator (DBA) on hand to deal with these 
rare problems as they come up.  But DBAs are not available to fix problems 
in an embedded database like SQLite, and hence SQLite goes to great care 

to make sure that plans do not change unexpectedly after deployment.</p>

<p>This stability guarantee applies equally to the legacy query planner in
SQLite 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, this 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
Council</a>.  The query planners in SQLite versions 3.7.17 and earlier 
do not choose good plans for TPC-H Q8.  And it has been determined that 
no amount
................................................................................
of tweaking of the legacy query planner will fix that.  In order to find
a good solution to the TPC-H Q8 query, and to continue improving the 
quality of SQLite's query planner, it became necessary to redesign the
query planner.  This section tries to explain why this redesign was
necessary and how the NGQP is different and addresses the TPC-H Q8 problem.
</p>

<h3>3.1 Query Details</h3>

<p>
TPC-H Q8 is an eight-way join.
As observed above, the main task of the query planner is
to figure out the best nesting order of the eight loops in order to minimize
the work needed to complete the join.
A simplified model of this problem for the case of TPC-H Q8 is shown
by the following diagram:
</p>

<center>
<img src="images/qp/tpchq8.gif">
</center>

<p>
................................................................................
GROUP BY, or DISTINCT clause. So for TPC-H Q8,
the graph above is a reasonable representation of what needs to be computed.
The general case involves a lot of extra complication, which for clarity
is neglected in the remainder of this article.</p>

<h3>3.3 Finding The Best Query Plan</h3>

<p>Prior to version 3.8.0, SQLite always used the
the "Nearest Neighbor" or "NN" heuristic when searching for the best query plan.
The NN heuristic makes a single traversal of the graph, always chosing
the lowest-cost arc as the next step.  
The NN heuristic works surprisingly well in most cases.
And NN is fast, so that SQLite is able to quickly find good plans
for even large 64-way joins.  In contrast, other SQL database engines that
do more extensive searching tend to bog down when the
................................................................................
formula for selecting N might change in subsequent releases.</p>

<tcl>hd_fragment hazards {hazards of upgrading to the NGQP}</tcl>
<h2>4.0 Hazards Of Upgrading To NGQP</h2>

<p>For most applications, upgrading from the legacy query planner to the NGQP
is a no-brainer.  Just drop in the newer version of SQLite and recompile and
the application will run faster.  There are no API changes nor modifications
to compilation procedures.</p>

<p>But as with any query planner change, upgrading to the NGQP does carry
a small risk of introducing performance regressions.  The problem here is
not that the NGQP is incorrect or buggy.  More likely,
the legacy query planner merely stumbled over a better query plan
by stupid luck and the NGQP is not quite so lucky.</p>
................................................................................
<p>Fossil is both the version-control system for SQLite and also a test
platform for SQLite.  Whenever changes or enhancements are made to SQLite, 
Fossil is one of the first applications to test and evaluate those
changes.  So Fossil was an early adopter of the NGQP.  And NGQP caused a
performance issue in Fossil, as described in the sequel.</p>

<p>One of the many reports that Fossil makes available is a timeline of
changes to a single branch showing all merges in and out of that branch.  See
<a href="http://www.sqlite.org/src/timeline?nd&n=200&r=trunk">http://www.sqlite.org/src/timeline?nd&n=200&r=trunk</a>
for a typical
example of such a report.  Generating such a report normally takes just
a few milliseconds.  But after upgrading to the NGQP we noticed that
this one report was taking closer to 10 seconds for the trunk of the
repository.</p>

<p>The core query used to generate the branch timeline is shown below.
(Readers are not expected to understand the details of this query.
................................................................................
                   WHERE tagid=11 AND tagtype>0 AND pid=blob.rid)
        OR EXISTS(SELECT 1 FROM plink JOIN tagxref ON rid=pid
                   WHERE tagid=11 AND tagtype>0 AND cid=blob.rid))
 ORDER BY event.mtime DESC
 LIMIT 200;
</pre></blockquote>

<p>This query is not

especially complicated, but even so it replaces hundreds or 
perhaps thousands of lines of procedural code.

The gist of the query is this:  Scan down the EVENT table looking
for the most recent 200 check-ins that satisfy any one of three conditions:

<p><ol>
<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>
These 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 last two
of the three conditions.  We will examine the middle condition
more closely.

The subquery of the second condition can be rewritten (with minor
and immaterial simplifications) as follows:</p>

<blockquote><pre>
SELECT 1
  FROM plink JOIN tagxref ON tagxref.rid=plink.cid
 WHERE tagxref.tagid=$trunk
   AND plink.pid=$ckid;
................................................................................
);
CREATE INDEX tagxref_i1 ON tagxref(tagid, mtime);
</pre></blockquote>

<p>There are only two reasonable ways to implement this query.
(There are many other possible algorithms, but none of the
others are contenders for being the "best" algorithm and are thus
ignored here.)</p>

<ol type="1">
<li value=1><p>
Find all children of checkin $ckid and test each one to see if
it has the $trunk tag.
<li value=2><p>
Find all checkins with the $trunk tag and test each one to see if
it is a child of $ckid.
</ol>

<p>
Intuitively, we humans understand that algorithm-1 is best.
Each check-in is likely to have few children (one child is
the most common case) and each child can be checked for the
$trunk tag in logarithmic time.  Indeed, algorithm-1 is the
faster choice in practice.  But the NGQP has no intuition.  The
NGQP must use hard math, and algorithm-2 is slightly
better mathematically.  This is because, in the absence of other information,
the NGQP must assume that the indices PLINK_I1 and TAGXREF_I1 are of
equal quality and are equally selective.  Algorithm-2 uses one field
of the TAGXREF_I1 index and both fields of the PLINK_I1 index whereas
algorithm-1 only uses the first field of each index.  Since 
algorithm-2 uses more index material, the NGQP is correct
to judge it to be the better algorithm.  The scores are close and
algorithm-2 just barely squeaks ahead of algorithm-1.  But
algorithm-2 really is the correct choice here.
</p>

<p>
Unfortunately, algorithm-2 is slower than algorithm-1 in
this application.
</p>

<p>
The problem is that the indices are not of equal quality.
A check-in is likely to only have one child check-in.  There might be two
or three in some cases, but the usual number will be one.  So the first
................................................................................
(2013-06-24) on the SQLite repository, roughly 38 out of every 100 rows
in the TAGXREF table assign "trunk" tags to checkins.  Hence searching on just
the first field of the TAGXREF_I1 index is practically useless.
</p>

<p>
The NGQP has no way of knowing that TAGXREF_I1 is almost useless in this
query, unless [ANALYZE] has been run on the database.  The [ANALYZE] 
gathers statistics on the quality of the various indices are stored the
result in SQLITE_STAT1 table.  Having access to this statistical information,
the NGQP easily choses algorithm-1 as the best algorithm, by a wide
margin.</p>

<p>Why didn't the legacy query planner choose algorithm-2?
Easy: because the nearest neighbor greedy algorithm used by the legacy
query planner never even considered algorithm-2.  Graphs of the planning
problem look like this:</p>


<center>
<img src="images/qp/fqp1.gif">
</center>

<p>
In the "without ANALYZE" case on the left, the NN algorithm chooses 
loop P (PLINK) as the outer loop because 4.9 is less than 5.3, resulting
in the selection of algorithm-1. NN completely misses the fact that 
5.2+4.4 makes a slightly cheaper plan than 4.9+4.8. But the NNN algorithm 
does select the lower cost plan, resulting in algorithm-2.
</p>

<p>
Note that after ANALYZE has been run, algorithm-1
will be selected by both NN and NNN.
</p>

<h3>4.2 Fixing The Problem</h3>

<p>Running [ANALYZE] on the repository database immediately fixed the
performance problem.  However, we want Fossil to be robust and to always
work quickly regardless of whether or not its repository has been analyzed.
For this reason, the query was modify to use the CROSS JOIN operator 
instead of simply JOIN.  SQLite will not reorder the tables of a CROSS JOIN.
This is a feature designed specifically to allow knowledgeable programmers
to enforce a particular loop nesting order.  Once the join
was changed to CROSS JOIN (the addition of a single keyword) the NGQP was
forced to chose the faster algorithm-1 regardless of whether or not
statistical information had been gathered using ANALYZE.</p>

<p>The previous sentence called algorithm-1 "faster", but this
is not strictly true.  Algorithm-1 is faster in common repositories, but
it is possible to construct a repository composed mostly of
new branches, one check-in per branch, and with many branches originating from
the same parent.  In that case, TAGXREF_I1 would become more selective
than PLINK_I1 and algorithm-2 really would be the faster choice.
However such branch-heavy repositories are unlikely to appear in
practice.</p>