DBMS-Course/topics/07-query-processing.html at main · sridhar-3009/DBMS-Course · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0">
  <script>try{var t=localStorage.getItem("dbms-theme")||"dark";document.documentElement.setAttribute("data-theme",t)}catch(e){document.documentElement.setAttribute("data-theme","dark")}</script>
  <title>Query Processing — DBMS Illustrated</title>
  <link rel="stylesheet" href="../css/style.css">
  <style>:root{--topic-color:#3B82F6}</style>
</head>
<body>
<div class="reading-progress" id="reading-progress"></div>
<nav class="navbar">
  <div class="navbar-inner">
    <a class="navbar-brand" href="../index.html"><span class="brand-icon" style="color:var(--primary-soft)">&#9670;</span>DBMS Illustrated</a>
    <div class="navbar-links"><a href="../index.html#topics">All Topics</a></div>
    <div class="navbar-actions"><button class="btn-icon" id="theme-toggle" title="Toggle theme">&#9788;</button></div>
  </div>
</nav>

<div class="container">
  <div class="breadcrumb">
    <a href="../index.html">Home</a><span class="breadcrumb-sep">›</span>
    <a href="../index.html#topics">Course</a><span class="breadcrumb-sep">›</span><span>Query Processing</span>
  </div>

  <div class="topic-header">
    <div class="topic-badge">Topic 07</div>
    <h1>Query <span class="accent">Processing</span></h1>
    <p class="subtitle">When you type a SQL query, the database does not just run it blindly. It reads the query, validates it, thinks about several ways it could be answered, picks the fastest approach, and then executes it. This topic pulls back the curtain on that process — from the moment you press Enter to the moment rows come back.</p>
    <div class="company-badges">
      <span class="badge">PostgreSQL</span><span class="badge">MySQL</span><span class="badge">SQL Server</span>
      <span class="badge">BigQuery</span><span class="badge">Presto</span>
    </div>
  </div>

  <div class="at-a-glance reveal">
    <h3>At a Glance</h3>
    <ul>
      <li><strong>Query pipeline</strong> — every SQL query goes through five steps before returning results: Parse (read and understand the SQL), Validate (check names and permissions), Rewrite (clean up and expand views), Optimize (pick the fastest plan), Execute (actually do the work).</li>
      <li><strong>Cost-based optimizer</strong> — the database keeps statistics about how many rows are in each table and how the data is distributed. It uses those numbers to estimate how much work each possible plan would take, then picks the cheapest one.</li>
      <li><strong>Nested loop join</strong> — for each row in the first table, look up the matching row in the second table. Great when the second table has an index and the first is small. Terrible for large tables without indexes.</li>
      <li><strong>Hash join</strong> — build a lookup table from the smaller dataset, then probe it with rows from the larger. Efficient for large un-indexed joins as long as the lookup table fits in memory.</li>
      <li><strong>EXPLAIN ANALYZE</strong> — shows the database's plan and compares estimated row counts to actual row counts. A big mismatch means the statistics are stale — run ANALYZE to update them.</li>
    </ul>
  </div>

  <div class="section-label">Core Concepts</div>
  <div class="mini-cards">
    <div class="mini-card">
      <div class="mini-card-icon"></div>
      <h4>Query Optimizer</h4>
      <p>Think of the query optimizer as a travel planner. You say "get me from A to B." It considers multiple routes (execution plans), estimates how long each would take based on current conditions (table statistics — like traffic data), and picks the fastest route. A good optimizer can make the difference between a query that takes 10 seconds and one that takes 10 milliseconds. It uses statistics about how many rows are in each table and how data is distributed to make its estimates.</p>
    </div>
    <div class="mini-card">
      <div class="mini-card-icon"></div>
      <h4>Join Algorithms</h4>
      <p>When two tables need to be joined, the database has three main strategies. Nested Loop: for each row on one side, look up the matching row on the other — simple, but slow for large tables unless there is an index. Hash Join: build a lookup table from the smaller side in memory, then quickly find matches — great for large joins. Merge Join: if both sides are already sorted in the same order, walk through them in sync — very efficient when the sort is "free" from an existing index.</p>
    </div>
    <div class="mini-card">
      <div class="mini-card-icon"></div>
      <h4>Statistics and Cardinality</h4>
      <p>The optimizer needs to guess how many rows a filter will return — for example, how many employees earn over $80,000. This guess is called a cardinality estimate. To make good guesses, the database maintains statistics: rough summaries of how data is distributed in each column (like a histogram). When statistics are stale (out of date after large inserts or deletes), the guesses are wrong, the optimizer picks a bad plan, and queries get slow. Running ANALYZE updates the statistics and usually fixes this.</p>
    </div>
    <div class="mini-card">
      <div class="mini-card-icon"></div>
      <h4>Materialized Views</h4>
      <p>A regular view is just a saved query — every time you query it, the database runs the full computation. A materialized view is a view whose results are pre-computed and stored on disk like a table. Querying it is instant. The trade-off: the stored results can become stale when the underlying tables change. You need to refresh the materialized view periodically. Best for expensive reports or dashboards where slightly outdated data is acceptable and the query itself takes seconds to compute.</p>
    </div>
  </div>

  <div class="section-label">How It Works</div>
  <h2 class="section-title">Query Lifecycle</h2>
  <div class="steps">
    <div class="step-item"><div class="step-num">1</div><div><h4>Parse</h4><p>The database reads your SQL text like a compiler reads source code. It checks for syntax errors, confirms that the table names and column names actually exist, verifies the data types make sense, and checks that you have permission to access those tables. If anything is wrong at this stage, you get an error before any data is even looked at.</p></div></div>
    <div class="step-item"><div class="step-num">2</div><div><h4>Rewrite (Rule System)</h4><p>Before planning, the database silently rewrites your query to make it complete and safe. If you referenced a view (a saved query with a name), it replaces the view name with the actual query behind it. If there are row-level security rules (for example, "this user can only see their own data"), those get injected here. The final query may look quite different internally from what you wrote — but the result is always the same.</p></div></div>
    <div class="step-item"><div class="step-num">3</div><div><h4>Plan (Optimize)</h4><p>This is where the database decides how to answer your query. It generates multiple candidate plans and estimates the cost of each one — counting disk reads, CPU work, and memory. It picks the cheapest plan. For queries that join many tables, the number of possible plans explodes exponentially, so the optimizer uses smart search strategies (like dynamic programming) to find a good plan quickly without trying every possibility.</p></div></div>
    <div class="step-item"><div class="step-num">4</div><div><h4>Execute (Iterator Model)</h4><p>The execution works like an assembly line. The plan is a tree of operations — scan a table, filter rows, join, sort, aggregate. Each step asks the step below it "give me the next row," processes it, and passes it up. This pull-based approach is called the Iterator model (sometimes called the Volcano model). It is memory-efficient because only a few rows are in-flight at any given moment. Modern analytical databases process larger batches at once for better speed.</p></div></div>
  </div>

  <div class="section-label">Join Algorithm Deep Dive</div>
  <h2 class="section-title">Choosing the Right Algorithm</h2>
  <div class="steps">
    <div class="step-item">
      <div class="step-num">1</div>
      <div>
        <h4>Nested Loop Join</h4>
        <p>The simplest join strategy: for each row on one side, go look up the matching rows on the other side. If you are looking up a customer's orders, this is like reading each customer's row, then going to find their orders. Without an index on the orders table, you scan the entire orders table for every customer — very slow. With an index, each lookup is fast. The optimizer uses this when one side is small and the other side has an index on the join column.</p>
      </div>
    </div>
    <div class="step-item">
      <div class="step-num">2</div>
      <div>
        <h4>Hash Join</h4>
        <p>A smarter approach for large tables without indexes. In the first step (Build), the database reads the smaller table and builds a hash table in memory — like creating a quick-lookup dictionary. In the second step (Probe), it reads the larger table row by row and looks each row up in that dictionary. This is much faster than nested loop for large data because each lookup is nearly instant. The catch: the hash table (dictionary) needs to fit in memory. If it is too large, the database has to spill some of it to disk, which is slower.</p>
      </div>
    </div>
    <div class="step-item">
      <div class="step-num">3</div>
      <div>
        <h4>Sort-Merge Join</h4>
        <p>If both tables are already sorted by the join column (because of an index), this strategy is very efficient. Imagine merging two sorted decks of cards — you just look at the top of each deck, match pairs, and advance. You walk through both tables simultaneously in order, picking up matching pairs. If the tables are not already sorted, the database has to sort them first, which adds cost. But if an index provides the sorted order for free, this join type needs minimal extra work and produces results in sorted order — potentially eliminating a later ORDER BY step.</p>
      </div>
    </div>
    <div class="step-item">
      <div class="step-num">4</div>
      <div>
        <h4>Optimizer Choice Heuristics</h4>
        <p>You do not need to tell the database which join algorithm to use — the optimizer decides based on the situation. As a rough guide: Nested Loop with an index is best when one side is small (a few hundred rows) and the other has an index. Hash Join is best for large tables without useful indexes. Sort-Merge is best when both sides are already sorted or when sorted output is needed downstream. If the optimizer makes a bad choice (usually because its statistics are outdated), refresh them with ANALYZE and the plan usually improves.</p>
      </div>
    </div>
  </div>

  <div class="comparison-grid">
    <div class="comparison-card">
      <h4>Hash Join</h4>
      <ul>
        <li>Build hash table from smaller relation</li>
        <li>Probe with larger relation rows</li>
        <li>O(n+m) time, O(min(n,m)) space</li>
        <li>Best when one side fits in memory</li>
        <li>Unsorted output</li>
        <li>Spills to disk if memory exceeded</li>
      </ul>
    </div>
    <div class="comparison-card">
      <h4>Merge Join</h4>
      <ul>
        <li>Both inputs must be sorted on join key</li>
        <li>Walk both sorted lists in lockstep</li>
        <li>O(n log n + m log m) if sorting needed</li>
        <li>Best with sorted inputs or needed sort</li>
        <li>Produces sorted output — eliminates ORDER BY</li>
        <li>Can exploit existing index order</li>
      </ul>
    </div>
    <div class="comparison-card">
      <h4>Nested Loop Join</h4>
      <ul>
        <li>For each outer row, scan inner table</li>
        <li>O(n x m) without index, O(n log m) with index</li>
        <li>Best when outer is tiny and inner has index</li>
        <li>No memory requirement</li>
        <li>Bad for large unsorted tables</li>
        <li>Default when optimizer has no better option</li>
      </ul>
    </div>
    <div class="comparison-card">
      <h4>Vectorized Execution</h4>
      <ul>
        <li>Process batches of 1024 rows at once</li>
        <li>SIMD instructions operate on whole vectors</li>
        <li>Better CPU cache utilization than Volcano</li>
        <li>DuckDB, Snowflake, ClickHouse, Velox</li>
        <li>10-100x throughput vs tuple-at-a-time</li>
        <li>Best for analytical (OLAP) workloads</li>
      </ul>
    </div>
  </div>

  <div class="code-block">
    <div class="cb-header"><span class="cb-lang">PostgreSQL EXPLAIN ANALYZE</span></div>
    <pre><span class="kw">EXPLAIN</span> (<span class="kw">ANALYZE</span>, <span class="kw">BUFFERS</span>, <span class="kw">FORMAT</span> TEXT)
<span class="kw">SELECT</span> d.dept_name, <span class="fn">COUNT</span>(*), <span class="fn">AVG</span>(e.salary)
<span class="kw">FROM</span>  employees e <span class="kw">JOIN</span> departments d <span class="kw">ON</span> e.dept_id = d.dept_id
<span class="kw">WHERE</span> e.hire_date > <span class="str">'2020-01-01'</span>
<span class="kw">GROUP BY</span> d.dept_name;

<span class="cmt">-- Annotated output:
-- HashAggregate  (cost=245.20..247.70 rows=200 width=44)
--                (actual time=12.4..12.6 rows=15 loops=1)
--   ->  Hash Join  (cost=42.00..220.00 rows=1040 width=28)
--                  (actual time=1.2..9.8 rows=1040 loops=1)
--         Hash Cond: (e.dept_id = d.dept_id)
--         ->  Seq Scan on employees  (cost=0.00..160.00 rows=1040)
--                                    (actual rows=1040)
--               Filter: (hire_date > '2020-01-01')
--               Rows Removed by Filter: 8960
--         ->  Hash  (cost=22.00..22.00 rows=200)
--               Buckets: 1024  Batches: 1  Memory Usage: 18kB
--               ->  Seq Scan on departments (rows=200)
--
-- Key signals:
-- estimated 1040 = actual 1040: good estimate, plan is correct
-- Rows Removed by Filter: 8960 of 10000 = 89.6% selectivity
-- Memory Usage: 18kB — well within work_mem, no spill</span>

<span class="cmt">Force stats refresh if estimates are wrong</span>
<span class="kw">ANALYZE</span> employees;
<span class="kw">ANALYZE</span> departments;

<span class="cmt">Extended statistics for correlated columns</span>
<span class="kw">CREATE STATISTICS</span> emp_dept_stats <span class="kw">ON</span> dept_id, hire_date
<span class="kw">FROM</span> employees;</pre>
  </div>

  <div class="section-label">Interactive Demo</div>
  <h2 class="section-title">Query Execution Plan Visualizer</h2>
  <p class="section-desc">Pick a query preset. Watch data packets flow upward through the plan tree — from table scans through joins to the final result.</p>

  <div class="diagram-box">
    <svg viewBox="0 0 700 230" role="img" aria-label="Query execution plan: scan, filter, hash join, aggregate, result">
      <!-- Result at top -->
      <rect x="260" y="8"  width="180" height="42" rx="8" class="svg-box-g"/>
      <text x="350" y="26"  text-anchor="middle" class="svg-label">Result Set</text>
      <text x="350" y="43"  text-anchor="middle" class="svg-soft">returned to client</text>
      <!-- Aggregate -->
      <rect x="260" y="74" width="180" height="42" rx="8" class="svg-box-a"/>
      <text x="350" y="92"  text-anchor="middle" class="svg-label">Aggregate</text>
      <text x="350" y="109" text-anchor="middle" class="svg-soft">SUM / COUNT / GROUP BY</text>
      <!-- Hash Join -->
      <rect x="260" y="140" width="180" height="42" rx="8" class="svg-box-p"/>
      <text x="350" y="158" text-anchor="middle" class="svg-label">Hash Join</text>
      <text x="350" y="175" text-anchor="middle" class="svg-soft">build hash table on smaller rel</text>
      <!-- Seq Scan left -->
      <rect x="60"  y="185" width="165" height="42" rx="8" class="svg-box-c"/>
      <text x="142" y="203" text-anchor="middle" class="svg-label">Seq Scan</text>
      <text x="142" y="220" text-anchor="middle" class="svg-mono">employees (full)</text>
      <!-- Index Scan right -->
      <rect x="475" y="185" width="165" height="42" rx="8" class="svg-box-c"/>
      <text x="557" y="203" text-anchor="middle" class="svg-label">Index Scan</text>
      <text x="557" y="220" text-anchor="middle" class="svg-mono">departments (dept_id)</text>
      <!-- Vertical connectors -->
      <line x1="350" y1="50"  x2="350" y2="74"  class="svg-line"/>
      <line x1="350" y1="116" x2="350" y2="140" class="svg-line"/>
      <line x1="350" y1="182" x2="142" y2="185" class="svg-line"/>
      <line x1="350" y1="182" x2="557" y2="185" class="svg-line"/>
      <!-- Cost labels -->
      <text x="590" y="92"  class="svg-mono" style="font-size:10px;fill:#F59E0B">cost: 1200</text>
      <text x="590" y="160" class="svg-mono" style="font-size:10px;fill:#F59E0B">cost: 980</text>
      <text x="590" y="208" class="svg-mono" style="font-size:10px;fill:#F59E0B">cost: 42</text>
      <!-- Packets flowing upward -->
      <circle class="pkt" cx="142" cy="185" r="5" fill="#0EA5E9"/>
      <circle class="pkt" cx="350" cy="182" r="5" fill="#7C3AED"/>
      <circle class="pkt" cx="350" cy="116" r="5" fill="#F59E0B"/>
      <circle class="pkt" cx="350" cy="50"  r="5" fill="#10B981"/>
    </svg>
    <p class="diagram-caption">The planner builds a tree where rows flow upward — leaves produce tuples, parent operators consume and transform them. The optimizer chooses operators (hash vs. merge join, seq vs. index scan) by minimizing estimated cost using statistics from pg_statistic.</p>
  </div>

  <div class="demo-section" id="demo-query">
    <div class="demo-header">
      <h3>Execution Plan Tree</h3>
      <div class="demo-controls">
        <button class="demo-btn" data-plan="simple">Simple SELECT</button>
        <button class="demo-btn" data-plan="join">JOIN Query</button>
        <button class="demo-btn" data-plan="agg">GROUP BY + AGG</button>
      </div>
    </div>
    <div class="demo-canvas-wrap"></div>
    <div class="demo-hint">Colored particles flow from leaf nodes (scans) upward through operators to Result. Cost shown on each node.</div>
  </div>

  <div class="section-label">Predicate Pushdown</div>
  <h2 class="section-title">Filter Early, Join Less</h2>
  <div class="steps">
    <div class="step-item">
      <div class="step-num">1</div>
      <div>
        <h4>What It Is</h4>
        <p>Predicate pushdown is an optimization where the database moves your WHERE filter as early as possible in the execution plan — ideally right when reading the table. The idea is to throw away irrelevant rows as soon as possible, so expensive operations like joins and aggregations have less data to process. The database applies this automatically — you just write a good WHERE clause.</p>
      </div>
    </div>
    <div class="step-item">
      <div class="step-num">2</div>
      <div>
        <h4>Example: 20x Smaller Join</h4>
        <p>Imagine joining 1 million employees with 200 departments, then filtering for only the Engineering department. Without pushdown, the join produces 200 million row combinations and then throws most away. With pushdown, the database first filters down to the ~50,000 Engineering employees, then joins only those 50,000 with the 200 departments. The join is 20 times smaller. Same final result — but the work is dramatically reduced.</p>
      </div>
    </div>
    <div class="step-item">
      <div class="step-num">3</div>
      <div>
        <h4>Distributed Systems Impact</h4>
        <p>In large-scale analytics tools (like Spark, BigQuery, or Snowflake), predicate pushdown becomes even more powerful. If your data is partitioned by date (meaning each month's data is in a separate file), and you query only January, the database only reads January's file — it skips the rest entirely. This can reduce the amount of data read from gigabytes to megabytes. Designing your data partitioning around your most common filters is one of the highest-leverage optimizations in large-scale analytics.</p>
      </div>
    </div>
  </div>

  <div class="section-label">Anti-patterns</div>
  <div class="antipatterns">
    <div class="antipattern">
      <h4>Stale statistics causing bad plans</h4>
      <p>If ANALYZE has not run after a large data load, the optimizer uses outdated row count estimates. A table that grew from 100K to 10M rows without ANALYZE may get Nested Loop joins instead of Hash joins — orders of magnitude slower. Run ANALYZE after bulk loads.</p>
    </div>
    <div class="antipattern">
      <h4>Implicit type casts defeating index usage</h4>
      <p>WHERE user_id = '12345' when user_id is BIGINT forces a cast on every row during a sequential scan. The optimizer cannot use an index because it does not know the cast will preserve order. Match parameter types to column types exactly.</p>
    </div>
    <div class="antipattern">
      <h4>Not using EXPLAIN ANALYZE before deploying</h4>
      <p>EXPLAIN (without ANALYZE) shows only estimated costs. EXPLAIN ANALYZE shows actual row counts and time. A query with estimated 100 rows but actual 100,000 rows has bad statistics and will have a bad plan in production.</p>
    </div>
    <div class="antipattern">
      <h4>Setting work_mem too low</h4>
      <p>Hash joins and sorts that exceed work_mem spill to disk, often causing a 10-100x slowdown. Check for "Batches: N" in EXPLAIN output where N > 1 — this means disk spill. Increase work_mem for the session on expensive queries: <code>SET work_mem = '256MB'</code>.</p>
    </div>
  </div>

  <div class="section-label">Quiz</div>
  <div class="quiz-section">
    <div class="quiz-question">
      <div class="quiz-q-num">Question 1 of 5</div>
      <div class="quiz-q-text">Hash join is preferred over nested loop join when:</div>
      <div class="quiz-options">
        <div class="quiz-option" data-correct="false" data-explanation="Sorted inputs favor merge join, not hash join."><span class="opt-letter">A</span>Both tables are sorted on the join key</div>
        <div class="quiz-option" data-correct="false" data-explanation="Neither fitting in memory makes hash join spill to disk — less ideal than when one side fits."><span class="opt-letter">B</span>Neither table fits in memory</div>
        <div class="quiz-option" data-correct="true" data-explanation="Hash join builds a hash table from the smaller relation in memory, then probes it with the larger. O(n+m) vs O(n x m) for nested loop on large unsorted tables."><span class="opt-letter">C</span>One side fits in memory and tables are large and unsorted</div>
        <div class="quiz-option" data-correct="false" data-explanation="An available index favors index nested loop join, not hash join."><span class="opt-letter">D</span>An index is available on the join column</div>
      </div>
      <div class="quiz-feedback"></div>
    </div>
    <div class="quiz-question">
      <div class="quiz-q-num">Question 2 of 5</div>
      <div class="quiz-q-text">The query optimizer uses statistics to:</div>
      <div class="quiz-options">
        <div class="quiz-option" data-correct="false" data-explanation="Statistics inform planning; correctness is enforced by the execution engine."><span class="opt-letter">A</span>Guarantee query correctness</div>
        <div class="quiz-option" data-correct="true" data-explanation="Statistics (row counts, histograms, distinct values) help the optimizer estimate how many rows each operation will produce — enabling cost-based plan selection."><span class="opt-letter">B</span>Estimate cardinality and choose the lowest-cost plan</div>
        <div class="quiz-option" data-correct="false" data-explanation="Locks are managed by the transaction manager, not statistics."><span class="opt-letter">C</span>Lock the relevant resources before execution</div>
        <div class="quiz-option" data-correct="false" data-explanation="Query result caching is a separate mechanism from statistics."><span class="opt-letter">D</span>Cache query results for future identical queries</div>
      </div>
      <div class="quiz-feedback"></div>
    </div>
    <div class="quiz-question">
      <div class="quiz-q-num">Question 3 of 5</div>
      <div class="quiz-q-text">A materialized view differs from a regular view in that it:</div>
      <div class="quiz-options">
        <div class="quiz-option" data-correct="false" data-explanation="Regular views are recomputed on every query; materialized views store the result."><span class="opt-letter">A</span>Is recomputed on every query</div>
        <div class="quiz-option" data-correct="true" data-explanation="A materialized view stores the query result on disk. Reads are instant (just scan the stored data). Trade-off: data may be stale until refreshed."><span class="opt-letter">B</span>Stores precomputed query results on disk</div>
        <div class="quiz-option" data-correct="false" data-explanation="Materialized views can be indexed just like regular tables."><span class="opt-letter">C</span>Cannot be indexed</div>
        <div class="quiz-option" data-correct="false" data-explanation="Materialized views work for any query type, not just aggregates."><span class="opt-letter">D</span>Only works with GROUP BY aggregations</div>
      </div>
      <div class="quiz-feedback"></div>
    </div>
    <div class="quiz-question">
      <div class="quiz-q-num">Question 4 of 5</div>
      <div class="quiz-q-text">In the Volcano/Iterator execution model, how do rows flow through the query plan?</div>
      <div class="quiz-options">
        <div class="quiz-option" data-correct="false" data-explanation="Rows flow upward from leaf nodes (scans) to the root (result), not downward."><span class="opt-letter">A</span>From the root node downward to leaf scans</div>
        <div class="quiz-option" data-correct="false" data-explanation="Rows are not loaded into memory all at once in the Volcano model — it is tuple-at-a-time."><span class="opt-letter">B</span>All rows are loaded into memory, then processed</div>
        <div class="quiz-option" data-correct="true" data-explanation="Each operator calls GetNext() on its children, pulling one tuple at a time from the bottom up. Rows flow from leaf scans (bottom) to the result node (top)."><span class="opt-letter">C</span>Each operator pulls one row at a time from its children — bottom up</div>
        <div class="quiz-option" data-correct="false" data-explanation="Operators do not push rows to parents in the Volcano model; parents pull from children."><span class="opt-letter">D</span>Each operator pushes rows to its parent node</div>
      </div>
      <div class="quiz-feedback"></div>
    </div>
    <div class="quiz-question">
      <div class="quiz-q-num">Question 5 of 5</div>
      <div class="quiz-q-text">What does predicate pushdown accomplish in a query plan?</div>
      <div class="quiz-options">
        <div class="quiz-option" data-correct="false" data-explanation="Predicate pushdown filters rows early — it does not change the WHERE clause syntax."><span class="opt-letter">A</span>Rewrites WHERE clauses into HAVING clauses</div>
        <div class="quiz-option" data-correct="true" data-explanation="By moving WHERE filters as early as possible (into leaf scans), the number of rows flowing through expensive join and aggregation nodes is minimized."><span class="opt-letter">B</span>Moves filters as early in the plan as possible, reducing rows entering expensive join nodes</div>
        <div class="quiz-option" data-correct="false" data-explanation="Predicate pushdown is about row reduction, not index creation."><span class="opt-letter">C</span>Automatically creates indexes on filtered columns</div>
        <div class="quiz-option" data-correct="false" data-explanation="Predicate pushdown does not convert joins to subqueries."><span class="opt-letter">D</span>Converts joins to correlated subqueries for performance</div>
      </div>
      <div class="quiz-feedback"></div>
    </div>
  </div>

  <div class="section-label">Interview Q&A</div>
  <div class="qa-section">
    <div class="qa-item">
      <div class="qa-q">What is the Volcano/Iterator model of query execution?<span class="qa-chevron">▾</span></div>
      <div class="qa-a"><div class="qa-a-inner">The Volcano model implements query execution as a tree of operators, each implementing a <code>GetNext()</code> interface. The top-level operator (Result) calls GetNext() on its child, which calls GetNext() on its child, and so on. Data flows upward one tuple at a time. Benefits: memory-efficient (one tuple in flight per operator), composable, simple to implement. Drawback: poor CPU cache utilization due to virtual function calls per tuple. Modern databases (DuckDB, Snowflake) use vectorized execution: process batches of 1024 rows using SIMD, dramatically improving cache efficiency and throughput for OLAP workloads.</div></div>
    </div>
    <div class="qa-item">
      <div class="qa-q">How does the query optimizer handle join ordering for 3+ tables?<span class="qa-chevron">▾</span></div>
      <div class="qa-a"><div class="qa-a-inner">With n tables, there are n!/2 possible left-deep join orderings. For n=4 that is 12; for n=10 that is 1.8M. The optimizer uses dynamic programming (as in System R and PostgreSQL): start with single-table costs, then for each pair, triple, etc. find the cheapest plan using previously computed sub-plans. PostgreSQL uses this up to 8 tables, then switches to a genetic algorithm (GEQO) for larger queries. Heuristics: push filters early to reduce cardinality fast, join on equality predicates before inequality predicates, prefer smaller-to-larger ordering.</div></div>
    </div>
    <div class="qa-item">
      <div class="qa-q">What is predicate pushdown and why is it important?<span class="qa-chevron">▾</span></div>
      <div class="qa-a"><div class="qa-a-inner">Predicate pushdown moves WHERE conditions as early as possible in the query plan — ideally into the table scan. Instead of joining 1M employees x 200 departments then filtering for dept='Engineering', the optimizer pushes the filter into the employees scan first — reducing input to the join from 1M to ~50K rows. The join is 20x smaller. In distributed systems (Spark, BigQuery), predicate pushdown to the storage layer (Parquet column pruning, partition elimination) can avoid reading irrelevant files entirely — reducing I/O by orders of magnitude.</div></div>
    </div>
    <div class="qa-item">
      <div class="qa-q">What is a query plan hint and when should you use one?<span class="qa-chevron">▾</span></div>
      <div class="qa-a"><div class="qa-a-inner">Plan hints let you override the optimizer's choice: force an index (<code>USE INDEX</code> in MySQL), join order, or join type. They should be a last resort — used only when: (1) you have confirmed with EXPLAIN ANALYZE that the optimizer chose a bad plan, (2) you have refreshed statistics and it still makes the wrong choice, (3) you understand exactly why the optimizer is wrong. Hints are brittle: they survive schema changes silently (the hint may force a plan that becomes even worse after a new index is added). Prefer fixing statistics, adding or removing indexes, or rewriting the query. PostgreSQL does not support hints natively (use the <code>pg_hint_plan</code> extension); MySQL does.</div></div>
    </div>
    <div class="qa-item">
      <div class="qa-q">When should you use a materialized view?<span class="qa-chevron">▾</span></div>
      <div class="qa-a"><div class="qa-a-inner">Use a materialized view when: (1) A complex query (multi-table join + aggregation) is run frequently and takes seconds. (2) The underlying data changes infrequently enough that stale reads are acceptable. (3) You need to index the result of a query (not possible with regular views). Refresh strategies: <code>REFRESH MATERIALIZED VIEW CONCURRENTLY</code> in PostgreSQL (does not lock reads), scheduled job, or on-demand. Trade-off: write amplification (every base table update may trigger a refresh) vs read speed. Alternatives: Redis/Memcached cache, denormalized summary tables updated by triggers, or incremental view maintenance (supported in some OLAP systems).</div></div>
    </div>
    <div class="qa-item">
      <div class="qa-q">What is vectorized execution and how does it differ from Volcano?<span class="qa-chevron">▾</span></div>
      <div class="qa-a"><div class="qa-a-inner">Volcano processes one tuple at a time through the operator tree — high function call overhead per row. Vectorized execution (columnar) processes a batch (typically 1024 rows) per GetNext() call. Benefits: (1) CPU SIMD instructions can operate on arrays of values in parallel. (2) Better cache locality — a column of 1024 integers fits in L1/L2 cache. (3) Branch prediction improves for tight loops over arrays. (4) Operator overhead amortized over the batch. Result: 10-100x throughput improvement for scan-heavy OLAP workloads. DuckDB, ClickHouse, Snowflake, and Velox all use vectorized execution. For OLTP workloads with small result sets, the difference is smaller since few rows are processed per query.</div></div>
    </div>
    <div class="qa-item">
      <div class="qa-q">What causes a plan regression and how do you diagnose one?<span class="qa-chevron">▾</span></div>
      <div class="qa-a"><div class="qa-a-inner">A plan regression is when the optimizer switches to a worse execution plan, often after: (1) A new index is added (optimizer may now choose it even when the old plan was better). (2) Data distribution changed significantly (stale statistics cause wrong cardinality estimates). (3) A PostgreSQL or MySQL version upgrade (optimizer behavior changed). (4) Parameter changes (work_mem, enable_hashjoin). Diagnosis: compare EXPLAIN ANALYZE before and after — look for plan node changes (SeqScan vs IndexScan, HashJoin vs NestedLoop) and check estimated vs actual row counts. Fix: run ANALYZE, create extended statistics for correlated columns, or use plan hints as a last resort.</div></div>
    </div>
    <div class="qa-item">
      <div class="qa-q">How does the cost model in PostgreSQL work?<span class="qa-chevron">▾</span></div>
      <div class="qa-a"><div class="qa-a-inner">PostgreSQL's cost model estimates: <code>total_cost = seq_page_cost x pages_read + random_page_cost x random_reads + cpu_tuple_cost x rows + cpu_operator_cost x operations</code>. Key parameters: <code>seq_page_cost = 1.0</code> (baseline), <code>random_page_cost = 4.0</code> (SSDs: lower to 1.1-2.0), <code>cpu_tuple_cost = 0.01</code>. If random_page_cost is too high for your SSD storage, the optimizer will prefer SeqScans over IndexScans even when the index is faster. Tune these constants to match your hardware: <code>SET random_page_cost = 1.1</code> for NVMe. The planner then uses table statistics (pg_statistic) to estimate selectivity at each node.</div></div>
    </div>
  </div>

  <div class="section-label">Further Reading</div>
  <div class="reading-links">
    <a class="reading-link" href="https://www.postgresql.org/docs/current/planner-optimizer.html" target="_blank">PostgreSQL Planner/Optimizer</a>
    <a class="reading-link" href="https://explain.depesz.com/" target="_blank">Explain Depesz (Plan Visualizer)</a>
    <a class="reading-link" href="https://use-the-index-luke.com/sql/explain-plan" target="_blank">Reading EXPLAIN Plans</a>
  </div>

  <div class="topic-nav">
    <a href="06-indexing.html" class="topic-nav-link"><div class="topic-nav-arrow">←</div><div><div class="topic-nav-label">Previous</div><div class="topic-nav-title">Indexing</div></div></a>
    <a href="08-concurrency.html" class="topic-nav-link next"><div class="topic-nav-arrow">→</div><div><div class="topic-nav-label">Next</div><div class="topic-nav-title">Concurrency Control</div></div></a>
  </div>
</div>

<script src="../js/main.js"></script>
<script src="../js/demos.js"></script>
</body>
</html>