A database query requests information computed from stored data. It can filter database tuples, project selected database attributes, combine database relations or aggregate groups. For example, a query can return the count of orders per customer rather than retrieving every order separately. The query specifies a result; a database query plan chooses operations for computing it. Equivalent result specifications can have very different costs under different indexes and data sizes. In SQL, duplicate rows and null values require conventions beyond the simplest mathematical relational algebra.
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 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]
A physical recipe for evaluating a database query, specifying scans, index accesses and implementations of relational joins and duplicate elimination.
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.
An index whose search order determines, or closely follows, the physical placement of the data records. Clustering by one database attribute does not give indexed access by an unrelated database attribute.
Database query results may contain repeated records, with their multiplicities retained.
Database query results contain no repeated database tuples. SQL usually uses bag semantics unless duplicate elimination is requested.
A database query language expresses requests over a database using a defined syntax and semantics. A declarative language describes the desired result while allowing a query optimizer to choose its evaluation. SQL is a prominent example for relational databases; relational algebra supplies operations useful for representing and transforming query plans. Expressive power, treatment of duplicates and null values, and the ability to update data vary by language. A query that is syntactically accepted is not automatically safe or efficient on arbitrary datasets.
Tuple relational calculus describes query answers by predicates over database tuples rather than a sequence of storage operations. A set-builder expression returns tuples satisfying a formula built from relation membership, attribute comparisons, logical connectives and quantifiers. For example,selects employee tuples whose salary exceeds100. A join can be expressed using existentially quantified tuples from two relations and equality of their shared identifying attribute.
The formula needs a safety restriction. Over an unrestricted infinite value universe, a query such as can demand infinitely many absent tuples. Safe tuple relational calculus restricts results to information grounded in the input and explicit constants. Under the usual finite-relation assumptions, its expressive power agrees with relational algebra. This gives a declarative query language while leaving the database system free to choose an efficient query plan.
Safe tuple relational calculus restricts tuple relational calculus so that output values come from the finite input relations or explicit constants, with suitable restrictions on quantification. This prevents an apparently simple database query from demanding an infinite result over an unrestricted value universe. Database query safety is a semantic requirement; merely writing a familiar-looking formula does not ensure it.[ref]
Relational Model slides for Database System Concepts by Abraham Silberschatz and others. slides3.82 and3.86, Safety of Expressions
For a finite unary relation , the database query safely returns . In contrast, over all integers requests every other unary database tuple, an infinite collection. Restricting negation to tuples already drawn from another finite relation gives an expressible finite set difference. Under the usual finite relational model, the safe calculus and relational algebra express the same queries.
Domain relational calculus describes a database query using first-order logic variables ranging over individual attribute values. A formula specifies which output tuples qualify, instead of prescribing a sequence of physical scans or joins. This differs from tuple relational calculus, whose variables range over whole database tuples.
For example, if records an scientific instrument identifier and a measurement value, thenreturns identifiers with some recorded value above five. The existential quantifier binds , while is the output variable. Each returned identifier occurs in a stored database tuple, so extending the ambient domain by unused values cannot change the result.
The apparently simple query behaves differently: with unrestricted quantification, it can return every unused domain value as well as absent recorded values. Database query safety and domain independence of a database query formalize why a finite input must not silently turn such a query into an unbounded enumeration. A finite candidate relation gives the safer intended query .
The requirement that a database query have a finite, appropriately range-restricted answer on finite input. In the usual domain-independent interpretation, extending the ambient value domain with unused values must not change the answer. The absence of a negation symbol alone does not ensure safety.
A database query has the same result when its ambient domain is extended while all input database relations are unchanged.
SQL is a language family for defining and querying relational databases and modifying their contents. A query such as
SELECT customer, COUNT(*) FROM orders GROUP BY customer groups rows by customer and counts each group. A WHERE condition filters rows before grouping; HAVING filters groups afterward. Implementations usually use bag semantics, retaining duplicates unless removed explicitly. Null values also introduce three-valued condition evaluation, so ordinary two-valued logical rewrites need care. Standard features and vendor extensions must be distinguished when portability matters.[ref]https://www.postgresql.org/docs/current/queries-table-expressions.html. PostgreSQL documentation, §7.2, table-expression pipeline
SQL NULL marks a missing or unknown value. Ordinary comparisons involving SQL NULL, including
NULL = NULL, produce the truth value unknown. To test a scalar value for absence, use IS NULL; to compare while treating two missing values alike, use IS NOT DISTINCT FROM.[ref]Comparison Functions and Operators in the PostgreSQL documentation. version 18, section 9.2, null comparisons and predicates
This three-valued logic changes query reasoning.
5 NOT IN (2, NULL) is unknown: five differs from two, but the missing value might be five. A relational selection retains true conditions, so unknown does not pass the filter.[ref]Subquery Expressions in the PostgreSQL documentation. version 18, section 9.24.3, NOT IN with null inputs
Database aggregation has operation-specific rules. On values
2, NULL, 4, COUNT(*) counts three rows, COUNT(value) counts two non-null values and AVG(value) is three. With no input rows, COUNT returns zero while AVG and SUM return SQL NULL. Therefore a blanket rule that all database aggregation ignores SQL NULL is insufficient.[ref]Aggregate Functions in the PostgreSQL documentation. version 18, section 9.21, count variants and empty-input behavior
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 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.
For two database relations with compatible database attributes, retains the database tuples in the first and absent from the second.
Combines database tuples satisfying a matching condition. A natural join uses equality of all shared database attribute names.
A natural join combines two database relations by equating every identically named attribute and retaining one copy of each common attribute. If
people(id,name) contains (7,Ada) and scores(id,mark) contains (7,90), their natural join contains (7,Ada,90). With no common names it becomes a Cartesian product. Matching several common columns requires all their equalities, so adding a same-named column can silently change the result. An explicit join condition is often clearer when schemas evolve. In SQL, duplicates and null values follow the implementation's join semantics.[ref]https://www.postgresql.org/docs/current/queries-table-expressions.html. §7.2.1.1, joined tables and NATURAL JOIN
Retains the database tuples satisfying a condition.
Articles by others on the same topic
There are currently no matching articles.