Relational Query Optimization & Execution: Relational Algebra Equivalence, Cost-Based Join Optimization (Nested Loop vs Hash Join vs Sort-Merge), and Index Scan Selectivity

The simulated benchmark models an in-memory hash join with uniform key distributions and negligible bucket collision chaining, resulting in deterministic operation scaling T(N) = 2N. In physical enterprise database engines (PostgreSQL, MySQL InnoDB, Oracle, Microsoft SQL Server), execution latency is heavily modulated by: (1) external memory Grace hash partitioning and multi-pass disk I/O when relation size exceeds buffer pool capacity M; (2) data skew and duplicate join keys ('heavy hitters') creating unbalanced hash chains; (3) NUMA memory bus node remote access penalties on multi-socket database servers; (4) parallel query execution thread synchronization and exchange operator (Tuple Mover / Gather) serialization overhead; and (5) cardinality estimation errors propagating exponentially through multi-join query trees. In an in-memory equi-join between two relations R and S of identical cardinality |R| = |S| = N, the classical Hash Join algorithm operates in two sequential phases: (1) Build Phase: The optimizer designates relation R as the build input. For each of the N tuples in R, the engine evaluates the hash function on the join key h(t_R.k) and inserts the tuple into the corresponding hash bucket, performing exactly N insertion operations. (2) Probe Phase: The engine scans relation S as the probe input. For each of the N tuples in S, it computes the hash value h(t_S.k), accesses the hash bucket, and evaluates the join predicate against matching candidate keys. Under uniform hash distribution and unique primary-foreign key relationships, each probe executes exactly 1 tuple comparison, totaling N probe comparisons. The total operation count is strictly T(N) = N (build insertions) + N (probe comparisons) = 2.0000 · N operations. Ordinary least-squares linear regression against tuple cardinality N yields an empirical scaling multiplier of k_join = 2.0000 comparisons/tuple with baseline intercept T_0 = 0.0000 operations and correlation coefficient R² = 1.00000. In contrast, Nested Loop Join scales quadratically as C_nlj(N) = N², Block Nested Loop Join incurs B(R) + ⌈B(R)/(B-2)⌉ · B(S) disk block transfers, and Sort-Merge Join incurs 2 B(R) log_{B-1}(B(R)/B) + 2 B(S) log_{B-1}(B(S)/B) + B(R) + B(S) block I/Os.