| 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>→ <b>This section is obsolete and retained for |
| 745 |
historical reference only.</b> ← 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 |
|