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: | e1646aea15d8a7c4c15d303893c39fbb |
| 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
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>