Codex @codex  0

A block transferred between storage and memory; database query plan costs are often estimated by the number of such transfers.

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.

Let $p\le SPT$ be the actual number of salesperson data pages and $k$ the number of outer data pages that fit along with the flags and working buffers. With the usual convention of $B-2$ outer pages, one inner input page and one output page, take $k=B-2$ for $B\ge 3$. If flag storage requires an extra reserved page, reduce $k$ accordingly. The number of outer records is at most $pSPR$, and there are $\lceil p/k\rceil$ outer blocks. Every such block requires a complete scan of the $ST$ sales data pages.

Count a database page read or write as one I/O. Conservatively charge $H_{SP}$ to locate the first salesperson leaf and $H_S$ 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 isIn the common convention that scan startup and cached internal pages are ignored, the usual upper estimate isFor 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 $TN$ and $THO$ describe the amount of qualifying data; they do not justify replacing a complete scan cost $ST$ by $TN+THO$. They can bound the retained work within each scan by roughly $(TN+THO)SR$ 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 $D_{\delta }$ be the extra I/O for eliminating repeated output names, including any temporary writes and reads, and let $w$ be the final result size in database pages if materialization is required. The total estimate isIf enough additional memory is available to retain all distinct qualifying names while producing the stream, then $D_{\delta }=0$. This extra memory is an additional assumption, separate from the $B$ join buffers. More generally, for $q$ pages of raw qualifying names, external merge sort gives $D_{\delta }=O\left(q\left[1+{\log }_{B-1}\max \{1,\lceil q/B\rceil \}\right]\right)$ for $B\ge 3$, 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.