Build a Query Engine

Because a customer places many orders, and putting the customer's name on every order would write the same name out again and again. Change your name and somebody has to find all of them. Instead each customer gets a number in the id column, and every order carries that number in its cust column. One name, stored once, pointed at from many places.

The price of that tidiness is that a question like "what did people in Galle buy" now needs both tables at once, and matching them up turns out to be the most expensive thing this whole course deals with. Steps 7 and 9 are about almost nothing else.

SQL was designed in the 1970s so that people who were not programmers could ask questions of a database. That is why SELECT name FROM customers WHERE city = 'Galle' reads roughly as you would say it. The words in capitals are keywords: fixed words the language reserves for itself. Everything else is your table and column names, your numbers, and text in single quotes.

The plain-English look is a surface. Underneath, a query is a precise statement about which rows you want, and it says nothing at all about the order the work is done in. That gap is the subject of this course.

To compare two ways of answering a question you need one number for each. This course counts work units. Reading the next row of a table costs 1. Comparing two values costs 1. Jumping straight to one particular row, which Step 6 explains, costs more, and you will get to choose how much more. Putting a row into a lookup table, or looking one up in it, costs 1.

Those weights are a decision, not a law of nature, and a real database makes a similar decision with different numbers. What matters is that every figure printed by this page was produced by running the code and adding up as it went. None of them were typed in by hand.

Because everything that comes next gets much simpler. Without tokens, every later step would have to worry about spaces, about whether SELECTED starts with the word SELECT, and about where a piece of quoted text starts and finishes. With tokens, all of that is settled once and never thought about again.

The same split shows up wherever a machine reads text people wrote. A compiler, the program that turns code a person wrote into instructions a processor runs, starts exactly this way. So does the thing that reads a web page.

A tree here is a way of writing down "this thing contains those things". Each entry is a node. A node can hold other nodes underneath it, which are its children. A node with nothing underneath it is a leaf. Drawn on a page it usually goes downwards, with the whole thing at the top and the small pieces at the bottom, which is why it is called a tree drawn upside down.

In this page a tree is shown as indented lines. A line indented further than the one above it sits inside that line. It is the same shape as a list of folders inside folders.

Because order carries meaning. SELECT name FROM customers and FROM customers SELECT name are made of the same tokens, and only the first is a query. The rules about which token may follow which are called a grammar, and the parser is the grammar turned into a procedure: read the next token, check that it is allowed here, use it, move on.

That is why the parser can say something useful when it fails. It always knows exactly what it was expecting when it stopped. The one in this page reports what it wanted and which character it was standing on.

An operator is one small machine with rows going in and rows coming out. That is the whole idea. It has no opinion about where its rows came from or where they go. Because of that, operators can be stacked in different orders and swapped for other operators that do the same job differently, which is what the next three steps are entirely about.

The test inside a Filter has a name of its own: a predicate. It is any statement about a row that comes out either true or false, such as price > 1000. You will see the word in any real database's own output, so it is worth having.

Rows enter at the bottom, at the Get, and travel upwards. Each operator sits above the one that feeds it. So the top line of the printed plan is the last thing to happen, and the most indented lines at the bottom are the first.

This trips up everybody at first, including people who have used databases for years. It is the order rows move in, not the order the lines are printed in, that matters. Every real database prints its plans this way round, so it is worth getting used to here where the plans are four lines long.

Think of the index at the back of a paper book. The book itself is in page order, which is no help at all if you want the pages about volcanoes. The index is in alphabetical order and each entry names the pages. You find "volcano" quickly because the list is sorted, and then you turn straight to page 212.

A database index works the same way and costs the same things: it takes up space, it has to be kept correct every time a row changes, and it only helps for the column it was built on. An index on city is no use whatever for a question about price.

Logical is the shopping list: milk, bread, apples. Physical is the route: which shop, in what order, walking or on the bus. The list does not change when you take the bus instead, and the shopping is the same when you get home. But one route takes ten minutes and another takes an hour.

The engine is allowed to pick any route it likes, as long as the shopping is identical. That is a very strong promise, and it is what lets a database get faster without anybody rewriting their queries.

The other arrangement is possible: the table could push every row upwards as fast as it can read them. Some engines do work that way, and it is faster when you want all the rows. It has one bad property, though. The bottom of the plan has no idea how many rows the top actually wants, so it cannot stop early. It can produce rows faster than the operator above can absorb them.

Pulling means the demand comes from the top, where the knowledge is. It also means the middle of the plan holds almost nothing: at any moment there is roughly one row inside each operator, not a whole table.

