Database query plan

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 $b$ outer pages per block, $p$ outer pages and $q$ inner pages, its data-read cost is $p+\lceil p/b\rceil q$, 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.