Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.
|Comment:||Clarification and typo fixes in the NGQP document.|
|Timelines:||family | ancestors | descendants | both | trunk|
|Files:||files | file ages | folders|
|User & Date:||drh 2013-08-23 16:37:14|
|23:48||Change the 3.8.0 release date to 2013-08-26. check-in: 105ed6eed2 user: drh tags: trunk|
|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 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.