Database Created 2026-10-31 Updated 2026-11-05
A database is an organized collection of data maintained for queries and updates. A database management system manages that collection, enforcing access rules and database integrity constraints. A relational database represents it through database relations, rather than exposing only an arbitrary collection of bytes in files.
For example, a laboratory can store biological sample identifiers, measurement values and scientific instrument identifiers as database tuples. A database query can select measurements above a threshold and join them to scientific instrument records. A foreign key can require every recorded scientific instrument identifier to name an existing scientific instrument. This makes the connection a maintained rule rather than a convention that every application must remember.
The logical relational schema and actual storage are distinct. A database query plan may use an index or scan database pages while returning the same specified result. Database transactions coordinate related updates, and database integrity constraints restrict the permitted states. PostgreSQL's documentation gives a concrete implementation in which named tables contain rows with named, typed columns and databases group tables.[ref]
Database page 2026-10-31
A block transferred between storage and memory; database query plan costs are often estimated by the number of such transfers.
Database query Created 2026-10-31 Updated 2026-11-05
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]
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 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]
A simple valid database query plan uses a block nested-loop join with the salesperson records on the outside, checking both sale conditions during the same inner scan. It avoids materializing the potentially much larger set of matching sale pairs.
  • Read a block of salesperson records. Retain each empid, its name, and two initially false flags, one for each target price.
  • Scan all of Sales. Apply relational selection to disregard other prices. For each retained sale, match salespersonid against the identifiers in the current outer block, and set the corresponding price flag. Several matching sales only set the same flag again.
  • After the inner scan, output the names of outer records with both flags true. Repeat for the next outer block, then eliminate repeated names to implement set semantics.
Let be the actual number of salesperson data pages and the number of outer data pages that fit along with the flags and working buffers. With the usual convention of outer pages, one inner input page and one output page, take for . If flag storage requires an extra reserved page, reduce accordingly. The number of outer records is at most , and there are outer blocks. Every such block requires a complete scan of the sales data pages.
Count a database page read or write as one I/O. Conservatively charge to locate the first salesperson leaf and to locate the start of each inner scan; this permits a small double charge if a definition of height includes a data leaf. The estimated read cost is
In the common convention that scan startup and cached internal pages are ignored, the usual upper estimate is
For an empty outer input there are no inner scans. This database query plan requires neither a sorted sale input nor a price index. In particular, the clustered database index on invoiceno cannot locate records by price. The quantities and describe the amount of qualifying data; they do not justify replacing a complete scan cost by . They can bound the retained work within each scan by roughly sale records, if those page counts describe packed qualifying records. Comparison cost against the outer block is CPU work rather than additional I/O.
Finally let be the extra I/O for eliminating repeated output names, including any temporary writes and reads, and let be the final result size in database pages if materialization is required. The total estimate is
If enough additional memory is available to retain all distinct qualifying names while producing the stream, then . This extra memory is an additional assumption, separate from the join buffers. More generally, for pages of raw qualifying names, external merge sort gives for , including spooling. Names can be deduplicated during the merges. Counting this work matters because a database primary key on empid does not make names unique. No claim of optimality is needed for this database query plan.
Tuple relational calculus 2026-11-05
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.