Documentation Source Text

Check-in [828ca81aae]
Login

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

Overview
Comment:Further improvement and expansion of the NGQP documentation, including adding a checklist for preventing and dealing with bad choices by the query planner.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 828ca81aaeb7d4c32381e17aefe08b8396223e0b
User & Date: drh 2013-06-25 16:31:40
Context
2013-06-26
14:35
Updates to the changes.html page. Fix typos on the NGQP documentation. check-in: e0c107dec3 user: drh tags: trunk
2013-06-25
16:31
Further improvement and expansion of the NGQP documentation, including adding a checklist for preventing and dealing with bad choices by the query planner. check-in: 828ca81aae user: drh tags: trunk
01:44
Second draft of the NGQP document. check-in: e09abae6c3 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

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         -<h2>1.0 Executive Summary</h2>
           19  +<h2>1.0 Introduction</h2>
    20     20   
    21         -<p>Given an SQL statement, the task of the "query planner" is to figure
    22         -out the best algorithm to accomplish that statement.
           21  +<p>
           22  +The task of the "query planner" is to figure
           23  +out the best algorithm or "query plan" to accomplish an SQL statement.
    23     24   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  +rewritten so that it runs faster and generates better plans.  The
    25     26   rewrite is called the "next generation query planner" or "NGQP".
    26     27   </p>
    27     28   
    28     29   <p>This article overviews the importance of query planning, describes some
    29     30   of the problems inherent to query planning, and outlines how the NGQP
    30     31   solves those problems.</p>
    31     32   
    32     33   <p>The NGQP is almost always better than the legacy query planner.
    33     34   However, there may exist legacy applications that unknowingly depend on 
    34     35   undefined and/or suboptimal behavior in the legacy query planner, and
    35     36   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>
           37  +regressions.  This risk is considered and a checklist is provided
           38  +for reducing the risk and fixing any issues that do arise.</p>
    38     39   
    39     40   <h2>2.0 Background</h2>
    40     41   
    41     42   <p>For simple queries against a single table with few indices, there is usually
    42     43   an obvious choice for the best algorithm.
    43         -But for larger and more complex queries, multi-way joins with many indices
           44  +But for larger and more complex queries, such as
           45  +multi-way joins with many indices
    44     46   and subqueries, there can be hundreds, thousands, or millions
    45         -of "reasonable" algorithms for computing the result.
           47  +of reasonable algorithms for computing the result.
    46     48   The job of the query planner is to chose a single "best" query plan from
    47     49   this multitude of possibilities.</p>
    48     50   
    49     51   <p>The existence of a query planner is what makes SQL database engines
    50         -so useful and powerful.
           52  +so amazingly useful and powerful.
    51     53   The query planner frees the programmer from the chore of selecting
    52     54   a particular query plan, and thereby allows the programmer to
    53     55   focus more mental energy on higher-level application issues and on 
    54     56   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.
           57  +of query plans is obvious, this is not of huge importance.
    56     58   But as applications and schemas and queries grow more complex, a
    57     59   clever query planner can greatly speed and simplify the work of application
    58     60   development. 
    59     61   There is amazing power in being about to tell
    60         -the database engine what content is desired, and then leave the database
           62  +the database engine what content is desired, and then let the database
    61     63   engine to work out the best way to retrieve that content.</p>
    62     64   
    63     65   <p>Writing a good query planner is an inexact science.
    64     66   The query planner must work with incomplete information.
    65     67   It cannot determine how long any particular plan will take
    66     68   without actually running that plan.  So when comparing two
    67     69   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 
           70  +some guesses and assumption and those guesses and assumptions will 
    69     71   sometimes be wrong. A good query plan is one that will
    70     72   find the correct solution often enough that application
    71     73   programmers only rarely need to get involved.</p>
    72     74   
    73     75   <h3>2.1 Query Planning In SQLite</h3>
    74     76   
    75         -<p>The query engine in SQLite computes joins using nested loops, 
           77  +<p>SQLite computes joins using nested loops, 
    76     78   one loop for each table
    77     79   in the join.  (Additional loops might be inserted to handle IN operators
    78     80   in the WHERE clause, but those extra loops are not considered here.)
    79     81   One or more indices might be used on each loop to speed the search,
    80     82   or a loop might be a "full table scan" using only the original table.
    81     83   Thus query planning decomposes into two subtasks:</p>
    82     84   <ol>
