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 2026-11-05
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]
Planner and Optimizer in the PostgreSQL documentation. Section 51.5, opening paragraphs and Generating Possible Plans
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]
Planner and Optimizer in the PostgreSQL documentation. Section 51.5.1, scan alternatives, join sequences and heuristic search
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.
Past exam of the computer science course of the University of Oxford 2015 Databases 1 a iii Solution 2026-10-31
An arithmetic mean is database aggregation, which is outside classical relational algebra. Use SQL:For non-null prices of qualifying sales, the result isEach sale contributes once, even when a car was sold on several invoices. Do not use
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';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]Aggregate Functions in the PostgreSQL documentation. Section 9.21,
avg and the paragraph on aggregates with no selected rows Past exam of the computer science course of the University of Oxford 2015 Databases 1 a i Solution 2026-10-31
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 givesThe 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.
Past exam of the computer science course of the University of Oxford 2015 Databases 2 a Solution 2026-10-31
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 algebra 2026-10-31
An algebra of operations on database relations. Classical relational algebra has relational selection, relational projection, relational join, Cartesian product, union and relational difference; database aggregation requires an extension.
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 isIt 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.