Sort is the obvious one. It cannot hand up the smallest row until it has seen every row, because the very last row it reads might be the smallest. So Sort drains everything below it into memory first, then hands rows up one at a time. An operator that has to do this is called blocking.

A hash join is half blocking. It has to load one whole side into its lookup structure before it can check anything against it, but the other side still streams through row by row. That difference in shape is exactly why a hash join and a merge join behave so differently in Step 7.

Count the other way. One halving can settle between 2 things. Two halvings can settle among 4. Three among 8, then 16, 32, 64, 128, 256. That is eight steps to pick one out of 256, so 200 is comfortably inside eight.

The useful part is how slowly that grows. A thousand entries need ten steps. A million need twenty. A thousand million need thirty. Multiplying the table by a thousand adds ten steps, not a thousand steps, which is why sorted things are worth the trouble of keeping sorted.

Storage does not hand out one row at a time. It hands out a block of neighbouring rows at once, because fetching one and fetching fifty next to it takes almost the same time. A sequential scan gets the next forty-nine rows for nothing. A jump to an unrelated row throws that away and pays the full fetch again.

How much more depends on the machine. A spinning disk has to physically move an arm, and a jump might cost hundreds of times a neighbour. A solid-state drive is far kinder, and memory kinder still. This is a real setting in real databases, with a real name, and getting it wrong is a real cause of bad plans.

Three reasons, and all of them are about writing rather than reading. Every index is another copy of a column, so it takes space. Every row you add has to be added to every index, in the right sorted place, so writing gets slower with each index you create. And an index that no query uses still costs both of those every single day.

Real advice, and it is safe to skip this: create the index, measure the query, and delete the index if the plan did not change. Databases will tell you which indexes are never used, and on most systems that have been running a few years, several of them are not.

A hash is a calculation that turns any value into a number in a fixed range. Turn the word "Galle" into 47, always the same 47. Then keep an array of numbered pigeonholes, and file the row in pigeonhole 47. To find it later, hash "Galle" again, get 47 again, and look in that one pigeonhole. You never searched.

Two different values sometimes land in the same pigeonhole, which is why each one holds a small list rather than a single row. The cost is memory: the whole filed-away side has to fit somewhere. A real database that runs out of room for it has to spill onto disk, and a hash join that spills is a well known way for a query to fall off a cliff.

Most of what a merge join costs is the sorting. If both sides happen to arrive sorted on the join key already, that cost disappears and the join is one walk down two lists. Rows arriving from an index are already in that column's order, so a plan that reads both sides through indexes on the join columns gets its merge join at a discount.

There is a second prize. The rows come out of a merge join in sorted order, so if the query also has an ORDER BY on the join key, the Sort above it can be deleted. Real engines track this carefully, and it is one of the few places where the cheapest join is not the cheapest plan.

An estimate is a number worked out without measuring the thing itself. The engine is not being lazy: measuring would cost more than the query. What it needs is not the exact count but a figure good enough to tell 4 apart from 4,000, because that is the scale at which the decisions change.

This is worth being clear about, because it is the reason for everything in Step 9. The engine is not choosing the best plan. It is choosing the plan that looks best given a summary that was true at some point in the past.

A histogram is a tally. Go through the column once, and for each value keep a count of how many rows had it. The result is a small table: pen 1,200, mug 800, chair 900, and so on. It is far smaller than the column it describes, so it can be kept in memory and read instantly.

When a column has too many different values for that, such as a price or a date, the counts are grouped into ranges instead: how many rows between 0 and 100, how many between 100 and 200. Same idea, coarser answer. Either way it is one pass over the table, done occasionally, not per query.

On a table of a thousand million rows, one pass to build a histogram is itself an expensive operation. So real systems sample: read a few tens of thousands of rows chosen at random, count those, and scale the counts up. The answer is approximate, and for common values it is approximate in a harmless way.

It is less harmless for rare ones. A value held by 20 rows out of a thousand million may not appear in the sample at all, and then the summary says it does not exist. Safe to skip, but remember it: it is the same failure the next step is built on.

Because running the filter to find out how many rows pass is most of the work of the query. If planning cost as much as executing, planning would not be worth doing, and every query would pay it twice.

Some engines do a limited version of this anyway. They start executing, notice partway through that the row count is nothing like the estimate, throw the plan away and start again with a better one. That is real and it is called adaptive execution, and it is the exception rather than the rule because throwing away work is its own cost.

An engine that meets two tests at once usually multiplies their selectivities: if one keeps a tenth and the other keeps a fifth, together they keep a fiftieth. That is correct only when the two columns have nothing to do with each other. Ask for city = 'Kandy' and postcode = '20000' and the second test throws away nothing at all, because every Kandy address already has that postcode. The engine estimates a fiftieth and gets a tenth.