................................................................................
   104    106   then SQLite will not suddenly decide to start using a new and different
   105    107   query plan once your application is in the field, and thereby possibly
   106    108   causing a performance problem.  If your application works in the lab, it
   107    109   will continue working the same way after deployment.</p>
   108    110   
   109    111   <p>Enterprise-class client/server SQL database engines do not normally 
   110    112   make this guarantee.
   111         -In client/server SQL database engines, the server will keeps continuously
   112         -updated statistics on the sizes of tables and on the quality of indices 
   113         -and the query planner those statistics to aid in selecting the best plans.
          113  +In client/server SQL database engines, the server keeps track of
          114  +statistics on the sizes of tables and on the quality of indices 
          115  +and the query planner uses those statistics to help select the best plans.
   114    116   As content is added, deleted, or changed in the database, the statistics 
   115    117   will evolve and may cause the query planner to begin using a different 
   116    118   query plan for some particular query.  Usually the new plan will be better 
   117    119   for the evolving structure of the data.  But sometimes the new query plan will
   118    120   cause a performance reduction.  With a client/server database engine, there
   119    121   is typically a Database Administrator (DBA) on hand to deal with these 
   120    122   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 plans do not change unexpectedly after deployment.</p>
          123  +in an embedded database like SQLite, and hence SQLite is careful to
          124  +ensure that plans do not change unexpectedly after deployment.</p>
   123    125   
   124    126   <p>This stability guarantee applies equally to the legacy query planner in
   125    127   SQLite and to the NGQP.</p>
   126    128   
   127    129   <p>It is important to note that changing versions of SQLite might cause
   128    130   changes in query plans, as new enhancements are added to the query planner.
   129    131   The same version of SQLite it will
................................................................................
   164    166   <img src="images/qp/tpchq8.gif">
   165    167   </center>
   166    168   
   167    169   <p>
   168    170   In the diagram, each of the 8 tables in the FROM clause of the query is
   169    171   identified by a large circle with the label of the FROM-clause term:
   170    172   N2, S, L, P, O, C, N1 and R.
   171         -The arcs in the graph represent the cost of computing each term assuming
   172         -that the origin of the arc is in an outer loop.  For example, the
          173  +The arcs in the graph represent the estimated cost of computing each term 
          174  +assuming that the origin of the arc is in an outer loop.  For example, the
   173    175   cost of running the S loop as an inner loop to L is 2.30 whereas the
   174    176   cost of running the S loop as an outer loop to L is 9.17.</p>
   175    177   
   176    178   <p>The "cost" here is logarithmic.  With nested loops, the work
   177    179   is multiplied, not added.  But it customary to think of graphs
   178    180   with additive weights and so the graph shows the logarithm of the
   179    181   various costs.  The graph shows a cost advantage of S being inside of
................................................................................
   188    190   result.  One can think of the *-costs as a short-hand notation indicating
   189    191   multiple arcs with that cost, one each from each of the other nodes in the
   190    192   graph.  The graph is is therefore "complete", meaning that there are arcs
   191    193   (some explicit and some implied) in both directions between every pair of 
   192    194   nodes in the graph.</p>
   193    195   
   194    196   <p>The problem of finding the best query plan is equivalent to finding
   195         -a minimum-cost path through the graph shown above that visits each node
          197  +a minimum-cost path through the graph that visits each node
   196    198   exactly once.</p>
          199  +
          200  +<p>(Side note:  The costs estimates in the TPC-H Q8 graph where computed
          201  +by the query planner in SQLite 3.7.16 and converted using a base-10 logarithm.)
          202  +</p>
   197    203   
   198    204   <h3>3.2 Complications</h3>
   199    205   
   200    206   <p>The presentation of the query planner problem above is a simplification.
   201    207   The costs are estimates.  We cannot
   202    208   know what the true cost of running a loop is until we actually run the loop.
   203    209   SQLite makes guesses for the cost of running a loop based on
