Debian Codegraph @

www/queryplanner-ng.html

raw
1 <!DOCTYPE html>
2 <html><head>
3 <meta name="viewport" content="width=device-width, initial-scale=1.0">
4 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
5 <link href="sqlite.css" rel="stylesheet">
6 <title>The Next-Generation Query Planner</title>
7 <!-- path= -->
8 </head>
9 <body>
10 <div class=nosearch>
11 <a href="index.html">
12 <img class="logo" src="images/sqlite370_banner.svg" alt="SQLite" border="0">
13 </a>
14 <div><!-- IE hack to prevent disappearing logo --></div>
15 <div class="tagline desktoponly">
16 Small. Fast. Reliable.<br>Choose any three.
17 </div>
18 <div class="menu mainmenu">
19 <ul>
20 <li><a href="index.html">Home</a>
21 <li class='mobileonly'><a href="javascript:void(0)" onclick='toggle_div("submenu")'>Menu</a>
22 <li class='wideonly'><a href='about.html'>About</a>
23 <li class='desktoponly'><a href="docs.html">Documentation</a>
24 <li class='desktoponly'><a href="download.html">Download</a>
25 <li class='wideonly'><a href='copyright.html'>License</a>
26 <li class='desktoponly'><a href="support.html">Support</a>
27 <li class='desktoponly'><a href="prosupport.html">Purchase</a>
28 <li class='search' id='search_menubutton'>
29 <a href="javascript:void(0)" onclick='toggle_search()'>Search</a>
30 </ul>
31 </div>
32 <div class="menu submenu" id="submenu">
33 <ul>
34 <li><a href='about.html'>About</a>
35 <li><a href='docs.html'>Documentation</a>
36 <li><a href='download.html'>Download</a>
37 <li><a href='support.html'>Support</a>
38 <li><a href='prosupport.html'>Purchase</a>
39 </ul>
40 </div>
41 <div class="searchmenu" id="searchmenu">
42 <form method="GET" action="search">
43 <select name="s" id="searchtype">
44 <option value="d">Search Documentation</option>
45 <option value="c">Search Changelog</option>
46 </select>
47 <input type="text" name="q" id="searchbox" value="">
48 <input type="submit" value="Go">
49 </form>
50 </div>
51 </div>
52 <script>
53 function toggle_div(nm) {
54 var w = document.getElementById(nm);
55 if( w.style.display=="block" ){
56 w.style.display = "none";
57 }else{
58 w.style.display = "block";
59 }
60 }
61 function toggle_search() {
62 var w = document.getElementById("searchmenu");
63 if( w.style.display=="block" ){
64 w.style.display = "none";
65 } else {
66 w.style.display = "block";
67 setTimeout(function(){
68 document.getElementById("searchbox").focus()
69 }, 30);
70 }
71 }
72 function div_off(nm){document.getElementById(nm).style.display="none";}
73 window.onbeforeunload = function(e){div_off("submenu");}
74 /* Disable the Search feature if we are not operating from CGI, since */
75 /* Search is accomplished using CGI and will not work without it. */
76 if( !location.origin || !location.origin.match || !location.origin.match(/http/) ){
77 document.getElementById("search_menubutton").style.display = "none";
78 }
79 /* Used by the Hide/Show button beside syntax diagrams, to toggle the */
80 function hideorshow(btn,obj){
81 var x = document.getElementById(obj);
82 var b = document.getElementById(btn);
83 if( x.style.display!='none' ){
84 x.style.display = 'none';
85 b.innerHTML='show';
86 }else{
87 x.style.display = '';
88 b.innerHTML='hide';
89 }
90 return false;
91 }
92 var antiRobot = 0;
93 function antiRobotGo(){
94 if( antiRobot!=3 ) return;
95 antiRobot = 7;
96 var j = document.getElementById("mtimelink");
97 if(j && j.hasAttribute("data-href")) j.href=j.getAttribute("data-href");
98 }
99 function antiRobotDefense(){
100 document.body.onmousedown=function(){
101 antiRobot |= 2;
102 antiRobotGo();
103 document.body.onmousedown=null;
104 }
105 document.body.onmousemove=function(){
106 antiRobot |= 2;
107 antiRobotGo();
108 document.body.onmousemove=null;
109 }
110 setTimeout(function(){
111 antiRobot |= 1;
112 antiRobotGo();
113 }, 100)
114 antiRobotGo();
115 }
116 antiRobotDefense();
117 </script>
118 <div class=fancy>
119 <div class=nosearch>
120 <div class="fancy_title">
121 The Next-Generation Query Planner
122 </div>
123 <details class="fancy_toc">
124 <summary>Table Of Contents</summary>
125 <div id="toc_sub"><div class="fancy-toc1"><a href="#_introduction">1. Introduction</a></div>
126 <div class="fancy-toc1"><a href="#_background">2. Background</a></div>
127 <div class="fancy-toc2"><a href="#_query_planning_in_sqlite">2.1. Query Planning In SQLite</a></div>
128 <div class="fancy-toc2"><a href="#_the_sqlite_query_planner_stability_guarantee">2.2. The SQLite Query Planner Stability Guarantee</a></div>
129 <div class="fancy-toc1"><a href="#_a_difficult_case">3. A Difficult Case</a></div>
130 <div class="fancy-toc2"><a href="#_query_details">3.1. Query Details</a></div>
131 <div class="fancy-toc2"><a href="#_complications">3.2. Complications</a></div>
132 <div class="fancy-toc2"><a href="#_finding_the_best_query_plan">3.3. Finding The Best Query Plan</a></div>
133 <div class="fancy-toc2"><a href="#_the_n_nearest_neighbors_or_n3_algorithm">3.4. The N Nearest Neighbors or "N3" Algorithm</a></div>
134 <div class="fancy-toc1"><a href="#the_star_query_heuristic">4. The Star-Query Heuristic</a></div>
135 <div class="fancy-toc2"><a href="#background_what_is_a_star_query">4.1. Background: What Is A Star-Query</a></div>
136 <div class="fancy-toc2"><a href="#query_planning_problems_with_high_dimensionality_star_queries">4.2. Query Planning Problems With High-Dimensionality Star-Queries</a></div>
137 <div class="fancy-toc2"><a href="#a_large_test_case">4.3. A Large Test Case</a></div>
138 <div class="fancy-toc2"><a href="#tweaks_to_n3_to_support_star_queries">4.4. Tweaks To N3 To Support Star Queries</a></div>
139 <div class="fancy-toc1"><a href="#_hazards_of_upgrading_to_ngqp">5. Hazards Of Upgrading To NGQP</a></div>
140 <div class="fancy-toc2"><a href="#_case_study_upgrading_fossil_to_the_ngqp">5.1. Case Study: Upgrading Fossil to the NGQP</a></div>
141 <div class="fancy-toc2"><a href="#_fixing_the_problem">5.2. Fixing The Problem</a></div>
142 <div class="fancy-toc2"><a href="#update_2017_a_better_fix">5.3. Update 2017: A Better Fix</a></div>
143 <div class="fancy-toc1"><a href="#_checklist_for_avoiding_or_fixing_query_planner_problems">6. Checklist For Avoiding Or Fixing Query Planner Problems</a></div>
144 <div class="fancy-toc1"><a href="#_summary">7. Summary</a></div>
145 </div>
146 </details>
147 </div>
148
149
150
151
152
153 <h1 id="_introduction"><span>1. </span> Introduction</h1>
154
155 <p>
156 The task of the "query planner" is to figure
157 out the best algorithm or "query plan" to accomplish an SQL statement.
158 Beginning with SQLite <a href="releaselog/3_8_0.html">version 3.8.0</a> (2013-08-26),
159 the query planner component has been
160 rewritten so that it runs faster and generates better plans. The
161 rewrite is called the "next generation query planner" or "NGQP".
162 </p>
163
164 <p>This article overviews the importance of query planning, describes some
165 of the problems inherent to query planning, and outlines how the NGQP
166 solves those problems.</p>
167
168 <p>The NGQP is almost always better than the legacy query planner.
169 However, there may exist legacy applications that unknowingly depend on
170 undefined and/or suboptimal behavior in the legacy query planner, and
171 upgrading to the NGQP on those legacy applications could cause performance
172 regressions. This risk is considered and a checklist is provided
173 for reducing the risk and for fixing any issues that do arise.</p>
174
175 <p>This document focuses on the NGQP. For a more general overview of the
176 SQLite query planner that encompasses the entire history of SQLite, see the
177 "<a href="optoverview.html">The SQLite Query Optimizer Overview</a>" and
178 "<a href="queryplanner.html">How Indexes Work</a>" documents.</p>
179
180 <h1 id="_background"><span>2. </span> Background</h1>
181
182 <p>For simple queries against a single table with few indexes, there is usually
183 an obvious choice for the best algorithm.
184 But for larger and more complex queries, such as
185 multi-way joins with many indexes
186 and subqueries, there can be hundreds, thousands, or millions
187 of reasonable algorithms for computing the result.
188 The job of the query planner is to choose the single "best" query plan from
189 this multitude of possibilities.</p>
190
191 <p>Query planners are what make SQL database engines so amazingly useful and powerful.
192 (This is true of all SQL database engines, not just SQLite.)
193 The query planner frees the programmer from the chore of selecting
194 a particular query plan, and thereby allows the programmer to
195 focus more mental energy on higher-level application issues and on
196 providing more value to the end user. For simple queries where the choice
197 of query plan is obvious, this is convenient but not hugely important.
198 But as applications and schemas and queries grow more complex, a
199 clever query planner can greatly speed and simplify the work of application
200 development.
201 There is amazing power in being able to tell
202 the database engine what content is desired, and then let the database
203 engine figure out the best way to retrieve that content.</p>
204
205 <p>Writing a good query planner is more art than science.
206 The query planner must work with incomplete information.
207 It cannot determine how long any particular plan will take
208 without actually running that plan. So when comparing two
209 or more plans to figure out which is "best", the query planner has to make
210 some guesses and assumptions and those guesses and assumptions will
211 sometimes be wrong. A good query planner is one that will
212 find the correct solution often enough that application
213 programmers rarely need to get involved.</p>
214
215 <h2 id="_query_planning_in_sqlite"><span>2.1. </span> Query Planning In SQLite</h2>
216
217 <p>SQLite computes joins using nested loops,
218 one loop for each table
219 in the join. (Additional loops might be inserted for IN
220 and OR operators in the WHERE clause. SQLite considers those too,
221 but for simplicity we will ignore them in this essay.)
222 One or more indexes might be used on each loop to speed the search,
223 or a loop might be a "full table scan" that reads every row in the
224 table. Thus query planning decomposes into two subtasks:</p>
225 <ol>
226 <li> Picking the nested order of the various loops
227 </li><li> Choosing good indexes for each loop
228 </li></ol>
229 <p>Picking the nesting order is generally the more challenging problem.
230 Once the nesting order of the join is established, the choice of indexes
231 for each loop is normally obvious.</p>
232
233 <a name="qpstab"></a>
234
235 <h2 id="_the_sqlite_query_planner_stability_guarantee"><span>2.2. </span> The SQLite Query Planner Stability Guarantee</h2>
236
237 <p>When the Query Planner Stability Guarantee (QPSG) is enabled
238 SQLite will always pick the same query plan for any
239 given SQL statement as long as:
240
241 </p><ol type="a">
242 <li>the database schema does not change in significant ways such as
243 adding or dropping indexes,</li>
244 <li>the ANALYZE command is not rerun, </li>
245 <li>the same version of SQLite is used.</li>
246 </ol>
247
248 <p>The QPSG is disabled by default. It can be enabled at compile-time
249 using the <a href="compile.html#enable_qpsg">SQLITE_ENABLE_QPSG</a> compile-time option, or at run-time by
250 invoking <a href="c3ref/db_config.html">sqlite3_db_config</a>(db,<a href="c3ref/c_dbconfig_defensive.html#sqlitedbconfigenableqpsg">SQLITE_DBCONFIG_ENABLE_QPSG</a>,1,0).
251
252 </p><p>The QPSG means that if all of your queries run efficiently
253 during testing, and if your application does not change the schema,
254 then SQLite will not suddenly decide to start using a different
255 query plan, possibly causing a performance problem after your application
256 is released to users. If your application works in the lab, it
257 will continue working the same way after deployment.</p>
258
259 <p>Client/server SQL database engines do not normally
260 make this guarantee.
261 In client/server SQL database engines, the server keeps track of
262 statistics on the sizes of tables and on the quality of indexes
263 and the query planner uses those statistics to help select the best plans.
264 As content is added, deleted, or changed in the database, the statistics
265 will evolve and may cause the query planner to begin using a different
266 query plan for some particular query. Usually the new plan will be better
267 for the evolving structure of the data. But sometimes the new query plan will
268 cause a performance reduction. With a client/server database engine, there
269 is typically a Database Administrator (DBA) on hand to deal with these
270 rare problems as they come up. But DBAs are not available to fix problems
271 in an embedded database like SQLite, and hence SQLite is careful to
272 ensure that plans do not change unexpectedly after deployment.</p>
273
274 <p>It is important to note that changing versions of SQLite might cause
275 changes in query plans.
276 The same version of SQLite will
277 always pick the same query plan, but if you relink your application to use
278 a different version of SQLite, then query plans might change. In rare
279 cases, an SQLite version change might lead to a performance regression.
280 This is one reason
281 you should consider statically linking your applications against SQLite
282 rather than use a system-wide SQLite shared library which might
283 change without your knowledge or control.</p>
284
285 <p>See also:
286 </p><ul>
287 <li> <a href="lang_analyze.html#req">Recommended usage patterns for ANALYZE</a>
288 </li><li> <a href="pragma.html#pragma_optimize">PRAGMA optimize</a>
289 </li></ul>
290
291 <h1 id="_a_difficult_case"><span>3. </span> A Difficult Case</h1>
292
293 <p>
294 "TPC-H Q8" is a test query from the
295 <a href="http://www.tpc.org/tpch/">Transaction Processing Performance
296 Council</a>. The query planners in SQLite versions 3.7.17 and earlier
297 do not choose good plans for TPC-H Q8. And it has been determined that
298 no amount
299 of tweaking of the legacy query planner will fix that. In order to find
300 a good solution to the TPC-H Q8 query, and to continue improving the
301 quality of SQLite's query planner, it became necessary to redesign the
302 query planner. This section tries to explain why this redesign was
303 necessary and how the NGQP is different and addresses the TPC-H Q8 problem.
304 </p>
305
306 <h2 id="_query_details"><span>3.1. </span> Query Details</h2>
307
308 <p>
309 TPC-H Q8 is an eight-way join.
310 As observed above, the main task of the query planner is
311 to figure out the best nesting order of the eight loops in order to minimize
312 the work needed to complete the join.
313 A simplified model of this problem for the case of TPC-H Q8 is shown
314 by the following diagram:
315 </p>
316
317 <center>
318 <div style="max-width:677px;"><svg xmlns='http://www.w3.org/2000/svg' style='font-size:initial;' class="pikchr" viewBox="0 0 677.503 310.031" data-pikchr-date="20250319161943">
319 <circle cx="132.37" cy="104.064" r="28.3066" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
320 <text x="132.37" y="104.064" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" font-size="156.25%" dominant-baseline="central">S</text>
321 <circle cx="234.274" cy="104.064" r="28.3066" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
322 <text x="234.274" y="104.064" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" font-size="156.25%" dominant-baseline="central">L</text>
323 <circle cx="336.178" cy="104.064" r="28.3066" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
324 <text x="336.178" y="104.064" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" font-size="156.25%" dominant-baseline="central">O</text>
325 <circle cx="438.082" cy="104.064" r="28.3066" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
326 <text x="438.082" y="104.064" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" font-size="156.25%" dominant-baseline="central">C</text>
327 <circle cx="539.985" cy="104.064" r="28.3066" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
328 <text x="539.985" y="104.064" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" font-size="156.25%" dominant-baseline="central">N1</text>
329 <circle cx="641.889" cy="104.064" r="28.3066" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
330 <text x="641.889" y="104.064" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" font-size="156.25%" dominant-baseline="central">R</text>
331 <circle cx="234.274" cy="205.968" r="28.3066" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
332 <text x="234.274" y="205.968" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" font-size="156.25%" dominant-baseline="central">P</text>
333 <circle cx="30.4666" cy="104.064" r="28.3066" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
334 <text x="30.4666" y="104.064" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" font-size="156.25%" dominant-baseline="central">N2</text>
335 <polygon points="104.064,101.229 91.7604,101.223 94.7978,93.1349" style="fill:rgb(0,0,0)"/>
336 <path d="M58.7732,101.229 L 70.0958,96.9771 Q 81.4185,92.7252 90.045,95.9647 L 98.6714,99.2041" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
337 <text x="81.4185" y="84.6612" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">6.00</text>
338 <polygon points="58.7732,106.898 71.0766,106.904 68.0391,114.993" style="fill:rgb(0,0,0)"/>
339 <path d="M104.064,106.898 L 92.7411,111.15 Q 81.4185,115.402 72.792,112.163 L 64.1655,108.923" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
340 <text x="81.4185" y="123.466" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">2.08</text>
341 <polygon points="205.968,101.229 193.664,101.223 196.702,93.1349" style="fill:rgb(0,0,0)"/>
342 <path d="M160.677,101.229 L 172,96.9771 Q 183.322,92.7252 191.949,95.9647 L 200.575,99.2041" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
343 <text x="183.322" y="84.6612" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">9.17</text>
344 <polygon points="160.677,106.898 172.98,106.904 169.943,114.993" style="fill:rgb(0,0,0)"/>
345 <path d="M205.968,106.898 L 194.645,111.15 Q 183.322,115.402 174.696,112.163 L 166.069,108.923" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
346 <text x="183.322" y="123.466" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">2.30</text>
347 <polygon points="307.871,101.229 295.568,101.223 298.605,93.1349" style="fill:rgb(0,0,0)"/>
348 <path d="M262.581,101.229 L 273.903,96.9771 Q 285.226,92.7252 293.852,95.9647 L 302.479,99.2041" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
349 <text x="285.226" y="84.6612" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">2.77</text>
350 <polygon points="262.581,106.898 274.884,106.904 271.847,114.993" style="fill:rgb(0,0,0)"/>
351 <path d="M307.871,106.898 L 296.549,111.15 Q 285.226,115.402 276.6,112.163 L 267.973,108.923" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
352 <text x="285.226" y="123.466" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">4.03</text>
353 <polygon points="409.775,101.229 397.472,101.223 400.509,93.1349" style="fill:rgb(0,0,0)"/>
354 <path d="M364.484,101.229 L 375.807,96.9771 Q 387.13,92.7252 395.756,95.9647 L 404.383,99.2041" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
355 <text x="387.13" y="84.6612" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">2.64</text>
356 <polygon points="364.484,106.898 376.788,106.904 373.75,114.993" style="fill:rgb(0,0,0)"/>
357 <path d="M409.775,106.898 L 398.452,111.15 Q 387.13,115.402 378.503,112.163 L 369.877,108.923" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
358 <text x="387.13" y="123.466" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">5.30</text>
359 <polygon points="511.679,101.229 499.375,101.223 502.413,93.1349" style="fill:rgb(0,0,0)"/>
360 <path d="M466.388,101.229 L 477.711,96.9771 Q 489.034,92.7252 497.66,95.9647 L 506.286,99.2041" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
361 <text x="489.034" y="84.6612" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">2.08</text>
362 <polygon points="466.388,106.898 478.692,106.904 475.654,114.993" style="fill:rgb(0,0,0)"/>
363 <path d="M511.679,106.898 L 500.356,111.15 Q 489.034,115.402 480.407,112.163 L 471.781,108.923" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
364 <text x="489.034" y="123.466" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">6.40</text>
365 <polygon points="613.583,101.229 601.279,101.223 604.317,93.1349" style="fill:rgb(0,0,0)"/>
366 <path d="M568.292,101.229 L 579.615,96.9771 Q 590.937,92.7252 599.564,95.9647 L 608.19,99.2041" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
367 <text x="590.937" y="84.6612" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">1.79</text>
368 <polygon points="568.292,106.898 580.595,106.904 577.558,114.993" style="fill:rgb(0,0,0)"/>
369 <path d="M613.583,106.898 L 602.26,111.15 Q 590.937,115.402 582.311,112.163 L 573.684,108.923" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
370 <text x="590.937" y="123.466" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">3.47</text>
371 <polygon points="237.109,177.661 237.114,165.358 245.203,168.395" style="fill:rgb(0,0,0)"/>
372 <path d="M237.109,132.37 L 241.361,143.693 Q 245.613,155.016 242.373,163.642 L 239.134,172.269" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
373 <text x="245.613" y="155.016" text-anchor="start" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">2.64</text>
374 <polygon points="231.439,132.37 231.434,144.674 223.345,141.636" style="fill:rgb(0,0,0)"/>
375 <path d="M231.439,177.661 L 227.188,166.338 Q 222.936,155.016 226.175,146.389 L 229.415,137.763" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
376 <text x="222.936" y="155.016" text-anchor="end" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">6.01</text>
377 <circle cx="30.4666" cy="16.3133" r="14.1533" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
378 <text x="30.4666" y="16.3133" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" dominant-baseline="central">*</text>
379 <polygon points="30.4666,75.7572 26.1466,64.2372 34.7866,64.2372" style="fill:rgb(0,0,0)"/>
380 <path d="M30.4666,30.4666L30.4666,69.9972" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
381 <text x="30.4666" y="53.1119" text-anchor="start" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central"> 5.52</text>
382 <circle cx="132.37" cy="16.3133" r="14.1533" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
383 <text x="132.37" y="16.3133" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" dominant-baseline="central">*</text>
384 <polygon points="132.37,75.7572 128.05,64.2372 136.69,64.2372" style="fill:rgb(0,0,0)"/>
385 <path d="M132.37,30.4666L132.37,69.9972" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
386 <text x="132.37" y="53.1119" text-anchor="start" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central"> 9.47</text>
387 <circle cx="234.274" cy="16.3133" r="14.1533" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
388 <text x="234.274" y="16.3133" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" dominant-baseline="central">*</text>
389 <polygon points="234.274,75.7572 229.954,64.2372 238.594,64.2372" style="fill:rgb(0,0,0)"/>
390 <path d="M234.274,30.4666L234.274,69.9972" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
391 <text x="234.274" y="53.1119" text-anchor="start" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central"> 16.40</text>
392 <circle cx="336.178" cy="16.3133" r="14.1533" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
393 <text x="336.178" y="16.3133" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" dominant-baseline="central">*</text>
394 <polygon points="336.178,75.7572 331.858,64.2372 340.498,64.2372" style="fill:rgb(0,0,0)"/>
395 <path d="M336.178,30.4666L336.178,69.9972" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
396 <text x="336.178" y="53.1119" text-anchor="start" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central"> 13.87</text>
397 <circle cx="438.082" cy="16.3133" r="14.1533" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
398 <text x="438.082" y="16.3133" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" dominant-baseline="central">*</text>
399 <polygon points="438.082,75.7572 433.762,64.2372 442.402,64.2372" style="fill:rgb(0,0,0)"/>
400 <path d="M438.082,30.4666L438.082,69.9972" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
401 <text x="438.082" y="53.1119" text-anchor="start" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central"> 12.56</text>
402 <circle cx="539.985" cy="16.3133" r="14.1533" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
403 <text x="539.985" y="16.3133" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" dominant-baseline="central">*</text>
404 <polygon points="539.985,75.7572 535.665,64.2372 544.305,64.2372" style="fill:rgb(0,0,0)"/>
405 <path d="M539.985,30.4666L539.985,69.9972" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
406 <text x="539.985" y="53.1119" text-anchor="start" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central"> 5.52</text>
407 <circle cx="641.889" cy="16.3133" r="14.1533" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
408 <text x="641.889" y="16.3133" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" dominant-baseline="central">*</text>
409 <polygon points="641.889,75.7572 637.569,64.2372 646.209,64.2372" style="fill:rgb(0,0,0)"/>
410 <path d="M641.889,30.4666L641.889,69.9972" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
411 <text x="641.889" y="53.1119" text-anchor="start" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central"> 3.56</text>
412 <circle cx="234.274" cy="293.718" r="14.1533" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
413 <text x="234.274" y="293.718" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" dominant-baseline="central">*</text>
414 <polygon points="234.274,234.274 238.594,245.794 229.954,245.794" style="fill:rgb(0,0,0)"/>
415 <path d="M234.274,279.565L234.274,240.034" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
416 <text x="234.274" y="256.919" text-anchor="start" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central"> 7.71</text>
417 </svg>
418 </div>
419 </center>
420
421 <p>
422 In the diagram, each of the 8 tables in the FROM clause of the query is
423 identified by a large circle with the label of the FROM-clause term:
424 N2, S, L, P, O, C, N1 and R.
425 The arcs in the graph represent the estimated cost of computing each term
426 assuming that the origin of the arc is in an outer loop. For example, the
427 cost of running the S loop as an inner loop to L is 2.30 whereas the
428 cost of running the S loop as an outer loop to L is 9.17.</p>
429
430 <p>The "cost" here is logarithmic. With nested loops, the work
431 is multiplied, not added. But it is customary to think of graphs
432 with additive weights and so the graph shows the logarithm of the
433 various costs. The graph shows a cost advantage of S being inside of
434 L of about 6.87, but this translates into the query running about
435 963 times faster when S loop is inside of the L loop rather than
436 being outside of it.</p>
437
438 <p>The arrows from the small circles labeled with "*" indicate the cost
439 of running each loop with no dependencies. The outermost loop must use this
440 *-cost. Inner loops have the option of using the *-cost or a cost assuming
441 one of the other terms is in an outer loop, whichever gives the best
442 result. One can think of the *-costs as a short-hand notation indicating
443 multiple arcs, one from each of the other nodes in the
444 graph. The graph is therefore "complete", meaning that there are arcs
445 (some explicit and some implied) in both directions between every pair of
446 nodes in the graph.</p>
447
448 <p>The problem of finding the best query plan is equivalent to finding
449 a minimum-cost path through the graph that visits each node
450 exactly once.</p>
451
452 <p>(Side note: The cost estimates in the TPC-H Q8 graph above were computed
453 by the query planner in SQLite 3.7.16 and converted using a natural logarithm.)
454 </p>
455
456 <h2 id="_complications"><span>3.2. </span> Complications</h2>
457
458 <p>The presentation of the query planner problem above is a simplification.
459 The costs are estimates. We cannot
460 know what the true cost of running a loop is until we actually run the loop.
461 SQLite makes guesses for the cost of running a loop based on
462 the availability of indexes and constraints found in the WHERE
463 clause. These guesses are usually pretty good, but they can sometimes be
464 off. Using the <a href="lang_analyze.html">ANALYZE</a> command to collect additional statistical
465 information about the database can sometimes enable SQLite to make better
466 guesses about the cost.</p>
467
468 <p>The costs are comprised of multiple numbers, not a single number as
469 shown in the graph.
470 SQLite computes several different estimated costs for each loop that apply at
471 different times. For example, there is a "setup" cost that is incurred
472 just once when the query starts. The setup cost is the cost of computing
473 a <a href="optoverview.html#autoindex">query-time index</a> for a table that does not already
474 have an index. Then there
475 is the cost of running each step of the loop. Finally, there is an estimate
476 of the number of rows generated by the loop, which is information needed in
477 estimating the costs of inner loops. Sorting costs may come into play
478 if the query has an ORDER BY clause.</p>
479
480 <p>In a general query, dependencies need not be on a single loop, and hence
481 the matrix of dependencies might not be representable as a graph.
482 For example, one of the WHERE clause constraints might be
483 S.a=L.b+P.c, implying that the S loop must be an inner loop of both
484 L and P. Such dependencies cannot be drawn as a graph
485 since there is no way for an arc to originate at two or more nodes at
486 once.</p>
487
488 <p>If the query contains an ORDER BY clause or a GROUP BY clause or if
489 the query uses the DISTINCT keyword then it is advantageous to select a
490 path through the graph that causes rows to naturally appear in sorted order,
491 so that no separate sorting step is required. Automatic elimination of
492 ORDER BY clauses
493 can make a large performance difference, so this is another factor
494 that needs to be considered in a complete implementation.</p>
495
496 <p>In the TPC-H Q8 query, the setup costs are all negligible,
497 all dependencies are between individual nodes, and there is no ORDER BY,
498 GROUP BY, or DISTINCT clause. So for TPC-H Q8,
499 the graph above is a reasonable representation of what needs to be computed.
500 The general case involves a lot of extra complication, which for clarity
501 is neglected in the remainder of this article.</p>
502
503 <h2 id="_finding_the_best_query_plan"><span>3.3. </span> Finding The Best Query Plan</h2>
504
505 <p>Prior to <a href="releaselog/3_8_0.html">version 3.8.0</a> (2013-08-26), SQLite always used
506 the "Nearest Neighbor" or "NN" heuristic when searching for the best query plan.
507 The NN heuristic makes a single traversal of the graph, always choosing
508 the lowest-cost arc as the next step.
509 The NN heuristic works surprisingly well in most cases.
510 And NN is fast, so that SQLite is able to quickly find good plans
511 for even large 64-way joins. In contrast, other SQL database engines that
512 do more extensive searching tend to bog down when the
513 number of tables in a join goes above 10 or 15.</p>
514
515 <p>Unfortunately, the query plan computed by NN for TPC-H Q8 is not optimal.
516 The plan computed using NN is R-N1-N2-S-C-O-L-P with a cost of 36.92.
517 The notation
518 in the previous sentence means that the R table is run in the outer loop,
519 N1 is in the next inner loop, N2 is in the third loop, and so forth down
520 to P which is in the inner-most loop. The shortest path through the
521 graph (as found via exhaustive search) is P-L-O-C-N1-R-S-N2
522 with a cost of 27.38. The difference might not seem like much, but
523 remember that
524 the costs are logarithmic, so the shortest path is nearly 750 times
525 faster than that path found using the NN heuristic.</p>
526
527 <p>One solution to this problem is to change SQLite to do an exhaustive
528 search for the best path. But an exhaustive search requires time
529 proportional to
530 K! (where K is the number of tables in the join) and so when you get
531 beyond a 10-way join, the time
532 to run <a href="c3ref/prepare.html">sqlite3_prepare()</a> becomes very large.</p>
533
534 <a name="n3"></a>
535
536 <h2 id="_the_n_nearest_neighbors_or_n3_algorithm"><span>3.4. </span> The N Nearest Neighbors or "N3" Algorithm</h2>
537
538 <p>The NGQP uses a new algorithm for seeking the best path through the
539 graph: "N Nearest Neighbors" (hereafter "N3"). With N3, instead of
540 choosing just one nearest neighbor for each step, the algorithm keeps
541 track of the N bests paths at each step for some small integer N.</p>
542
543 <p>Suppose N=4. Then for the TPC-H Q8 graph, the first step finds
544 the four shortest paths to visit any single node in the graph:
545
546 </p><blockquote>
547 R (cost: 3.56) <br>
548 N1 (cost: 5.52) <br>
549 N2 (cost: 5.52) <br>
550 P (cost: 7.71) <br>
551 </blockquote>
552
553 <p>The second step finds the four shortest paths to visit two nodes
554 beginning with one of the four paths from the previous step. In the
555 case where two or more paths are equivalent (they have the same set of
556 visited nodes, though possibly in a different order) only the
557 first and lowest-cost path is retained. We have:</p>
558
559 <blockquote>
560 R-N1 (cost: 7.03) <br>
561 R-N2 (cost: 9.08) <br>
562 N2-N1 (cost: 11.04) <br>
563 R-P {cost: 11.27} <br>
564 </blockquote>
565
566 <p>The third step starts with the four shortest two-node paths and finds
567 the four shortest three-node paths:</p>
568
569 <blockquote>
570 R-N1-N2 (cost: 12.55) <br>
571 R-N1-C (cost: 13.43) <br>
572 R-N1-P (cost: 14.74) <br>
573 R-N2-S (cost: 15.08) <br>
574 </blockquote>
575
576 <p>And so forth. There are 8 nodes in the TPC-H Q8 query,
577 so this process repeats a total of 8
578 times. In the general case of a K-way join, the storage requirement
579 is O(N) and the computation time is O(K*N), which is significantly faster
580 than the O(2<small><sup>K</sup></small>) exact solution.</p>
581
582 <p>But what value to choose for N? One might try N=K. This makes the
583 algorithm O(K<small><sup>2</sup></small>)
584 which is actually still quite efficient, since the
585 maximum value of K is 64 and K rarely exceeds 10.
586 But that is not enough for the TPC-H Q8
587 problem. With N=8 on TPC-H Q8 the N3 algorithm finds
588 the solution R-N1-C-O-L-S-N2-P with a cost of 29.78.
589 That is a big improvement over NN, but it is still
590 not optimal. N3 finds the optimal solution for TPC-H Q8
591 when N is 10 or greater.</p>
592
593 <p>The initial implementation of NGQP chooses N=1 for simple queries, N=5
594 for two-way joins and N=10 for all joins with three or more tables.
595 Later, the N value for joins with three or more tables was raised to 12
596 or to 18 if the join is against a star-schema. Further refinements
597 are likely in the future.</p>
598
599 <a name="starq"></a>
600
601 <h1 id="the_star_query_heuristic"><span>4. </span>The Star-Query Heuristic</h1>
602
603 <p>The <a href="queryplanner-ng.html#n3">N3 algorithm</a> works well for most queries. But there are a
604 few cases where it generates a bad plan. Specifically, for some
605 queries against a <a href="https://en.wikipedia.org/wiki/Star_schema">star-schema</a>
606 where there is a large fact table and six or more small dimension
607 tables and where there exist indexes going in both directions, the
608 N3 algorithm misses the best query plan unless the N parameter is
609 very large - exponential in the number of dimension tables.
610 Call these kinds of queries "star-queries".
611 More recent versions of SQLite (circa 2024 or 2025 and later) implement
612 a heuristic to work around this, so that efficient query plans are
613 chosen for star-queries, without requiring hints from the programmer.
614
615 </p><h2 id="background_what_is_a_star_query"><span>4.1. </span>Background: What Is A Star-Query</h2>
616
617 <p>A star-schema is a common relational database design in which
618 there is a large "fact-table" surrounding by smaller "dimension-tables".
619 The dimension-tables are typically keyed by integer ID values and
620 hold a variety of other attributes that are accessed using that ID.
621 The fact-table contains ID values referencing the various
622 dimension tables.
623
624 </p><p>For example, suppose you have dimension tables, all with integer
625 ID values as their PRIMARY KEY, like this:
626
627 </p><ul>
628 <li> A PRODUCT table holds information about each product.
629 </li><li> A SELLER table holds information about each sales staff member.
630 </li><li> A CUSTOMER table holds information about each customer.
631 </li><li> A CARRIER table holds information about each shipping provider.
632 </li><li> A WAREHOUSE table holds information about all warehouses.
633 </li></ul>
634
635 <p>Each of the dimension tables is relatively small. How many
636 warehouses does your business operate? Maybe PRODUCT
637 and CUSTOMER are somewhat larger, but the number of entries might
638 be still measured in thousands, not millions.
639
640 </p><p>The dimension tables are bound together by a single SALES table
641 that records each sale. The SALES table contains things like:
642
643 </p><ul>
644 <li> The time and value of the sale.
645 </li><li> The PRODUCT-id, SELLER-id, CUSTOMER-id, CARRIER-id, and
646 WAREHOUSE-id.
647 </li></ul>
648
649 <p>The SALES table is our fact-table. The number of entries
650 in SALES is orders of magnitude larger than any of the dimension
651 tables. And each SALES table row references a single entry in the
652 various dimension tables. A dimension table row might reference
653 many thousands of SALES table rows, on the other hand.
654
655 </p><p>This is a classic example of a star-schema. Data representations
656 like this come up all the time, and in diverse fields. We call
657 queries against this schema a "star-query". For example, asking
658 for a complete report of all sales between the hours of 12:00
659 and 14:00 on 2024-01-04 would be a star-query. The SALES table
660 would be consulted to find all entries between the specified
661 hours, then the various dimension tables would be consulted to
662 look up information about each individual sale.
663
664 </p><h2 id="query_planning_problems_with_high_dimensionality_star_queries"><span>4.2. </span>Query Planning Problems With High-Dimensionality Star-Queries</h2>
665
666 <p>The <a href="queryplanner-ng.html#n3">N3 query planning algorithm</a> described above works fine
667 and generates a optimal solution for star-queries with less than
668 five or six dimension tables. However, if the number of dimension
669 tables grows larger, then depending on how indexes are defined and
670 on the relative sizes of the fact and dimension tables, the N3
671 algorithm will sometimes find a suboptimal plan.
672
673 </p><p>That happens because N3 is still a greedy algorithm.
674 Even though it is keeping track of up to N different solutions at
675 each step, it only follows the N best solutions. That leads to
676 problems as follows:
677
678 </p><p>The step of finding all relevant entries in the fact table can
679 be slow, because the fact table is so big. Finding relevant values
680 of the fact table might be slower than doing a full table scan of
681 the relatively small dimension tables. The best plan is usually
682 to spend time finding the relevant rows of the fact table first
683 and then do primary-key lookups of corresponding dimension table
684 rows. But because N3 is a greedy algorithm, it tends to accumulate
685 a bunch of full-table scans of dimension tables in its N-best plan
686 set early in the search. If there enough dimension tables, they
687 can fill up all N available slots and push out the best plan which
688 starts with the more expensive search of the fact table.
689
690 </p><p>N3 will still always find the best plan in the end, given a
691 large enough value for N. The trouble is that a sufficiently large
692 N might be exponential in the number of dimension tables. That
693 means that overall query planning algorithm would require
694 exponential time. N3 works great with three or four dimension
695 tables. With a larger number of dimension tables, however, it
696 starts to generate query plans that include full-table scans
697 of the smaller dimension tables, which severely degrades
698 performance.
699
700 </p><h2 id="a_large_test_case"><span>4.3. </span>A Large Test Case</h2>
701
702 <p>The <a href="https://sqlite.org/src/file/test/starschema1.test">test/starschema1.test</a>
703 test script in the SQLite source tree shows a star-query with one
704 fact table and 63 dimension tables.
705 This test case is contrived, but it does demonstrate how the
706 N3 algorithm can fail unless it is amended, as described in the
707 next section.
708
709 </p><h2 id="tweaks_to_n3_to_support_star_queries"><span>4.4. </span>Tweaks To N3 To Support Star Queries</h2>
710
711 <p>To help the SQLite query planner come up with better query plans
712 for star-queries, heuristics are used to adjust cost estimates for
713 searching the various tables.
714
715 </p><p>The current heuristic, as of version 3.49.0 (2025-02-06), is
716 to artificially raise the estimated full-table scan cost for
717 dimension tables so that the cost is slightly greater than the
718 cost of finding the relevant rows of the fact table. This prevents
719 a bunch of pointless full-table scans of dimension tables from
720 pushing the search of the fact table out of the
721 set of N-best solutions early in the algorithm, so that doing
722 the fact table search wins in the end.
723 Only the full-table scan costs of dimension tables are modified.
724 The estimated costs for all other access methods is unchanged, and
725 no costs are changed for tables of the query that are not clearly
726 dimension tables, or for which the evaluation order is already
727 constrained by OUTER JOINs. So the disruption to the algorithm
728 is minimal, but sufficient to always find a good solution for
729 star-queries even with a large number of dimensions.
730
731 </p><p>A different heuristic was used in SQLite versions 3.47.0
732 and 3.48.0. The earlier heuristic was to lower the cost of all
733 fact-table access methods so that they were able to out-compete
734 full-table scans of the dimension tables, and thus avoid
735 being eliminated from consideration early in the algorithm.
736 However, this artificial lowering of the fact-table cost created
737 other distortions that lead to performance regressions for
738 other complex joins.
739
740 <a name="hazards"></a>
741
742 </p><h1 id="_hazards_of_upgrading_to_ngqp"><span>5. </span> Hazards Of Upgrading To NGQP</h1>
743
744 <p><i>&rarr; <b>This section is obsolete and retained for
745 historical reference only.</b> &larr; This section was important
746 when the NGQP was new. But a decade has elapsed, the NGQP has been
747 deployed successfully to billions of devices, and everyone has upgraded,
748 and no performance regressions were ever reported back to the SQLite
749 developers. The upgrade hazard has vanished.
750 <b>Skip ahead to the <a href="queryplanner-ng.html#howtofix">query planner checklist</a></b>.</i>
751
752 </p><p>For most applications, upgrading from the legacy query planner to the NGQP
753 requires little thought or effort.
754 Simply replace the older SQLite version with the newer version of SQLite
755 and recompile and the application will run faster.
756 There are no API changes nor modifications
757 to compilation procedures.</p>
758
759 <p>But as with any query planner change, upgrading to the NGQP does carry
760 a small risk of introducing performance regressions. The problem here is
761 not that the NGQP is incorrect or buggy or inferior to the legacy query
762 planner. Given reliable information about the selectivity of indexes,
763 the NGQP should always pick a plan that is as good as before, or better.
764 The problem is that some applications may be using low-quality and
765 low-selectivity indexes without having run <a href="lang_analyze.html">ANALYZE</a>. The older query
766 planners look at many fewer possible implementations for each query and
767 so they may have stumbled over a good plan by stupid luck. The NGQP, on
768 the other hand, looks at many more query plan possibilities, and it may
769 choose a different query plan that
770 works better in theory, assuming good indexes, but which gives a performance
771 regression in practice, because of the shape of the data.</p>
772
773 <p>Key points:</p>
774
775 <ul>
776 <li><p>The NGQP will always find an equal or better query plan, compared to
777 prior query planners, as long as it
778 has access to accurate <a href="lang_analyze.html">ANALYZE</a> data in the <a href="fileformat2.html#stat1tab">SQLITE_STAT1</a> file.</p>
779 </li><li><p>The NGQP will always find a good query plan
780 as long as the schema does not contain indexes that have more than
781 about 10 or 20 rows with the same value in the left-most column of the
782 index.</p>
783 </li></ul>
784
785 <p>Not all applications meet these conditions. Fortunately,
786 the NGQP will still usually find good query plans, even without these conditions.
787 However, cases do arise (rarely) where performance regressions can occur.</p>
788
789 <a name="fossilcasestudy"></a>
790
791 <h2 id="_case_study_upgrading_fossil_to_the_ngqp"><span>5.1. </span> Case Study: Upgrading Fossil to the NGQP</h2>
792
793 <p>The <a href="http://www.fossil-scm.org/">Fossil DVCS</a> is the version
794 control system used to track all of the SQLite source code.
795 A Fossil repository is an SQLite database file.
796 (Readers are invited to ponder this recursion as an independent exercise.)
797 Fossil is both the version-control system for SQLite and a test
798 platform for SQLite. Whenever enhancements are made to SQLite,
799 Fossil is one of the first applications to test and evaluate those
800 enhancements. So Fossil was an early adopter of the NGQP.</p>
801
802 <p>Unfortunately, the NGQP caused a
803 performance regression in Fossil.</p>
804
805 <p>One of the many reports that Fossil makes available is a timeline of
806 changes to a single branch showing all merges in and out of that branch. See
807 <a href="https://sqlite.org/src/timeline?nd&n=200&r=trunk">https://sqlite.org/src/timeline?nd&n=200&r=trunk</a>
808 for a typical
809 example of such a report. Generating such a report normally takes just
810 a few milliseconds. But after upgrading to the NGQP we noticed that
811 this one report was taking closer to 10 seconds for the trunk of the
812 repository.</p>
813
814 <p>The core query used to generate the branch timeline is shown below.
815 (Readers are not expected to understand the details of this query.
816 Commentary will follow.)</p>
817
818 <blockquote><pre>
819 SELECT
820 blob.rid AS blobRid,
821 uuid AS uuid,
822 datetime(event.mtime,'localtime') AS timestamp,
823 coalesce(ecomment, comment) AS comment,
824 coalesce(euser, user) AS user,
825 blob.rid IN leaf AS leaf,
826 bgcolor AS bgColor,
827 event.type AS eventType,
828 (SELECT group_concat(substr(tagname,5), ', ')
829 FROM tag, tagxref
830 WHERE tagname GLOB 'sym-*'
831 AND tag.tagid=tagxref.tagid
832 AND tagxref.rid=blob.rid
833 AND tagxref.tagtype>0) AS tags,
834 tagid AS tagid,
835 brief AS brief,
836 event.mtime AS mtime
837 FROM event CROSS JOIN blob
838 WHERE blob.rid=event.objid
839 AND (EXISTS(SELECT 1 FROM tagxref
840 WHERE tagid=11 AND tagtype>0 AND rid=blob.rid)
841 OR EXISTS(SELECT 1 FROM plink JOIN tagxref ON rid=cid
842 WHERE tagid=11 AND tagtype>0 AND pid=blob.rid)
843 OR EXISTS(SELECT 1 FROM plink JOIN tagxref ON rid=pid
844 WHERE tagid=11 AND tagtype>0 AND cid=blob.rid))
845 ORDER BY event.mtime DESC
846 LIMIT 200;
847 </pre></blockquote>
848
849 <p>This query is not
850 especially complicated, but even so it replaces hundreds or
851 perhaps thousands of lines of procedural code.
852 The gist of the query is this: Scan down the EVENT table looking
853 for the most recent 200 check-ins that satisfy any one of three conditions:
854
855 </p><p></p><ol>
856 <li> The check-in has a "trunk" tag.
857 </li><li> The check-in has a child that has a "trunk" tag.
858 </li><li> The check-in has a parent that has a "trunk" tag.
859 </li></ol>
860
861 <p>
862 The first condition causes all of the trunk check-ins to be displayed and
863 the second and third cause check-ins that merge into or fork from
864 the trunk to also be included.
865 The three conditions are implemented by the three OR-connected
866 EXISTS statements in the WHERE clause of the query.
867 The slowdown that occurred with the NGQP was caused by the second and
868 third conditions. The problem is the same in each, so we will examine
869 just the second one.
870 The subquery of the second condition can be rewritten (with minor
871 and immaterial simplifications) as follows:</p>
872
873 <blockquote><pre>
874 SELECT 1
875 FROM plink JOIN tagxref ON tagxref.rid=plink.cid
876 WHERE tagxref.tagid=$trunk
877 AND plink.pid=$ckid;
878 </pre></blockquote>
879
880 <p>The PLINK table holds parent-child relationships between
881 check-ins. The TAGXREF table maps tags into check-ins.
882 For reference, the relevant portions of the schemas
883 for these two tables is shown here:</p>
884
885 <blockquote><pre>
886 CREATE TABLE plink(
887 pid INTEGER REFERENCES blob,
888 cid INTEGER REFERENCES blob
889 );
890 CREATE UNIQUE INDEX plink_i1 ON plink(pid,cid);
891
892 CREATE TABLE tagxref(
893 tagid INTEGER REFERENCES tag,
894 mtime TIMESTAMP,
895 rid INTEGER REFERENCE blob,
896 UNIQUE(rid, tagid)
897 );
898 CREATE INDEX tagxref_i1 ON tagxref(tagid, mtime);
899 </pre></blockquote>
900
901 <p>There are only two reasonable ways to implement this query.
902 (There are many other possible algorithms, but none of the
903 others are contenders for being the "best" algorithm.)</p>
904
905 <ol type="1">
906 <li value="1"><p>
907 Find all children of check-in $ckid and test each one to see if
908 it has the $trunk tag.
909 </p></li><li value="2"><p>
910 Find all check-ins with the $trunk tag and test each one to see if
911 it is a child of $ckid.
912 </p></li></ol>
913
914 <p>
915 Intuitively, we humans understand that algorithm-1 is best.
916 Each check-in is likely to have few children (one child is
917 the most common case) and each child can be tested for the
918 $trunk tag in logarithmic time. Indeed, algorithm-1 is the
919 faster choice in practice. But the NGQP has no intuition. The
920 NGQP must use hard math, and algorithm-2 is slightly
921 better mathematically. This is because, in the absence of other information,
922 the NGQP must assume that the indexes PLINK_I1 and TAGXREF_I1 are of
923 equal quality and are equally selective. Algorithm-2 uses one field
924 of the TAGXREF_I1 index and both fields of the PLINK_I1 index whereas
925 algorithm-1 only uses the first field of each index. Since
926 algorithm-2 uses more index material, the NGQP is correct
927 to judge it to be the better algorithm. The scores are close and
928 algorithm-2 just barely squeaks ahead of algorithm-1. But
929 algorithm-2 really is the correct choice here.
930 </p>
931
932 <p>
933 Unfortunately, algorithm-2 is slower than algorithm-1 in
934 this application.
935 </p>
936
937 <p>
938 The problem is that the indexes are not of equal quality.
939 A check-in is likely to only have one child. So the first
940 field of PLINK_I1 will usually narrow down the search to just a single
941 row. But there are thousands and thousands of check-ins tagged with "trunk",
942 so the first field of TAGXREF_I1 will be
943 of little help in narrowing down the search.
944 </p>
945
946 <p>
947 The NGQP has no way of knowing that TAGXREF_I1 is almost useless in this
948 query, unless <a href="lang_analyze.html">ANALYZE</a> has been run on the database. The <a href="lang_analyze.html">ANALYZE</a> command
949 gathers statistics on the quality of the various indexes and stores those
950 statistics in <a href="fileformat2.html#stat1tab">SQLITE_STAT1</a> table.
951 Having access to this statistical information,
952 the NGQP easily chooses algorithm-1 as the best algorithm, by a wide
953 margin.</p>
954
955 <p>Why didn't the legacy query planner choose algorithm-2?
956 Easy: because the NN algorithm
957 never even considered algorithm-2. Graphs of the planning
958 problem look like this:</p>
959
960 <center>
961 <div style="max-width:534px;"><svg xmlns='http://www.w3.org/2000/svg' style='font-size:initial;' class="pikchr" viewBox="0 0 534.752 191.8" data-pikchr-date="20250319161943">
962 <circle cx="61.5913" cy="104.064" r="28.3066" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
963 <text x="61.5913" y="104.064" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" font-size="156.25%" dominant-baseline="central">P</text>
964 <circle cx="163.495" cy="104.064" r="28.3066" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
965 <text x="163.495" y="104.064" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" font-size="156.25%" dominant-baseline="central">T</text>
966 <polygon points="135.188,101.229 122.885,101.223 125.923,93.1349" style="fill:rgb(0,0,0)"/>
967 <path d="M89.8979,101.229 L 101.221,96.9771 Q 112.543,92.7252 121.17,95.9647 L 129.796,99.2041" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
968 <text x="112.543" y="84.6612" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">4.8</text>
969 <polygon points="89.8979,106.898 102.201,106.904 99.1638,114.993" style="fill:rgb(0,0,0)"/>
970 <path d="M135.188,106.898 L 123.866,111.15 Q 112.543,115.402 103.917,112.163 L 95.2902,108.923" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
971 <text x="112.543" y="123.466" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">4.4</text>
972 <circle cx="61.5913" cy="16.3133" r="14.1533" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
973 <text x="61.5913" y="16.3133" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" dominant-baseline="central">*</text>
974 <polygon points="61.5913,75.7572 57.2713,64.2372 65.9113,64.2372" style="fill:rgb(0,0,0)"/>
975 <path d="M61.5913,30.4666L61.5913,69.9972" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
976 <text x="61.5913" y="53.1119" text-anchor="start" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central"> 4.9</text>
977 <circle cx="163.495" cy="16.3133" r="14.1533" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
978 <text x="163.495" y="16.3133" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" dominant-baseline="central">*</text>
979 <polygon points="163.495,75.7572 159.175,64.2372 167.815,64.2372" style="fill:rgb(0,0,0)"/>
980 <path d="M163.495,30.4666L163.495,69.9972" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
981 <text x="163.495" y="53.1119" text-anchor="start" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central"> 5.2</text>
982 <text x="112.543" y="172" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" font-size="125%" dominant-baseline="central">without ANALYZE</text>
983 <circle cx="389.948" cy="104.064" r="28.3066" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
984 <text x="389.948" y="104.064" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" font-size="156.25%" dominant-baseline="central">P</text>
985 <circle cx="491.852" cy="104.064" r="28.3066" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
986 <text x="491.852" y="104.064" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" font-size="156.25%" dominant-baseline="central">T</text>
987 <polygon points="463.545,101.229 451.242,101.223 454.279,93.1349" style="fill:rgb(0,0,0)"/>
988 <path d="M418.254,101.229 L 429.577,96.9771 Q 440.9,92.7252 449.526,95.9647 L 458.153,99.2041" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
989 <text x="440.9" y="84.6612" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">4.4</text>
990 <polygon points="418.254,106.898 430.558,106.904 427.52,114.993" style="fill:rgb(0,0,0)"/>
991 <path d="M463.545,106.898 L 452.222,111.15 Q 440.9,115.402 432.273,112.163 L 423.647,108.923" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
992 <text x="440.9" y="123.466" text-anchor="middle" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central">3.8</text>
993 <circle cx="389.948" cy="16.3133" r="14.1533" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
994 <text x="389.948" y="16.3133" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" dominant-baseline="central">*</text>
995 <polygon points="389.948,75.7572 385.628,64.2372 394.268,64.2372" style="fill:rgb(0,0,0)"/>
996 <path d="M389.948,30.4666L389.948,69.9972" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
997 <text x="389.948" y="53.1119" text-anchor="start" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central"> 3.9</text>
998 <circle cx="491.852" cy="16.3133" r="14.1533" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
999 <text x="491.852" y="16.3133" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" dominant-baseline="central">*</text>
1000 <polygon points="491.852,75.7572 487.532,64.2372 496.172,64.2372" style="fill:rgb(0,0,0)"/>
1001 <path d="M491.852,30.4666L491.852,69.9972" style="fill:none;stroke-width:2.16;stroke:rgb(0,0,0);" />
1002 <text x="491.852" y="53.1119" text-anchor="start" fill="rgb(0,0,0)" font-size="80%" dominant-baseline="central"> 6.1</text>
1003 <text x="440.9" y="172" text-anchor="middle" font-weight="bold" fill="rgb(0,0,0)" font-size="125%" dominant-baseline="central">with ANALYZE</text>
1004 </svg>
1005 </div>
1006 </center>
1007
1008 <p>
1009 In the "without ANALYZE" case on the left, the NN algorithm chooses
1010 loop P (PLINK) as the outer loop because 4.9 is less than 5.2, resulting
1011 in path P-T which is algorithm-1. NN only looks at the single best choice
1012 at each step so it completely misses the fact that
1013 5.2+4.4 makes a slightly cheaper plan than 4.9+4.8. But the N3 algorithm
1014 keeps track of the 5 best paths for a 2-way join, so it ends up
1015 selecting path T-P because of its slightly lower overall cost.
1016 Path T-P is algorithm-2.
1017 </p>
1018
1019 <p>
1020 Note that with ANALYZE the cost estimates are
1021 better aligned with reality and algorithm-1 is
1022 selected by both NN and N3.
1023 </p>
1024
1025 <p>(Side note: The costs estimates in the two most recent graphs
1026 were computed by the NGQP using a base-2 logarithm and slightly different
1027 cost assumptions compared to the legacy query planner.
1028 Hence, the cost estimates in
1029 these latter two graphs are not directly comparable to the cost estimates
1030 in the TPC-H Q8 graph.)</p>
1031
1032 <h2 id="_fixing_the_problem"><span>5.2. </span> Fixing The Problem</h2>
1033
1034 <p>Running <a href="lang_analyze.html">ANALYZE</a> on the repository database immediately fixed the
1035 performance problem. However, we want Fossil to be robust and to always
1036 work quickly regardless of whether or not its repository has been analyzed.
1037 For this reason, the query was modified to use the CROSS JOIN operator
1038 instead of the plain JOIN operator.
1039 SQLite will not reorder the tables of a CROSS JOIN.
1040 This is a long-standing feature of SQLite that is specifically designed
1041 to allow knowledgeable programmers
1042 to enforce a particular loop nesting order. Once the join
1043 was changed to CROSS JOIN (the addition of a single keyword) the NGQP was
1044 forced to choose the faster algorithm-1 regardless of whether or not
1045 statistical information had been gathered using ANALYZE.</p>
1046
1047 <p>We say that algorithm-1 is "faster", but this
1048 is not strictly true. Algorithm-1 is faster in common repositories, but
1049 it is possible to construct a repository in which
1050 every check-in is on a different uniquely-named branch and
1051 all check-ins are children of the root check-in.
1052 In that case, TAGXREF_I1 would become more selective
1053 than PLINK_I1 and algorithm-2 really would be the faster choice.
1054 However such repositories are very unlikely to appear in
1055 practice and so hard-coding the loop nested order using the
1056 CROSS JOIN syntax is a reasonable solution
1057 to the problem in this case.</p>
1058
1059 <h2 id="update_2017_a_better_fix"><span>5.3. </span>Update 2017: A Better Fix</h2>
1060
1061 <p>The prior text was written in early 2013, before the first release of
1062 SQLite version 3.8.0. This paragraph was added in mid 2021.
1063 While all of the previous discussion remains true, a lot of improvements
1064 have been made to the query planner, making this whole section largely moot.
1065
1066 </p><p>In 2017, Fossil was enhanced to make use of the new
1067 <a href="pragma.html#pragma_optimize">PRAGMA optimize</a> statement. Whenever Fossil is about to close the
1068 database connection to its repository, it first runs
1069 "PRAGMA optimize", which will in turn cause ANALYZE to be run if it
1070 is needed. Usually an ANALYZE is not needed, and so there is no
1071 measurable performance penalty for doing this. But every now and
1072 then ANALYZE might be run on a few of the tables in the repository
1073 database. Because of this, query planning issues such as the one
1074 described here no longer come up in Fossil. The fact that ANALYZE
1075 is run periodically to keep the <a href="fileformat2.html#stat1tab">sqlite_stat1</a> table up-to-date means
1076 that hand-tuning of queries is no longer required. We have not had
1077 to tweak a query in Fossil in ages.
1078
1079 </p><p>Therefore, the current recommendation for avoiding problems such
1080 as this one is to simply run "PRAGMA optimize" just prior to closing
1081 each database connection. Or, if your application is long-running and
1082 never closes any database connections, then run "PRAGMA optimize" once
1083 per day or so. Also consider running "PRAGMA optimize" after any
1084 schema change.
1085
1086 <a name="howtofix"></a>
1087
1088 </p><h1 id="_checklist_for_avoiding_or_fixing_query_planner_problems"><span>6. </span> Checklist For Avoiding Or Fixing Query Planner Problems</h1>
1089
1090 <ol>
1091 <li><p><b>Don't panic!</b>
1092 Cases where the query planner picks an inferior plan are actually quite
1093 rare. You are unlikely to run across any problems in your application.
1094 If you are not having performance issues, you do not need to worry
1095 about any of this.</p>
1096
1097 </li><li><p><b>Create appropriate indexes.</b>
1098 Most SQL performance problems arise not because of query planner issues
1099 but rather due to lack of appropriate indexes. Make sure indexes are
1100 available to assist all large queries. Most performance issues can be
1101 resolved by one or two CREATE INDEX commands and with no changes to
1102 application code.</p>
1103
1104 </li><li><p><b>Avoid creating low-quality indexes.</b>.
1105 A low-quality index (for the purpose of this checklist) is one where
1106 there are more than 10 or 20 rows in the table that have the same value
1107 for the left-most column of the index. In particular, avoid using
1108 boolean or "enum" columns as the left-most columns of your indexes.</p>
1109
1110 <p>The Fossil performance problem described in the previous section of
1111 this document arose because there were over
1112 ten-thousand entries in the TAGXREF table with the same value for the
1113 left-most column (the TAGID column) of the TAGXREF_I1 index.</p>
1114
1115 </li><li><p><b>If you must use a low-quality index, be sure to run <a href="lang_analyze.html">ANALYZE</a>.</b>
1116 Low-quality indexes will not confuse the query planner as long as the
1117 query planner knows that the indexes are of low quality. And the way
1118 the query planner knows this is by the content of the <a href="fileformat2.html#stat1tab">SQLITE_STAT1</a> table,
1119 which is computed by the ANALYZE command.</p>
1120
1121 <p>Of course, ANALYZE only works effectively if you have a significant
1122 amount of content in your database in the first place. When creating a
1123 new database that you expect to accumulate a lot of data, you can run
1124 the command "ANALYZE sqlite_schema" to create the SQLITE_STAT1 table,
1125 then prepopulate the <a href="fileformat2.html#stat1tab">sqlite_stat1</a> table (using ordinary INSERT statements)
1126 with content that describes a typical
1127 database for your application - perhaps content that you extracted after
1128 running ANALYZE on a well-populated template database in the lab.
1129 Or, you could just run "<a href="pragma.html#pragma_optimize">PRAGMA optimize</a>" before shutting down
1130 database connections so that ANALYZE will be run automatically as
1131 needed to keep the <a href="fileformat2.html#stat1tab">sqlite_stat1</a> table current.</p></li>
1132
1133 <li><p><b>Instrument your code.</b>
1134 Add logic that lets you know quickly and easily which queries are taking
1135 too much time. Then work on just those specific queries.</p>
1136
1137 <p>
1138 </p><hr>
1139 <i>Update 2024: The query planner has been improved so much over
1140 the years that you should never need to use any of the
1141 hacks described below. The capabilities described below are still
1142 available, for backwards compatibility. But you shouldn't use
1143 them. If you do find a case where you are getting a suboptimal query
1144 plan, please report it to the SQLite developers on the
1145 <a href="https://sqlite.org/forum">SQLite Forum</a> so that they can try to fix
1146 the problem. In other words:
1147 <p>
1148 </p><center><b>Stop Reading Here!</b></center>
1149 <p>To help encourage you to stop reading, the remainder of this checklist
1150 is now grayed out.
1151 </p><hr>
1152
1153 </i></li><li><p style="color:grey;">Use <a href="lang_corefunc.html#unlikely">unlikely()</a> and <a href="lang_corefunc.html#likelihood">likelihood()</a> SQL functions.
1154 SQLite normally assumes that terms in the WHERE clause that cannot be used
1155 by indexes have a strong probability of being true. If this assumption
1156 is incorrect, it could lead to a suboptimal query plan. The
1157 <a href="lang_corefunc.html#unlikely">unlikely()</a> and <a href="lang_corefunc.html#likelihood">likelihood()</a> SQL functions can be used to provide
1158 hints to the query planner about WHERE clause terms that are probably
1159 not true, and thus aid the query planner in selecting the best possible
1160 plan.
1161
1162 </p></li><li><p style="color:grey;">Use the <a href="optoverview.html#crossjoin">CROSS JOIN</a> syntax to enforce a particular
1163 loop nesting order on queries that might use low-quality indexes in an
1164 unanalyzed database.
1165 SQLite <a href="lang_select.html#crossjoin">treats the CROSS JOIN operator specially</a>, forcing the table to
1166 the left to be an outer loop relative to the table on the right.</p>
1167
1168 </li><li><p style="color:grey;">Use unary "+" operators to disqualify WHERE clause terms.
1169 If the query planner insists on selecting a poor-quality index for a particular
1170 query when a much higher-quality index is available, then
1171 <a href="optoverview.html#uplus">careful use of unary "+" operators</a> in the WHERE clause
1172 can force the query planner away from the poor-quality index.
1173 Avoid using this trick if at all possible, and especially avoid it
1174 early in the application development cycle. Beware that
1175 adding a unary "+" operator to an equality expression might change
1176 the result of that expression if
1177 <a href="datatype3.html#affinity">type affinity</a> is involved.</p>
1178
1179 </li><li><p style="color:grey;">Use the <a href="lang_indexedby.html">INDEXED BY</a> syntax to enforce the selection of
1180 particular indexes on problem queries.
1181 As with the previous two bullets, avoid this step if possible, and
1182 especially avoid doing this early in development as it is clearly a
1183 premature optimization.</p>
1184 </li></ol>
1185
1186 <h1 id="_summary"><span>7. </span> Summary</h1>
1187
1188 <p>The query planner in SQLite normally does a terrific job of selecting
1189 fast algorithms for running your SQL statements. This is true of the
1190 legacy query planner and even more true of the new NGQP. There may be
1191 an occasional situation where, due to incomplete information, the query
1192 planner selects a suboptimal plan. This will happen less often with the
1193 NGQP than with the legacy query planner, but it might still happen. Only
1194 in those rare cases do application developers need to get involved and
1195 help the query planner to do the right thing. In the common case, the
1196 NGQP is just a new enhancement to SQLite that makes the application run
1197 a little faster and which requires no new developer thought or action.</p>
1198 <p align="center"><small><i>This page was last updated on 2025-07-12 15:11:36Z </small></i></p>
1199