Block nested-loop join 2026-10-31
A relational join implementation that retains a block of outer records in memory while scanning the inner input. With outer pages per block, outer pages and inner pages, its data-read cost is , before temporary output costs.
Database query optimization chooses a database query plan for a database query by comparing ways to obtain the required result. The choice includes the order of relational joins, use of a database index, and the algorithms implementing those relational joins. A cost model estimates work from quantities such as input sizes and storage accesses. The selected plan minimizes estimated cost among considered alternatives; this need not be the fastest possible plan in reality.[ref]
Consider a relational join of one million orders with customers, followed by a condition selecting ten customers. Applying the customer condition first can greatly shrink a join input. If a suitable database index locates those customers' orders, the engine may avoid scanning all orders. If almost all customers qualify, a sequential scan can instead be cheaper than many scattered index accesses. These are alternative ways of computing the same answer, not different meanings of the query.
Join order also matters with three or more inputs: an early join that creates a huge intermediate result can dominate the total work. Exhaustive search itself becomes expensive as the number of inputs grows. PostgreSQL therefore switches to a heuristic search above a configurable threshold. Inaccurate size estimates can favor a poor plan even when the search algorithm correctly minimizes its cost model.[ref]
Database query plan Created 2026-10-31 Updated 2026-11-05
A physical recipe for evaluating a database query, specifying scans, index accesses and implementations of relational joins and duplicate elimination.
Database query processing 2026-11-05
Database query processing is the sequence that turns a database query into returned results. In a typical SQL system, it includes parsing the text, checking names and types, rewriting the query when appropriate, database query optimization, and executing the chosen database query plan. Planning chooses operations; execution actually performs storage accesses, relational joins, filtering and aggregation.[ref]
For a request for each customer's total order value, the engine might scan orders, group their database tuples by customer identifier, sum the values and return one result per customer. An alternative plan can first restrict the orders using a database index. The result specification alone does not prescribe which access method performs the work.
A query against a stored database view illustrates why processing has more than a text-to-loop step. PostgreSQL can rewrite the reference into a query on the underlying tables before planning. The executor then walks the resulting plan and obtains rows from its operations. The distinction is useful when diagnosing a slow query: excessive planning work, a poor plan, and unexpectedly expensive execution are different causes even if the same statement triggered them.[ref]
Dependency-preserving decomposition Created 2026-10-31 Updated 2026-11-05
A decomposition in which the database integrity constraints can be enforced using constraints on individual component database relations, without computing their relational join.
An arithmetic mean is database aggregation, which is outside classical relational algebra. Use SQL:
SELECT AVG(s.price) AS average_sale_price
FROM Sales AS s
JOIN Car AS c ON c.serialnumber = s.serialnumber
WHERE c.make = 'Saab';
For non-null prices of qualifying sales, the result is
Each sale contributes once, even when a car was sold on several invoices. Do not use DISTINCT inside AVG: two different sales at the same price must both count. The car's database primary key makes the relational join match each sale to exactly one car, so the relational join introduces no extra weighting.
If there are no qualifying non-null prices, AVG returns SQL NULL. It ignores null prices if the implementation permits them; it does not replace an absent arithmetic mean with zero.[ref]
First use relational selection to keep the Saab cars, then a natural join to find their sales, and finally a relational join to identify the corresponding salespeople. A relational projection gives
The foreign keys ensure that every sale has the referenced car and salesperson. Several qualifying sales by the same person produce just one occurrence of their name under set semantics. Two distinct people with the same name also yield that name only once: this is the requested relational projection onto names.
Find the salesperson identifiers satisfying each price condition using relational selection and relational projection:
Intersect these identifier sets, relational join the result to the salesperson records, and apply relational projection to names:
If intersection is not a primitive of the chosen relational algebra, use with relational difference. There is no need to access Car: the foreign key already ensures that every sale refers to a car.
Intersecting names instead of identifiers is wrong. Two different salespeople called Alex, one making only sales and the other only sales, would make Alex appear in both name sets although neither person satisfies the condition. Nor can one sale satisfy both price tests: the two distinct prices require distinct sale records.
Relational division Created 2026-10-31 Updated 2026-11-05
Relational division expresses an all-required-matches query. Let be a database relation, the required values and an explicit candidate database relation. The desired result is
It can be constructed using Cartesian product, relational projection and relational difference:
The inner relational difference contains missing required pairs. Its relational projection identifies failing candidates; removing them from proves the formula.
For example, can record scientific instrument/test pairs and the required tests. An scientific instrument with both pairs passes; one with only the heat pair does not. This is a universal quantifier requirement, unlike an ordinary relational join asking for some match.
When is empty, vacuous truth gives . Choosing is conventional but cannot recover candidates absent from ; use an independently stored scientific instrument database relation if those candidates must be included. Stating the candidate universe makes this edge case unambiguous.