................................................................................
   257    263   <p>Unfortunately, the query plan computed by NN for TPC-H Q8 is not optimal.
   258    264   The plan computed using NN is R-N1-N2-S-C-O-L-P with a cost of 36.92.  
   259    265   The notation
   260    266   in the previous sentence means that the R table is run in the outer loop,
   261    267   N1 is in the next inner loop, N2 is in the third loop, and so forth down
   262    268   to P which is in the inner-most loop.  The shortest path through the
   263    269   graph (as found via exhaustive search) is  P-L-O-C-N1-R-S-N2
   264         -with a cost of 27.38.  This might not seem like much, but remember that
          270  +with a cost of 27.38.  The difference might not seem like much, but 
          271  +remember that
   265    272   the costs are logarithmic, so the shortest path is nearly 14,000 times
   266    273   faster than that path found using the NN heuristic.</p>
   267    274   
   268    275   <p>One solution to this problem is to change SQLite to do an exhaustive
   269    276   search for the best path.  But an exhaustive search requires time 
   270    277   proportional to
   271    278   K! (where K is the number of tables in the join) and so when you get 
   272    279   beyond a 10-way join, the time
   273    280   to run [sqlite3_prepare()] becomes very large.</p>
   274    281   
   275         -<h3>3.4 N Nearest Neighbors</h3>
          282  +<h3>3.4 The N Nearest Neighbors or "N3" Heuristic</h3>
   276    283   
   277    284   <p>The NGQP uses a new heuristic for seeking the best path through the
   278         -graph: "N Nearest Neighbors" (or "NNN").  With NNN, instead of
          285  +graph: "N Nearest Neighbors" (hereafter "N3").  With N3, instead of
   279    286   choosing just one nearest neighbor for each step, the algorithm keeps
   280         -track of the N bests paths at each step.</p>
          287  +track of the N bests paths at each step for some small integer N.</p>
   281    288   
   282         -<p>Suppose N==4.  Then for the TPC-H Q8 graph, the first step finds
          289  +<p>Suppose N=4.  Then for the TPC-H Q8 graph, the first step finds
   283    290   the four shortest paths to visit any single node in the graph:
   284    291   
   285    292   <blockquote>
   286    293       R (cost: 3.56) <br>
   287    294       N1 (cost: 5.52) <br>
   288    295       N2 (cost: 5.52) <br>
   289    296       P (cost: 7.71) <br>
