Đang tạo bản xem trước...
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 C C D R2 a 10 10 cat a 20 40 dog b 10 15 bat d 30 20 rat • NLJ (conceptually) for each r R1 do for each s R2 do if r.C = s.C then output r,s pair
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 organization R1 R2 S1 S2 R3 R4 S3 S4 ….. • Clustered relation R1 R2 R3 R4 R5 R5 R7 R8 ….. • Clustering index
Clustering Index Tuples with a given value of the search key packed in as few blocks as possible 10 10 35 A index 19 19 19 19 42 37
Examples T(R) = 10,000 B(R) = 200 If R is clustered, then # R tuples per block = 10,000/200 = 50 Let V(R,A) = 40 ➔If I is a clustering index on R.A, then # IOs to access σR.A = “a”(R) = 250/50 = 5 ➔ If I is a non-clustering index on R.A, then # IOs to access σR.A = “a”(R) = 250 ( > B(R))
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
Implementing Tuple-at-a-time Operators • One pass algorithm: – Scan – Process tuples one by one – Write output • Cost = B(R) – Remember: Cost = # IOs, and we ignore the cost to write output
Implementing a Full-Relation Operator, Ex: Sort • Suppose T(R) x tupleSize(R) <= M x |B(R)| • Read R completely into memory • Sort • Write output • Cost = B(R)
Implementing a Full-Relation Operator, Ex: Sort • Suppose R won’t fit within M blocks • Consider a two-pass algorithm for Sort; generalizes to a multi-pass algorithm • Read R into memory in M-sized chunks • Sort each chunk in memory and write out to disk as a sorted sublist • Merge all sorted sublists • Write output
Two-phase Sort: Phase 1 Suppose B(R) = 1000, R is clustered, and M = 100 1 1 96 1 100 2 2 97 101 200 3 3 98 4 4 99 201 300 5 5 100 Memory Sorted Sublists 999 801 900 1000 R 901 1000
Two-phase Sort: Phase 2 100 1 1 1 200 101 2 2 3 3 300 201 4 4 5 5 Sorted Sublists 6 7 8 900 801 9 999 10 1000 1000 901 Memory Sorted R
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Chưa có bình luận nào. Hãy là người đầu tiên!
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!