Documentation Source Text

Check-in [e1646aea15]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Work toward documenting the NGQP changes.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:e1646aea15d8a7c4c15d303893c39fbb0849d30c
User & Date: drh 2013-06-24 19:23:40
Context
2013-06-25
01:44
Second draft of the NGQP document. check-in: e09abae6c3 user: drh tags: trunk
2013-06-24
19:23
Work toward documenting the NGQP changes. check-in: e1646aea15 user: drh tags: trunk
2013-06-21
19:06
Add documentation for the fts4 notindexed option. check-in: 968222aa1c user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to pages/changes.in.

    37     37         <a href="http://www.sqlite.org/src/timeline">
    38     38         http://www.sqlite.org/src/timeline</a>.</p>
    39     39       }
    40     40       hd_close_aux
    41     41       hd_enable_main 1
    42     42     }
    43     43   }
           44  +
           45  +chng {2013-08-15 (3.8.0)} {
           46  +<li>Cut-over to the [next generation query planner] for faster and better query plans.
           47  +<li>Added the [FTS4 notindexed option], allowing non-indexed columns in an FTS4 table.
           48  +}
           49  +
    44     50   chng {2013-05-20 (3.7.17)} {
    45     51   <li>Add support for [memory-mapped I/O].
    46     52   <li>Add the [sqlite3_strglob()] convenience interface.
    47     53   <li>Assigned the integer at offset 68 in the [database header] as the
    48     54       [Application ID] for when SQLite is used as an [application file-format].
    49     55       Added the [PRAGMA application_id] command to query and set the Application ID.
    50     56   <li>Report rollback recovery in the [error log] as SQLITE_NOTICE_RECOVER_ROLLBACK.

Changes to pages/index.in.

    91     91   
    92     92   </td>
    93     93   <td width="20"></td><td bgcolor="#044a64" width="1"></td><td width="20"></td>
    94     94   <td valign="top">
    95     95   <h3>Current Status</h3>
    96     96   
    97     97   <p><ul>
    98         -<li><a href="releaselog/3_7_17.html">Version 3.7.17</a>
           98  +<li><a href="releaselog/3_8_0.html">Version 3.8.0</a>
    99     99   of SQLite is recommended for all new development.
   100         -Upgrading from all previous SQLite versions
          100  +Upgrading from version 3.7.17 is optional.
          101  +Upgrading from all other prior versions of SQLite
   101    102   is recommended.</li>
   102    103   </ul></p>
   103    104   
   104    105   <h3>Common Links</h3>
   105    106   
   106    107   <p><ul>
   107    108   <li> <a href="features.html">Features</a> </li>

Changes to pages/queryplanner-ng.in.

    12     12     hd_puts [string trimright $txt]\n
    13     13     hd_puts "</pre></table></center>\n"
    14     14   }
    15     15   hd_keywords {next generation query planner}
    16     16   </tcl>
    17     17   <h1 align="center">The Next Generation Query Planner</h1>
    18     18   
    19         -<blockquote>
    20         -<p style="border:1px solid black; color: red;"><i><b>
    21         -This article is about proposed enhancements to SQLite that have not yet
    22         -been implemented.  Everything mentioned here is preliminary and subject
    23         -to change.  If and when the plans outlined in this document are
    24         -completed, this document will be revised into something along the lines
    25         -of "How The Query Planner Works".</b></i></p>
    26         -</blockquote>
    27         -
    28         -<h2>Introduction</h2>
           19  +<h2>1.0 Executive Summary</h2>
           20  +
           21  +<p>Given an SQL statement, the task of the "query planner" is to figure
           22  +out the best algorithm to use to accomplish that statement.
           23  +Beginning with SQLite version 3.8.0, the query planner component has been
           24  +rewritten so that it runs faster and generates better query plans.  The
           25  +rewrite is called the "next generation query planner" or "NGQP".
           26  +</p>
           27  +
           28  +<p>This article overviews the importance of query planning, describes some
           29  +of the problems inherent to query planning, and outlines how the NGQP
           30  +solves those problems.</p>
           31  +
           32  +<p>The NGQP is almost always better than the legacy query planner.
           33  +However, there may exist legacy applications that unknowingly depend on 
           34  +undefined and/or suboptimal behavior in the legacy query planner, and
           35  +upgrading to the NGQP on those legacy applications could cause performance
           36  +regressions.  This risk is considered and suggestions for reducing the
           37  +risk are outlined.</p>
           38  +
           39  +<h2>2.0 Background</h2>
           40  +
           41  +<p>For simple queries against a single table with few indices, there is usually
           42  +an obvious choice for the best algorithm.
           43  +But for larger and more complex queries, multi-way joins with many indices
           44  +and subqueries, there can be hundreds, thousands, or millions
           45  +of "reasonable" algorithms for computing the result.
           46  +The job of the query planner is to chose a single "best" query plan from
           47  +this multitude of possibilities.</p>
           48  +
           49  +<p>The existence of a query planner is what makes SQL database engines
           50  +so useful and powerful.
           51  +The query planner frees the programmer from the chore of selecting
           52  +a particular query plan, and thereby allows the programmer to
           53  +focus more mental energy on higher-level application issues and on 
           54  +providing more value to the end user.  For simple queries where the choice
           55  +of query plans is obvious, this may not seem like a big deal.
           56  +But as applications and schemas and queries grow more complex, a
           57  +clever query planner can greatly speed and simplify the work of application
           58  +development. 
           59  +There is amazing power in being about to tell
           60  +the database engine what content is desired, and then leave the database
           61  +engine to worry over the details of how to best retrieve that content.</p>
           62  +
           63  +<p>Writing a good query planner is an inexact science.
           64  +The query planner must work with incomplete information.
           65  +It cannot determine how long any particular plan will take
           66  +without actually running that plan.  So when comparing two
           67  +or more plans to figure out which is "best", the query planner has to make
           68  +some guesses and assumption and those guesses and assumptions that will 
           69  +sometimes be wrong. A good query plan is one that will
           70  +find the correct solution often enough that application
           71  +programmers only rarely need to get involved.</p>
           72  +
           73  +<h3>2.1 Query Planning In SQLite</h3>
           74  +
           75  +<p>The query engine in SQLite computes joins using nested loops, 
           76  +one loop for each table
           77  +in the join (plus possibly additional loops for IN operators in the
           78  +WHERE cause).
           79  +One or more indices might be used on each loop to speed the search,
           80  +or a loop might be a "full table scan" using only the original table.
           81  +Thus the task of query planner
           82  +breaks down into two subtasks:</p>
           83  +<ol>
           84  +<li> Picking the nested order of the various loops
           85  +<li> Choosing good indices for each loop
           86  +</ol>
           87  +<p>Picking the nesting order is generally the more challenging problem.
           88  +Once the nesting order of the join is established, the choice of indices
           89  +for each loop is normally obvious.</p>
           90  +
           91  +<tcl>hd_fragment qpstab {query planner stability guarantee}</tcl>
           92  +<h3>2.2 The SQLite Query Planner Stability Guarantee</h3>
           93  +
           94  +<p>SQLite will always pick the exact same query plan for any
           95  +given SQL statement as long as:
           96  +<ol type="a">
           97  +<li>the database schema does not change in significant ways such as 
           98  +    adding or dropping indices,</li>
           99  +<li>the ANALYZE command is not run, </li>
          100  +<li>SQLite is not compiled with [SQLITE_ENABLE_STAT3], and</li>
          101  +<li>the same version of SQLite is used.</li>
          102  +</ol>
          103  +This stability guarantee means that if all of your queries run efficiently
          104  +during testing, and if your application does not change the schema,
          105  +then SQLite will not suddenly decide to start using a new and different
          106  +query plan once your application is in the field, and thereby possibly
          107  +causing a performance problem.  If your application works in the lab, it
          108  +will continue working the same way after deployment.</p>
          109  +
          110  +<p>Enterprise-class SQL database engines do not normally make this guarantee.
          111  +In client/server SQL database engines, the server normally keeps running 
          112  +statistics on the sizes of tables and on the quality of indices and uses
          113  +those statistics to aid in query planning.  As content is added, deleted,
          114  +or changed in the database, these statistics will evolve and may cause the
          115  +query planner to suddenly start using a different query plan for some
          116  +particular query.  Usually the new plan will be better for the
          117  +evolving structure of the content.  But sometimes the new query plan will
          118  +cause a performance reduction.  With a client/server database engine, there
          119  +is typically a Database Administrator (DBA) on hand to deal with these 
          120  +rare problems as they come up.  But DBAs are not available to fix problems 
          121  +in an embedded database like SQLite, and hence SQLite goes to great care 
          122  +to make sure that 
          123  +query plans do not change unexpectedly after deployment.</p>
          124  +
          125  +<p>This stability guarantee applies equally to the legacy query planner in
          126  +SQLite and to the NGQP.</p>
          127  +
          128  +<p>It is important to note that any particular version of SQLite will
          129  +always pick the same query plan, but if you relink your application to use
          130  +a different version of SQLite, then query plans might change.  In rare
          131  +cases, this might lead to a performance regression.  This is one reason
          132  +you should consider statically linking your applications against SQLite 
          133  +rather than try to use a system-wide SQLite shared library which might 
          134  +change without your knowledge or control.</p>
          135  +
          136  +<h2>3.0 An Insurmountable Problem</h2>
    29    137   
    30    138   <p>
    31    139   "TPC-H Q8" is a test query from the
    32    140   <a href="http://www.tpc.org/tpch/">Transaction Processing Performance
    33         -Council</a>.  SQLite version 3.7.17 and earlier do not choose a good
    34         -query plan for TPC-H Q8.  This article explains why that is and what
    35         -we intend to do about it for SQLite version 3.7.18 and later.
          141  +Council</a>.  The query planners in SQLite versions 3.7.17 and earlier 
          142  +do not choose good plans for TPC-H Q8.  And it has been determined that 
          143  +no amount
          144  +of tweaking of the legacy query planner will fix that.  In order to find
          145  +a good solution to the TPC-H Q8 query, and to continue improving the 
          146  +quality of SQLite's query planner, it became necessary to redesign the
          147  +query planner.  This section tries to explain why this redesign was
          148  +necessary and how the NGQP is different and addresses the TPC-H Q8 problem.
    36    149   </p>
    37    150   
    38         -<h2>The Query</h2>
          151  +<h3>3.1 The Query</h3>
    39    152   
    40    153   <p>
    41    154   TPC-H Q8 is an eight-way join.
    42         -As SQLite uses only loop joins, the main task of the query planner is
    43         -to figure out the best nesting order of the 8 loops in order to minimize
    44         -the amount of CPU time and I/O required to complete the join.
          155  +As observed above, the main task of the query planner is
          156  +to figure out the best nesting order of the eight loops in order to minimize
          157  +the work needed to complete the join.
    45    158   A simplified model of this problem for the case of TPC-H Q8 is shown
    46    159   by the following (hand drawn) diagram:
    47    160   </p>
    48    161   
    49    162   <center>
    50    163   <img src="images/qp/tpchq8.gif">
    51    164   </center>
    52    165   
    53    166   <p>
    54         -In the diagram, each of the 8 terms in the FROM clause of the query is
          167  +In the diagram, each of the 8 tables in the FROM clause of the query is
    55    168   identified by a large circle with the label of the FROM-clause term:
    56    169   N2, S, L, P, O, C, N1 and R.
    57    170   The arcs in the graph represent the cost of computing each term assuming
    58    171   that the origin of the arc is in an outer loop.  For example, the
    59    172   cost of running the S loop as an inner loop to L is 2.30 whereas the
    60    173   cost of running the S loop as an outer loop to L is 9.17.</p>
    61    174   
    62         -<p>The "cost" is these cases is logarithmic.  With nested loops, the CPU time
    63         -and I/O is multiplied, not added.  But it easier to think of a
    64         -graph with additive weights and so the graph shows the logarithm of the
          175  +<p>The "cost" here is logarithmic.  With nested loops, the work
          176  +is multiplied, not added.  But it customary to think of graphs
          177  +with additive weights and so the graph shows the logarithm of the
    65    178   various costs.  The graph shows a cost advantage of S being inside of
    66    179   L of about 6.87, but this translates into the query running about
    67    180   963 times faster when S loop is inside of the L loop rather than
    68    181   being outside of it.</p>
    69    182   
    70    183   <p>The arrows from the small circles labeled with "*" indicate the cost
    71    184   of running each loop with no dependencies.  The outer loop must use this
    72    185   *-cost.  Inner loops have the option of using the *-cost or a cost assuming
    73    186   one of the other terms is in an outer loop, whichever gives the best
    74         -result.</p>
          187  +result.  One can think of the *-costs as a short-hand notation indicating
          188  +multiple arcs with that cost, one each from each of the other nodes in the
          189  +graph.  The graph is is therefore "complete", meaning that there are arcs
          190  +(some explicit and some implied) in both directions between every pair of 
          191  +nodes in the graph.</p>
    75    192   
    76    193   <p>The problem of finding the best query plan is equivalent to finding
    77    194   a minimum-cost path through the graph shown above that visits each node
    78    195   exactly once.</p>
    79    196   
    80         -<h3>Complications</h3>
          197  +<h3>3.2 Complications</h3>
    81    198   
    82    199   <p>The presentation of the query planner problem above is a simplification.
    83         -Keep in mind, first of all, that the costs are merely estimates.  We cannot
          200  +The costs are estimates.  We cannot
    84    201   know what the true cost of running a loop is until we actually run the loop.
    85    202   SQLite makes guesses for the cost of running a loop based on
    86    203   the availability of indices and constraints found in the WHERE
    87    204   clause.  These guesses are usually pretty good, but they can sometimes be
    88    205   off.  Using the [ANALYZE] command to collect additional statistical
    89    206   information about the database can sometimes enable SQLite to make better
    90         -guesses about the cost.  But sometimes [ANALYZE] does not help.</p>
          207  +guesses about the cost.</p>
    91    208   
    92         -<p>Further, the costs are not really a single number as shown above.
    93         -SQLite computes several different costs for each loop that apply at
          209  +<p>The costs are comprised of multiple numbers, not a single number as
          210  +shown in the graph.
          211  +SQLite computes several different estimated costs for each loop that apply at
    94    212   different times.  For example, there is a "setup" cost that is incurred
    95    213   just once when the query starts.  The setup cost is the cost of computing
    96    214   an [automatic indexing | automatic index] for a table that does not already
    97         -have an index.  There is an additional startup cost which is the cost of
    98         -initializing the loop for each iteration of the outer loop.  Then there
          215  +have an index.  Then there
    99    216   is the cost of running each step of the loop.  Finally, there is an estimate
   100    217   of the number rows generated by the loop, which is information needed in
   101         -estimating the costs of inner loops.</p>
          218  +estimating the costs of inner loops.  Sorting costs may come into play
          219  +if the query has an ORDER BY clause.</p>
   102    220   
   103         -<p>A general query need not be a simple graph as shown above.
   104         -Dependencies need not be on a single other loop.  For example, you might
   105         -have a query where a particular loop depends on two or more other terms
   106         -being in outer loops, instead of just a single term.  We cannot really
   107         -draw a graph for these kinds of queries since there is no way for an
   108         -arc to originate at two or more nodes at once.</p>
          221  +<p>In a general query, dependencies need not be on a single loop, and hence
          222  +the matrix of dependencies might not be representable as a graph.
          223  +For example, one of the WHERE clause constraints might be
          224  +S.a=L.b+P.c, implying that the S loop must be an inner loop of both
          225  +L and P.  Such dependencies cannot be drawn as a graph
          226  +since there is no way for an arc to originate at two or more nodes at
          227  +once.</p>
   109    228   
   110         -<p>In the TPC-H Q8 query, the setup and startup costs are all negligible
   111         -and all dependencies are from a single other node. So for this case, at least,
          229  +<p>If the query contains an ORDER BY clause or a GROUP BY clause or if
          230  +the query uses the DISTINCT keyword then it is advantageous to select a 
          231  +path through the graph that causes rows to naturally appear in sorted order, 
          232  +so that no separate sorting step is required.  Automatic elimination of 
          233  +ORDER BY clauses
          234  +can make a large performance difference, so this is another factor
          235  +that needs to be considered in a complete implementation.</p>
          236  +
          237  +<p>In the TPC-H Q8 query, the setup costs are all negligible,
          238  +all dependencies are between individual nodes, and there is no ORDER BY,
          239  +GROUP BY, or DISTINCT clause. So for TPC-H Q8,
   112    240   the graph above is a reasonable representation of what needs to be computed.
   113         -The general case involves a lot of extra complication.
   114         -But the point of this article is to explain what is going on, and that
   115         -extra complication does not aid in the explanation, and is therefore
   116         -omitted.</p>
          241  +The general case involves a lot of extra complication, which for clarity
          242  +is neglected in the remainder of this article.</p>
   117    243   
   118         -<h2>Finding The Best Query Plan</h2>
          244  +<h3>3.3 Finding The Best Query Plan</h3>
   119    245   
   120         -<p>Since its inception, SQLite has always used the rough equilvalent of
   121         -the "Nearest Neighbor" or "NN" heuristic when searching for the best query plan
   122         -for a particular query.  The NN heuristic chooses the lowest-cost arc
   123         -to follow next.  The NN heuristic works surprisingly well in most cases.
   124         -And NN is fast, so that SQLite is able to quickly find good query plans
   125         -for even large 64-way joins.  In contrast, other SQL database engines such
   126         -as Oracle, PostgreSQL, MySQL, and SQL Server tend to bog down when the
          246  +<p>Since its inception, SQLite has always used the rough equivalent of
          247  +the "Nearest Neighbor" or "NN" heuristic when searching for the best query plan.
          248  +The NN heuristic makes a single traversal of the graph, always chosing
          249  +the lowest-cost arc as the next step.  
          250  +The NN heuristic works surprisingly well in most cases.
          251  +And NN is fast, so that SQLite is able to quickly find good plans
          252  +for even large 64-way joins.  In contrast, other SQL database engines that
          253  +do more extensive searching tend to bog down when the
   127    254   number of tables in a join goes above 10 or 15.</p>
   128    255   
   129         -<p>However, the query plan computed by NN for TPC-H Q8 is not optimal.
          256  +<p>Unfortunately, the query plan computed by NN for TPC-H Q8 is not optimal.
   130    257   The plan computed using NN is R-N1-N2-S-C-O-L-P with a cost of 36.92.  
   131    258   The notation
   132    259   in the previous sentence means that the R table is run in the outer loop,
   133    260   N1 is in the next inner loop, N2 is in the third loop, and so forth down
   134         -to P which is in the inner-most loop.  But the shortest path through the
          261  +to P which is in the inner-most loop.  The shortest path through the
   135    262   graph (as found via exhaustive search) is  P-L-O-C-N1-R-S-N2
   136    263   with a cost of 27.38.  This might not seem like much, but remember that
   137    264   the costs are logarithmic, so the shortest path is nearly 14,000 times
   138    265   faster than that path found using the NN heuristic.</p>
   139    266   
   140    267   <p>One solution to this problem is to change SQLite to do an exhaustive
   141         -search for the best query plan.  But the SQLite developers are unwilling
   142         -to do this because an exhaustive search requires time proportional to
          268  +search for the best path.  But an exhaustive search requires time 
          269  +proportional to
   143    270   K! (where K is the number of tables in the join) and so when you get 
   144         -beyond a 10-way join, then time
          271  +beyond a 10-way join, the time
   145    272   to run [sqlite3_prepare()] becomes very large.</p>
   146    273   
   147         -<h3>N Nearest Neighbors</h3>
          274  +<h3>3.4 N Nearest Neighbors</h3>
   148    275   
   149         -<p>The proposed solution to this dilemma 
   150         -is to recode the SQLite query planner use a new
   151         -heuristic: "N Nearest Neighbors" (or "NNN").  With NNN, instead of
          276  +<p>The NGQP uses a new heuristic for seeking the best path through the
          277  +graph: "N Nearest Neighbors" (or "NNN").  With NNN, instead of
   152    278   choosing just one nearest neighbor for each step, the algorithm keeps
   153    279   track of the N bests paths at each step.</p>
   154    280   
   155         -<p>Suppose N==4.  Then for the TPC-H Q8 graph, the first step would find
          281  +<p>Suppose N==4.  Then for the TPC-H Q8 graph, the first step finds
   156    282   the four shortest paths to visit any single node in the graph:
   157    283   
   158    284   <blockquote>
   159    285       R (cost: 3.56) <br>
   160    286       N1 (cost: 5.52) <br>
   161    287       N2 (cost: 5.52) <br>
   162    288       P (cost: 7.71) <br>
   163    289   </blockquote>
   164    290   
   165         -<p>The second step would find the four shortest paths to visit two nodes 
   166         -and that begin with one of the four paths from the previous step.  In the
          291  +<p>The second step finds the four shortest paths to visit two nodes 
          292  +beginning with one of the four paths from the previous step.  In the
   167    293   case where two or more paths are equivalent (they have the same set of
   168    294   visited nodes, though possibly in a different order) then only the
   169         -first and lowest cost path is retained.  We have:</p>
          295  +first and lowest-cost path is retained.  We have:</p>
   170    296   
   171    297   <blockquote>
   172    298       R-N1 (cost: 7.03) <br>
   173    299       R-N2 (cost: 9.08) <br>
   174    300       N2-N1 (cost: 11.04) <br>
   175    301       R-P {cost: 11.27} <br>
   176    302   </blockquote>
   177    303   
   178         -<p>The third stop starts with the four shortest two-node paths and finds
   179         -the four shortest non-equivalent three-node paths:</p>
          304  +<p>The third step starts with the four shortest two-node paths and finds
          305  +the four shortest three-node paths:</p>
   180    306   
   181    307   <blockquote>
   182    308       R-N1-N2 (cost: 12.55) <br>
   183    309       R-N1-C (cost: 13.43) <br>
   184    310       R-N1-P (cost: 14.74) <br>
   185    311       R-N2-S (cost: 15.08) <br>
   186    312   </blockquote>
   187    313   
   188    314   <p>And so forth.  There are 8 nodes in the TPC-H Q8 query, 
   189    315   so this process repeats a total of 8
   190    316   times.  In the general case of a K-way join, the storage requirements
   191         -is O(N) and the computation time is O(K*N).  That is a lot less than an
   192         -exact solution which requires O(2**K) time.</p>
          317  +is O(N) and the computation time is O(K*N), which is significantly faster
          318  +than the O(2**K) exact solution.</p>
   193    319   
   194         -<p>But what value to choose for N?  We might make N==K.  This makes the
          320  +<p>But what value to choose for N?  One might try N==K.  This makes the
   195    321   algorithm O(N**2) which is actually still quite efficient, since the
   196    322   maximum value of K is 64.  But that is not enough for the TPC-H Q8
   197    323   problem.  With N==8 on TPC-H Q8 the NNN algorithm finds 
   198    324   the solution R-N1-C-O-L-S-N2-P with a cost of 29.78.  
   199    325   That is an improvement over NN, but it is still
   200         -not optimal.</p>
          326  +not optimal.  NNN finds the optimal solution for TPC-H Q8 
          327  +when N is 10 or greater.</p>
          328  +
          329  +<p>The initial implementation of NGQP choses N==1 for simple queries, N==5
          330  +for two-way joins and N==10 for all joins with three or more tables.  This
          331  +formula for selecting N might change in subsequent releases.</p>
          332  +
          333  +<tcl>hd_fragment hazards {hazards of upgrading to the NGQP}</tcl>
          334  +<h2>4.0 Hazards Of Upgrading To NGQP</h2>
          335  +
          336  +<p>For most applications, upgrading from the legacy query planner to the NGQP
          337  +is a no-brainer.  Just drop in the newer version of SQLite and recompile and
          338  +the application will run faster.  There are no API changes or changes
          339  +to compilation procedures.</p>
          340  +
          341  +<p>But as with any query planner change, upgrading to the NGQP does carry
          342  +a small risk of introducing performance regressions.  The problem here is
          343  +not that the NGQP is incorrect or buggy.  More likely,
          344  +the legacy query planner merely stumbled over a better query plan
          345  +by stupid luck and the NGQP is not quite so lucky.</p>
          346  +
          347  +<h3>4.1 Case Study: Upgrading Fossil to the NGQP</h3>
          348  +
          349  +<p>The <a href="http://www.fossil-scm.org/">Fossil DVCS</a> is the version
          350  +control system used to track all of the SQLite source code.
          351  +A Fossil repository is an SQLite database file.
          352  +(Readers are invited to ponder this recursion as an independent exercise.)
          353  +</p>
          354  +
          355  +<p>Fossil is both the version-control system for SQLite and also a test
          356  +platform for SQLite.  Whenever changes or enhancements are made to SQLite, 
          357  +Fossil is one of the first applications to test and evaluate those
          358  +changes.  So Fossil was an early adopter of the NGQP.  And NGQP caused a
          359  +performance issue in Fossil, as described in the sequel.</p>
          360  +
          361  +<p>One of the many reports that Fossil makes available is a timeline of
          362  +changes to a single branch showing all merges in and out of that branch.
          363  +See [http://www.sqlite.org/src/timeline?nd&n=200&r=trunk] for a typical
          364  +example of such a report.  Generating such a report normally takes just
          365  +a few milliseconds.  But after upgrading to the NGQP we noticed that
          366  +this one report was taking closer to 10 seconds for the trunk of the
          367  +repository.</p>
          368  +
          369  +<p>The core query used to generate the branch timeline is shown below.
          370  +(Readers are not expected to understand the details of this query.
          371  +Commentary will follow.)</p>
          372  +
          373  +<blockquote><pre>
          374  +SELECT
          375  +     blob.rid AS blobRid,
          376  +     uuid AS uuid,
          377  +     datetime(event.mtime,'localtime') AS timestamp,
          378  +     coalesce(ecomment, comment) AS comment,
          379  +     coalesce(euser, user) AS user,
          380  +     blob.rid IN leaf AS leaf,
          381  +     bgcolor AS bgColor,
          382  +     event.type AS eventType,
          383  +     (SELECT group_concat(substr(tagname,5), ', ')
          384  +        FROM tag, tagxref
          385  +       WHERE tagname GLOB 'sym-*'
          386  +         AND tag.tagid=tagxref.tagid
          387  +         AND tagxref.rid=blob.rid
          388  +         AND tagxref.tagtype>0) AS tags,
          389  +     tagid AS tagid,
          390  +     brief AS brief,
          391  +     event.mtime AS mtime
          392  +  FROM event CROSS JOIN blob
          393  + WHERE blob.rid=event.objid
          394  +   AND (EXISTS(SELECT 1 FROM tagxref
          395  +                WHERE tagid=11 AND tagtype>0 AND rid=blob.rid)
          396  +        OR EXISTS(SELECT 1 FROM plink JOIN tagxref ON rid=cid
          397  +                   WHERE tagid=11 AND tagtype>0 AND pid=blob.rid)
          398  +        OR EXISTS(SELECT 1 FROM plink JOIN tagxref ON rid=pid
          399  +                   WHERE tagid=11 AND tagtype>0 AND cid=blob.rid))
          400  + ORDER BY event.mtime DESC
          401  + LIMIT 200;
          402  +</pre></blockquote>
          403  +
          404  +<p>This query is only a two-way join, but it contains four subqueries,
          405  +one in the result set and three more in the WHERE clause.  This query is not
          406  +especially complicated, but even so it replaces hundreds or 
          407  +perhaps thousands of lines of procedural code.</p>
          408  +
          409  +<p>The gist of the query is this:  Scan down the EVENT table looking
          410  +for the most recent 200 check-ins that satisfy one of three conditions:
          411  +<ol>
          412  +<li> The check-in has a "trunk" tag.
          413  +<li> The check-in has a child that has a "trunk" tag.
          414  +<li> The check-in has a parent that has a "trunk" tag.
          415  +</ol>
          416  +These three conditions are implemented by the three OR-connected
          417  +EXISTS statements in the WHERE clause of the query.</p>
          418  +
          419  +<p>The slowdown that occurred with the NGQP was caused by the last two
          420  +of the three conditions.  We will examine the middle condition
          421  +more closely.</p>
          422  +
          423  +<p>The subquery of the second condition can be rewritten (with minor
          424  +and immaterial simplifications) as follows:</p>
          425  +
          426  +<blockquote><pre>
          427  +SELECT 1
          428  +  FROM plink JOIN tagxref ON tagxref.rid=plink.cid
          429  + WHERE tagxref.tagid=$trunk
          430  +   AND plink.pid=$ckid;
          431  +</pre></blockquote>
          432  +
          433  +<p>The PLINK table is used to show parent-child relationships between
          434  +check-ins.  The TAGXREF table is used to show which tags are assigned
          435  +to which check-ins.  For reference, the relevant portions of the schemas
          436  +for these two tables is shown here:</p>
          437  +
          438  +<blockquote><pre>
          439  +CREATE TABLE plink(
          440  +  pid INTEGER REFERENCES blob,
          441  +  cid INTEGER REFERENCES blob
          442  +);
          443  +CREATE UNIQUE INDEX plink_i1 ON plink(pid,cid);
          444  +
          445  +CREATE TABLE tagxref(
          446  +  tagid INTEGER REFERENCES tag,
          447  +  mtime TIMESTAMP,
          448  +  rid INTEGER REFERENCE blob,
          449  +  UNIQUE(rid, tagid)
          450  +);
          451  +CREATE INDEX tagxref_i1 ON tagxref(tagid, mtime);
          452  +</pre></blockquote>
          453  +
          454  +<p>There are only two reasonable ways to implement this query.
          455  +(There are many other possible algorithms, but none of the
          456  +others are contenders for being the "best" algorithm and are thus
          457  +ignored here.)<p.
          458  +
          459  +<ol>
          460  +<li value=1><p>
          461  +Find all children of checkin $ckid and test each one to see if
          462  +it has the $trunk tag.
          463  +<li value=2><p>
          464  +Find all checkins with the $trunk tag and test each one to see if
          465  +it is a child of $ckid.
          466  +</ol>
          467  +
          468  +<p>
          469  +Intuitively, we humans understand that algorithm (1) is best.
          470  +Each check-in is only likely to have a handful of children (having one child is
          471  +most common case) and each one of those children can be checked for the
          472  +$trunk tag in logarithmic time.  And, indeed, algorithm (1) is the
          473  +faster choice in practice.  But the NGQP is not equipped with intuition.  The
          474  +NGQP has to use hard math, and algorithm (2) works out to be slightly
          475  +better mathematically.  This is because, in the absence of other information,
          476  +the NGQP must assume that the indices PLINK_I1 and TAGXREF_I1 are of
          477  +equal quality and are equally selective.  Algorithm (2) uses one field
          478  +of the TAGXREF_I1 index and both fields of the PLINK_I1 index whereas
          479  +algorithm (1) only uses the first field of each index.  Since 
          480  +algorithm (2) uses more index material, the NGQP is correct
          481  +to judge it to be the better algorithm.  The scores are close and
          482  +algorithm (2) just barely squeaks ahead of algorithm (1).  But
          483  +algorithm (2) really is the correct choice here.
          484  +</p>
          485  +
          486  +<p>
          487  +Unfortunately, algorithm (2) is many times slower than algorithm (1) in
          488  +this application.
          489  +</p>
          490  +
          491  +<p>
          492  +The problem is that the indices are not of equal quality.
          493  +A check-in is likely to only have one child check-in.  There might be two
          494  +or three in some cases, but the usual number will be one.  So the first
          495  +field of PLINK_I1 will usually narrow down the search to just a single
          496  +row.  But there might be many more check-ins on the same branch, especially
          497  +if that branch is "trunk", so that the first field of TAGXREF_I1 will be
          498  +of little help in narrowing down the search.  As of this writing
          499  +(2013-06-24) on the SQLite repository, roughly 38 out of every 100 rows
          500  +in the TAGXREF table assign "trunk" tags to checkins.  Hence searching on just
          501  +the first field of the TAGXREF_I1 index is practically useless.
          502  +</p>
          503  +
          504  +<p>
          505  +The NGQP has no way of knowing that TAGXREF_I1 is almost useless in this
          506  +query, unless we have run [ANALYZE] on the database.  After [ANALYZE] is
          507  +run, statistics on the quality of the various indices are stored in the
          508  +SQLITE_STAT1 table.  Having access to this statistical information,
          509  +the NGQP easily choses algorithm (1) as the best algorithm, by a wide
          510  +margin.</p>
          511  +
          512  +<p>Why didn't the legacy query planner choose algorithm (2)?
          513  +Easy: because the nearest neighbor greedy algorithm used by the legacy
          514  +query planner never even considered algorithm (2).
          515  +Algorithm (1) was the only option that the legacy
          516  +query planner gave any thought to.  And hence
          517  +the legacy query planner just happened to make the faster choice by
          518  +stupid luck.</p>
   201    519   
   202         -<p>NNN finds the optimal solution for TPC-H Q8 when N is 10 or greater.</p>
          520  +<h3>4.2 Fixing The Problem</h3>
   203    521   
   204         -<p>The current thinking is to make N a parameter with a default
   205         -value of 15 or so.  This will likely find at least a very good plan in most
   206         -circumstances.  We think you will need to work very hard to
   207         -construct a query where NNN with N==15 does not find the optimal plan.
   208         -Remember that the all SQLite versions prior to 3.7.18 do
   209         -an excellent job with N==1.  The value of N==15 would be the compile-time
   210         -default, but can be changed using a PRAGMA.</p>
          522  +<p>Running [ANALYZE] on the repository database immediately fixed the
          523  +performance problem.  However, we want Fossil to be robust and to always
          524  +work quickly regardless of whether or not its repository has been analyzed.
          525  +For this reason, the query was modify to use the CROSS JOIN operator 
          526  +instead of simply JOIN.  SQLite will not reorder the tables of a CROSS JOIN.
          527  +This is a feature designed specifically to allow knowledgeable programmers
          528  +to enforce a particular loop nesting order.  Once the join
          529  +was changed to CROSS JOIN (the addition of a single keyword) the NGQP was
          530  +forced to chose the faster algorithm (1) regardless of whether or not
          531  +statistical information had been gathered using ANALYZE.</p>
   211    532   
   212         -<p>Another idea begin considered is to initially attempt to find a query
   213         -plan using N==1 and then fall back and make a second attempt with a larger
   214         -N if the first attempt fails to find a provably optimal plan.  A provably
   215         -optimal plan is one that uses the lowest-cost arc into each node.</p>
          533  +<p>The previous sentence called algorithm (1) "faster", but this
          534  +is not strictly true.  Algorithm (1) is faster in common repositories, but
          535  +it is possible (in theory) to construct a repository composed mostly of
          536  +new branches, one check-in per branch, with many branches originating from
          537  +the same parent.  In that case, TAGXREF_I1 would become more selective
          538  +than PLINK_I1 and algorithm (2) really would be the faster choice.
          539  +However such branch-heavy repositories are unlikely to appear in actual
          540  +practice.</p>