................................................................................
   312    319       R-N2-S (cost: 15.08) <br>
   313    320   </blockquote>
   314    321   
   315    322   <p>And so forth.  There are 8 nodes in the TPC-H Q8 query, 
   316    323   so this process repeats a total of 8
   317    324   times.  In the general case of a K-way join, the storage requirements
   318    325   is O(N) and the computation time is O(K*N), which is significantly faster
   319         -than the O(2**K) exact solution.</p>
          326  +than the O(2<small><sup>K</sup></small>) exact solution.</p>
   320    327   
   321         -<p>But what value to choose for N?  One might try N==K.  This makes the
   322         -algorithm O(N**2) which is actually still quite efficient, since the
   323         -maximum value of K is 64.  But that is not enough for the TPC-H Q8
   324         -problem.  With N==8 on TPC-H Q8 the NNN algorithm finds 
          328  +<p>But what value to choose for N?  One might try N=K.  This makes the
          329  +algorithm O(K<small><sup>2</sup></small>) 
          330  +which is actually still quite efficient, since the
          331  +maximum value of K is 64 and rarely exceeds 10.  
          332  +But that is not enough for the TPC-H Q8
          333  +problem.  With N=8 on TPC-H Q8 the N3 algorithm finds 
   325    334   the solution R-N1-C-O-L-S-N2-P with a cost of 29.78.  
   326         -That is an improvement over NN, but it is still
   327         -not optimal.  NNN finds the optimal solution for TPC-H Q8 
          335  +That is a big improvement over NN, but it is still
          336  +not optimal.  N3 finds the optimal solution for TPC-H Q8 
   328    337   when N is 10 or greater.</p>
   329    338   
   330         -<p>The initial implementation of NGQP choses N==1 for simple queries, N==5
   331         -for two-way joins and N==10 for all joins with three or more tables.  This
          339  +<p>The initial implementation of NGQP choses N=1 for simple queries, N=5
          340  +for two-way joins and N=10 for all joins with three or more tables.  This
   332    341   formula for selecting N might change in subsequent releases.</p>
   333    342   
   334    343   <tcl>hd_fragment hazards {hazards of upgrading to the NGQP}</tcl>
   335    344   <h2>4.0 Hazards Of Upgrading To NGQP</h2>
   336    345   
   337    346   <p>For most applications, upgrading from the legacy query planner to the NGQP
   338         -is a no-brainer.  Just drop in the newer version of SQLite and recompile and
   339         -the application will run faster.  There are no API changes nor modifications
          347  +requires little thought or effort.
          348  +Simply replace the older SQLite version with the newer version of SQLite 
          349  +and recompile and the application will run faster.  
          350  +There are no API changes nor modifications
   340    351   to compilation procedures.</p>
   341    352   
   342    353   <p>But as with any query planner change, upgrading to the NGQP does carry
   343    354   a small risk of introducing performance regressions.  The problem here is
   344         -not that the NGQP is incorrect or buggy.  More likely,
   345         -the legacy query planner merely stumbled over a better query plan
   346         -by stupid luck and the NGQP is not quite so lucky.</p>
          355  +not that the NGQP is incorrect or buggy or inferior to the legacy query
          356  +planner.  Given accurate cost estimates, the NGQP will always pick a better
          357  +plan than older query planners.  The problem is that cost estimates might
          358  +sometimes be inaccurate and the legacy query planner just happened to stumbled 
          359  +over a good plan by stupid luck while the NGQP is not as lucky.</p>
   347    360   
   348    361   <h3>4.1 Case Study: Upgrading Fossil to the NGQP</h3>
   349    362   
   350    363   <p>The <a href="http://www.fossil-scm.org/">Fossil DVCS</a> is the version
   351    364   control system used to track all of the SQLite source code.
   352    365   A Fossil repository is an SQLite database file.
   353    366   (Readers are invited to ponder this recursion as an independent exercise.)
................................................................................
   412    425   <p><ol>
   413    426   <li> The check-in has a "trunk" tag.
   414    427   <li> The check-in has a child that has a "trunk" tag.
   415    428   <li> The check-in has a parent that has a "trunk" tag.
   416    429   </ol></p>
   417    430   
   418    431   <p>
   419         -These three conditions are implemented by the three OR-connected
          432  +The first condition causes all of the trunk check-ins to be displayed and
          433  +the second and third cause check-ins that merge into or are derived from
          434  +the trunk to also be included.
          435  +The three conditions are implemented by the three OR-connected
   420    436   EXISTS statements in the WHERE clause of the query.
   421         -The slowdown that occurred with the NGQP was caused by the last two
   422         -of the three conditions.  We will examine the middle condition
   423         -more closely.
          437  +The slowdown that occurred with the NGQP was caused by the second and
          438  +third conditions.  The problem is the same in each, so we will examine
          439  +just the second conditions.
   424    440   The subquery of the second condition can be rewritten (with minor
   425    441   and immaterial simplifications) as follows:</p>
   426    442   
   427    443   <blockquote><pre>
   428    444   SELECT 1
   429    445     FROM plink JOIN tagxref ON tagxref.rid=plink.cid
   430    446    WHERE tagxref.tagid=$trunk
   431    447      AND plink.pid=$ckid;
   432    448   </pre></blockquote>
   433    449   
   434         -<p>The PLINK table is used to show parent-child relationships between
   435         -check-ins.  The TAGXREF table is used to show which tags are assigned
   436         -to which check-ins.  For reference, the relevant portions of the schemas
          450  +<p>The PLINK table holds parent-child relationships between
          451  +check-ins.  The TAGXREF table maps tags into check-ins.
          452  +For reference, the relevant portions of the schemas
   437    453   for these two tables is shown here:</p>
   438    454   
   439    455   <blockquote><pre>
   440    456   CREATE TABLE plink(
   441    457     pid INTEGER REFERENCES blob,
   442    458     cid INTEGER REFERENCES blob
   443    459   );
