Documentation Source Text

Check-in [a5a0ee107d]
Login

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

Overview
Comment:Clarification and typo fixes in the NGQP document.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:a5a0ee107dad54f83f0244e9e3ae674fb54e5292
User & Date: drh 2013-08-23 16:37:14
Context
2013-08-25
23:48
Change the 3.8.0 release date to 2013-08-26. check-in: 105ed6eed2 user: drh tags: trunk
2013-08-23
16:37
Clarification and typo fixes in the NGQP document. check-in: a5a0ee107d user: drh tags: trunk
16:16
Fix documentation typos. check-in: ce2a4ec1e7 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to pages/queryplanner-ng.in.

    62     62   But as applications and schemas and queries grow more complex, a
    63     63   clever query planner can greatly speed and simplify the work of application
    64     64   development. 
    65     65   There is amazing power in being about to tell
    66     66   the database engine what content is desired, and then let the database
    67     67   engine figure out the best way to retrieve that content.</p>
    68     68   
    69         -<p>Writing a good query planner is an inexact science.
           69  +<p>Writing a good query planner is more art than science.
    70     70   The query planner must work with incomplete information.
    71     71   It cannot determine how long any particular plan will take
    72     72   without actually running that plan.  So when comparing two
    73     73   or more plans to figure out which is "best", the query planner has to make
    74     74   some guesses and assumption and those guesses and assumptions will 
    75     75   sometimes be wrong. A good query plan is one that will
    76     76   find the correct solution often enough that application
    77         -programmers only rarely need to get involved.</p>
           77  +programmers rarely need to get involved.</p>
    78     78   
    79     79   <h3>2.1 Query Planning In SQLite</h3>
    80     80   
    81     81   <p>SQLite computes joins using nested loops, 
    82     82   one loop for each table
    83     83   in the join.  (Additional loops might be inserted for IN
    84     84   and OR operators in the WHERE clause.  SQLite considers those too,
................................................................................
   324    324       R-N1-C (cost: 13.43) <br>
   325    325       R-N1-P (cost: 14.74) <br>
   326    326       R-N2-S (cost: 15.08) <br>
   327    327   </blockquote>
   328    328   
   329    329   <p>And so forth.  There are 8 nodes in the TPC-H Q8 query, 
   330    330   so this process repeats a total of 8
   331         -times.  In the general case of a K-way join, the storage requirements
          331  +times.  In the general case of a K-way join, the storage requirement
   332    332   is O(N) and the computation time is O(K*N), which is significantly faster
   333    333   than the O(2<small><sup>K</sup></small>) exact solution.</p>
   334    334   
   335    335   <p>But what value to choose for N?  One might try N=K.  This makes the
   336    336   algorithm O(K<small><sup>2</sup></small>) 
   337    337   which is actually still quite efficient, since the
   338    338   maximum value of K is 64 and K rarely exceeds 10.