This is called correlation, and it is harder to fix than a stale summary, because it needs statistics about pairs of columns rather than single ones. Most systems can be told to collect those for a specific pair, and almost nobody does until a query goes wrong.

Columns, not just rows. If a query only ever uses name and item, there is no reason to carry price, qty and everything else through the join and the sort. Moving the Project down so unwanted columns are dropped at the earliest possible moment is called projection pushdown.

It saves less than filtering does in this engine, because a row here is a small object in memory. In a real system reading from storage it can matter enormously, and in the column-oriented databases built for reporting it is the single biggest saving there is: a query that names three columns out of two hundred reads three columns' worth of storage.

Two cases. If the test reads columns from both tables, such as orders.price > customers.credit, there is nowhere below the join where both are available, so it has to stay above. And with the kinds of join that keep unmatched rows, filling the missing side with blanks, moving a test across the join changes which rows survive, so the rewrite is not allowed even though it looks harmless.

Safe to skip, but this is a good example of what an engine's rewriting rules actually are: a list of transformations, each with a precise condition under which it does not change the answer. Getting one of those conditions wrong is how a database returns the wrong result, which is far worse than returning the right one slowly.

GROUP BY city makes one group per city. COUNT, SUM and AVG reduce each group to one row. HAVING filters groups after aggregation; WHERE filters input rows before it.

A window function also works across related rows, but it keeps every input row. It can number rows, compare with a previous row or compute a running total without collapsing the result.

Generate tiny tables containing duplicates, NULLs and empty inputs. Run the plan before and after the rewrite, then compare complete result bags. Shrink a failing case until the missing guard is obvious.

This catches correctness faults that performance benchmarks cannot see. Keep the reduced case as a permanent regression test.

Two plans for the same table subset can differ in output order or partitioning. A dearer subplan may avoid a later sort or network shuffle, so dynamic programming sometimes keeps more than one winner per subset.

The state key must include physical properties the parent can use. Keeping every property would make the search large again, so engines keep only useful alternatives.

A plan can contain several memory-hungry operators and several workers. Many copies may run concurrently. Multiply before setting a global limit.

Admission control can delay new heavy queries until memory is available. That queue is often safer than letting the operating system kill an arbitrary process.

A columnar executor can carry row positions through filters and fetch wide output values only for survivors. This is called late materialisation. It avoids moving unused strings through every operator.

The opposite can win when nearly every row survives or random fetches are expensive. Selectivity and storage layout decide the boundary.

If LIMIT has enough rows or one worker fails, upstream tasks must stop, close network streams and release temporary files. Otherwise a cancelled query keeps consuming the cluster.

Distributed plans therefore carry query ids, deadlines and cancellation signals alongside data batches. Cleanup is part of the operator contract.

Schema changes, dropped indexes and relevant setting changes can make an old plan invalid. Statistics or parameter distributions can make it valid but poor.

Track dependencies from a cached plan to catalog objects. Replan on structural changes, and use measured execution evidence to decide when a merely poor plan should be replaced.

A read-only subplan can often be restarted or repartitioned. An update, external function or sequence call may have already changed state. The executor cannot replay it blindly.

Mark safe adaptive boundaries in the plan. Above a side-effecting operator, prefer choices that preserve exactly-once effects or do not require replay.

PostgreSQL documents EXPLAIN, extended statistics, JIT and generic and custom prepared plans. Engine-specific behaviour belongs in the matching version's manual.

Learned estimators are an active research area. Treat a paper's benchmark as evidence for that workload, not a universal replacement claim. Reproduce the comparison on your distributions and failure cases.

Put the word EXPLAIN in front of any query and most databases print the plan instead of running it. The output is the same shape as the trees in this course: indented operators, read from the bottom up, each with an estimated row count. Add the word ANALYZE as well and it runs the query and prints the real counts beside the estimates.

That side-by-side pair is the single most useful thing in database work. A line where the estimate says 1 and the reality says 900,000 is Step 9 happening to you, and it points at the fix without any guessing.

In order. Print the plan and find the operator handing up the most rows, because that is where the cost is. Compare each estimate against the real count and find the first line where they diverge badly, because everything above it was planned on a wrong number. If they diverge, refresh the statistics before touching anything else.

Only then consider an index, and only on a column whose test throws most of the table away. Adding an index is the first thing most people reach for and it is rarely the answer, because an index cannot help a plan whose problem is that it thought one row was coming and got a million.