................................................................................
   450    466     UNIQUE(rid, tagid)
   451    467   );
   452    468   CREATE INDEX tagxref_i1 ON tagxref(tagid, mtime);
   453    469   </pre></blockquote>
   454    470   
   455    471   <p>There are only two reasonable ways to implement this query.
   456    472   (There are many other possible algorithms, but none of the
   457         -others are contenders for being the "best" algorithm and are thus
   458         -ignored here.)</p>
          473  +others are contenders for being the "best" algorithm.)</p>
   459    474   
   460    475   <ol type="1">
   461    476   <li value=1><p>
   462         -Find all children of checkin $ckid and test each one to see if
          477  +Find all children of check-in $ckid and test each one to see if
   463    478   it has the $trunk tag.
   464    479   <li value=2><p>
   465         -Find all checkins with the $trunk tag and test each one to see if
          480  +Find all check-ins with the $trunk tag and test each one to see if
   466    481   it is a child of $ckid.
   467    482   </ol>
   468    483   
   469    484   <p>
   470    485   Intuitively, we humans understand that algorithm-1 is best.
   471    486   Each check-in is likely to have few children (one child is
   472         -the most common case) and each child can be checked for the
          487  +the most common case) and each child can be tested for the
   473    488   $trunk tag in logarithmic time.  Indeed, algorithm-1 is the
   474    489   faster choice in practice.  But the NGQP has no intuition.  The
   475    490   NGQP must use hard math, and algorithm-2 is slightly
   476    491   better mathematically.  This is because, in the absence of other information,
   477    492   the NGQP must assume that the indices PLINK_I1 and TAGXREF_I1 are of
   478    493   equal quality and are equally selective.  Algorithm-2 uses one field
   479    494   of the TAGXREF_I1 index and both fields of the PLINK_I1 index whereas
