Data-Intensive Computing Systems Query Execution (Sort and Join operators) Shivnath Babu Roadmap A simple operator: Nested Loop Join Preliminaries Cost model Clustering Operator classes Operator implementation (with examples from joins) Scan-based Sort-based Using existing indexes Hash-based Buffer Management Parallel Processing Nested Loop Join (NLJ) R1 B a a b d C 10 20 10 30 C 10 40 15 20 D cat dog bat rat NLJ (conceptually) for each r  R1 do for each s  R2 do if r.C = s.C then output r,s pair R2 Nested Loop Join (contd.) Tuple-based Block-based Asymmetric Implementing Operators Basic algorithm Scan-based (e.g., NLJ) Sort-based Using existing indexes Hash-based (building an index on the fly) Memory management Tradeoff between memory and #IOs Parallel processing Roadmap A simple operator: Nested Loop Join Preliminaries Cost model Clustering Operator classes Operator implementation (with examples from joins) Scan-based Sort-based Using existing indexes Hash-based Buffer Management Parallel Processing Operator Cost Model Simplest: Count # of disk blocks read and written during operator execution Extends to query plans Cost of query plan = Sum of operator costs Caution: Ignoring CPU costs Assumptions Single-processor-single-disk machine Will consider parallelism later Ignore cost of writing out result Output size is independent of operator implementation Ignore # accesses to index blocks Parameters used in Cost Model B(R) = # blocks storing R tuples T(R) = # tuples in R V(R,A) = # distinct values of attr A in R M = # memory blocks available Roadmap A simple operator: Nested Loop Join Preliminaries Cost model Clustering Operator classes Operator implementation (with examples from joins) Scan-based Sort-based Using existing indexes Hash-based Buffer Management Parallel Processing Notions of clustering Clustered file o