................................................................................
   487    502   <p>
   488    503   Unfortunately, algorithm-2 is slower than algorithm-1 in
   489    504   this application.
   490    505   </p>
   491    506   
   492    507   <p>
   493    508   The problem is that the indices are not of equal quality.
   494         -A check-in is likely to only have one child check-in.  There might be two
   495         -or three in some cases, but the usual number will be one.  So the first
          509  +A check-in is likely to only have one child.  So the first
   496    510   field of PLINK_I1 will usually narrow down the search to just a single
   497         -row.  But there might be many more check-ins on the same branch, especially
   498         -if that branch is "trunk", so that the first field of TAGXREF_I1 will be
   499         -of little help in narrowing down the search.  As of this writing
   500         -(2013-06-24) on the SQLite repository, roughly 38 out of every 100 rows
   501         -in the TAGXREF table assign "trunk" tags to checkins.  Hence searching on just
   502         -the first field of the TAGXREF_I1 index is practically useless.
          511  +row.  But there are thousands and thousands check-ins tagged with "trunk", 
          512  +so the first field of TAGXREF_I1 will be
          513  +of little help in narrowing down the search.
   503    514   </p>
   504    515   
   505    516   <p>
   506    517   The NGQP has no way of knowing that TAGXREF_I1 is almost useless in this
   507         -query, unless [ANALYZE] has been run on the database.  The [ANALYZE] 
   508         -gathers statistics on the quality of the various indices are stored the
          518  +query, unless [ANALYZE] has been run on the database.  The [ANALYZE] command
          519  +gathers statistics on the quality of the various indices and stores the
   509    520   result in SQLITE_STAT1 table.  Having access to this statistical information,
   510    521   the NGQP easily choses algorithm-1 as the best algorithm, by a wide
   511    522   margin.</p>
   512    523   
   513    524   <p>Why didn't the legacy query planner choose algorithm-2?
   514         -Easy: because the nearest neighbor greedy algorithm used by the legacy
   515         -query planner never even considered algorithm-2.  Graphs of the planning
          525  +Easy: because the NN algorithm
          526  +never even considered algorithm-2.  Graphs of the planning
   516    527   problem look like this:</p>
   517    528   
   518    529   <center>
   519    530   <img src="images/qp/fqp1.gif">
   520    531   </center>
   521    532   
   522    533   <p>
   523    534   In the "without ANALYZE" case on the left, the NN algorithm chooses 
   524         -loop P (PLINK) as the outer loop because 4.9 is less than 5.3, resulting
   525         -in the selection of algorithm-1. NN completely misses the fact that 
   526         -5.2+4.4 makes a slightly cheaper plan than 4.9+4.8. But the NNN algorithm 
   527         -does select the lower cost plan, resulting in algorithm-2.
          535  +loop P (PLINK) as the outer loop because 4.9 is less than 5.2, resulting
          536  +in path P-T which is algorithm-1. NN only looks a the single best choice
          537  +at each step so it completely misses the fact that 
          538  +5.2+4.4 makes a slightly cheaper plan than 4.9+4.8. But the N3 algorithm
          539  +keeps track of the 5 best paths for a 2-way join, so it ends up
          540  +selecting path T-P because of its slightly lower overall cost.
          541  +Path T-P is algorithm-2.
   528    542   </p>
   529    543   
   530    544   <p>
   531         -Note that after ANALYZE has been run, algorithm-1
   532         -will be selected by both NN and NNN.
          545  +Note that with ANALYZE the cost estimates are
          546  +better aligned with reality and algorithm-1 is 
          547  +selected by both NN and N3.
   533    548   </p>
          549  +
          550  +<p>(Side note:  The costs estimates in the two most recent graphs 
          551  +were computed by the NGQP using a base-2 logarithm and slightly different
          552  +cost assumptions compared to the legacy query planner.  
          553  +Hence, the cost estimates in
          554  +these latter two graphs are not directly comparible to the cost estimates
          555  +in the TPC-H Q8 graph.)</p>
   534    556   
   535    557   <h3>4.2 Fixing The Problem</h3>
   536    558   
   537    559   <p>Running [ANALYZE] on the repository database immediately fixed the
   538    560   performance problem.  However, we want Fossil to be robust and to always
   539    561   work quickly regardless of whether or not its repository has been analyzed.
   540    562   For this reason, the query was modify to use the CROSS JOIN operator 
   541         -instead of simply JOIN.  SQLite will not reorder the tables of a CROSS JOIN.
   542         -This is a feature designed specifically to allow knowledgeable programmers
          563  +instead of simply JOIN.
          564  +(<a href="http://www.fossil-scm.org/fossil/fdiff?v1=c498d980579e18f8&v2=2a35f6ffed42e024&sbs=1">The
          565  +difference</a>)
          566  +SQLite will not reorder the tables of a CROSS JOIN.
          567  +This is a long-standing feature of SQLite that is specifically designed
          568  +to allow knowledgeable programmers
   543    569   to enforce a particular loop nesting order.  Once the join
   544    570   was changed to CROSS JOIN (the addition of a single keyword) the NGQP was
   545    571   forced to chose the faster algorithm-1 regardless of whether or not
   546    572   statistical information had been gathered using ANALYZE.</p>
   547    573   
   548         -<p>The previous sentence called algorithm-1 "faster", but this
          574  +<p>We say that algorithm-1 "faster", but this
   549    575   is not strictly true.  Algorithm-1 is faster in common repositories, but
   550         -it is possible to construct a repository composed mostly of
   551         -new branches, one check-in per branch, and with many branches originating from
   552         -the same parent.  In that case, TAGXREF_I1 would become more selective
          576  +it is possible to construct a repository in which
          577  +every check-in is on a different uniquely-named branch and
          578  +all check-ins are children of the root check-in.
          579  +In that case, TAGXREF_I1 would become more selective
   553    580   than PLINK_I1 and algorithm-2 really would be the faster choice.
   554         -However such branch-heavy repositories are unlikely to appear in
   555         -practice.</p>
          581  +However such repositories are very unlikely to appear in
          582  +practice and so hard-coding the loop nested order using the
          583  +CROSS JOIN syntax is a reasonable solution
          584  +to the problem i nthis case.</p>
          585  +
          586  +<tcl>hd_fragment howtofix</tcl>
          587  +<h2>5.0 Checklist For Avoiding Or Fixing Query Planner Problems</h2>
          588  +
          589  +<ol>
          590  +<li><p><b>Don't panic!</b>
          591  +Cases where the query planner picks an inferior plan are actually quite
          592  +rare.  You are unlikely to run accross any problems in your application.
          593  +If you are not having performance issues, the you do not need to worry
          594  +about any of this.</p>
          595  +
          596  +<li><p><b>Create appropriate indices.</b>
          597  +Most SQL performance problems arise not because of query planner issues
          598  +but rather due to lack of appropriate indices.  Make sure indices are
          599  +available to assist all large queries.  Most performance issues can be
          600  +resolved by one or two CREATE INDEX commands and with no changes to
          601  +application code.</p>
          602  +
          603  +<li><p><b>Avoid creating low-quality indices.</b>.
          604  +A low-quality index (for the purpose of this checklist) is one where
          605  +there are more than 10 or 20 rows in the table that have the same value
          606  +for the left-most column of the index.  In particular, avoid using
          607  +boolean or "enum" columns as the left-most columns of your indices.</p>
          608  +
          609  +<p>The performance problem in Fossil
          610  +described in the previous section came about because there were over
          611  +ten thousands entries in the TAGXREF table with the same value for the 
          612  +left-most column (the TAGID column) of the TAGXREF_I1 index.</p>
          613  +
          614  +<li><p><b>If you must use a low-quality index, be sure to run ANALYZE.</b>
          615  +Low-quality indices will not confuse the query planner as long as the
          616  +query planner knows that the indices are of low quality.  And the way
          617  +the query planner knows this is by the content of the SQLITE_STAT1 table,
          618  +normally computed by the ANALYZE command.</p>
          619  +
          620  +<p>Of course, ANALYZE only works effectively if you have a significant 
          621  +amount of content in your database in the first place.  When creating a 
          622  +new database that you expect to accumulate a lot of data, you can run 
          623  +the command "ANALYZE sqlite_master" to create the SQLITE_STAT1 table,
          624  +then prepopulate the SQLITE_STAT1 table (using ordinary INSERT statements)
          625  +with content that describes a typical
          626  +database for your application - perhaps content that you extracted after
          627  +running ANALYZE on a well-populated template database in the lab.</p>
          628  +
          629  +<li><p><b>Instrument your code.</b>
          630  +Add logic that lets you know quickly and easily which queries are taking
          631  +too much time.  Then work on just those specific queries.</p>
          632  +
          633  +<li><p><b>Use the CROSS JOIN syntax to enforce a particular
          634  +loop nesting order on queries that might use low-quality indices in
          635  +unanalyzed database.</b>
          636  +SQLite treats the keyword CROSS JOIN specially, forcing the table to the left
          637  +to be an an outer loop relative to the table on the right.</p>
          638  +
          639  +<p>Avoid this step if possible, as it defeats one of the huge advantages
          640  +of the whole SQL language concept, specifically that the application 
          641  +programmer does not need to get involved with query planning.  If you
          642  +do use CROSS JOIN, wait until late in your development cycle to do so,
          643  +and comment the use of CROSS JOIN carefully so that you can take it out
          644  +later if possible.  Avoid using CROSS JOIN early in the development
          645  +cycle as doing so is a premature optimization, which is well known to
          646  +be <a href="http://c2.com/cgi/wiki?PrematureOptimization">the root of
          647  +all evil</a>.</p>
          648  +
          649  +<li><p><b>Use the [INDEXED BY] syntax to enforce the selection of
          650  +particular indices on problem queries.</b>
          651  +As with the previous bullet, avoid this step if possible, and 
          652  +especially avoid doing this early in development as it is clearly a
          653  +premature optimization.</p>
          654  +</ol>
          655  +
          656  +<h2>6.0 Summary</h2>
          657  +
          658  +<p>The query planner in SQLite normally does a terrific job of selecting
          659  +fast algorithms for running your SQL statements.  This is true of the 
          660  +legacy query planner and even more true of the new NGQP.  There may be
          661  +an occasional situation where, due to incomplete information, the query
          662  +planner selects a suboptimal plan.  This will happen less often with the
          663  +NGQP than with the legacy query planner, but it might still happen.  Only
          664  +in those rare cases do application developers need to get involved and
          665  +help the query planner to do the right thing.  In the common case, the
          666  +NGQP is just a new enhancement to SQLite that makes the application run
          667  +a little faster and which requires no new developer though or action.</p>