Hash-Based Two-Pass Algorithms in Database Systems

csce 608 database systems n.w
1 / 67
Embed
Share

Explore the concept of hash-based two-pass algorithms in database systems, focusing on efficient relational algebraic operations, implementation techniques, and general frameworks to handle large relations. Learn about breaking relations into smaller pieces, organizing them in memory, and applying operations using hash buckets. Discover the phases and strategies involved in hash-based two-pass algorithms for processing large datasets.

  • Database Systems
  • Hash Algorithms
  • Two-Pass
  • Relational Algebra
  • Efficiency
rayaanacharya
rnah Follow

Uploaded on | 1 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. CSCE-608 Database Systems Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 33: On hash-based 2-pass algorithms

  2. in tables (relations) lock table DDL language DDL complier database administrator concurrency control file logging & recovery manager transaction manager Efficient Algorithms for Relational algebriac operations index/file manager buffer manager DML (query) language query execution engine database programmer DML complier main memory buffers secondary storage (disks) DBMS

  3. Algorithms Implementing Relational Algebraic Operations Projection and selection , Set/bag operations US, S, S, UB, B, B Join operations , , C Extended operations , , , table-scan 3

  4. Algorithms Implementing Relational Algebraic Operations Quick Review Operations requiring almost no space: , , UB, table-scan Nested-loop Algorithms For binary operations: US, S, S, Memory: M 2 One-pass Algorithms: , , , US, S, S, B, B, Unary: Memory: M B(R) Cost: B(R) , , , , C C Memory: M = 2 Cost: (R), (R), table-scan(R): B(R) Cost: B(R)*B(S)/M + B(R) Binary: Memory: M B(Rsmall) Cost: B(Rsmall) + B(Rlarge) UB(R, S): B(R) + B(S) 4 , , US, S, S, UB, B, B, , , , table-scan, , , C

  5. Two-pass algorithms Condition: large relations that cannot fit into the main memory M, but not extremely large. Basic Ideas: 1. Break relations into smaller pieces that fit in the main memory, make them more organized, and store them back to disk; 2. Apply operation based on merging the blocks from the smaller and more organized pieces. Two main techniques: 1. Sort-based; 2. Hash-based. 5 5 , , US, S, S, UB, B, B, , , , table-scan, , , C

  6. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. R 6 6 , , US, S, S, UB, B, B, , , , table-scan, , , C

  7. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Unary operations (R), (R), (R) main memory R 7 7 , , US, S, S, UB, B, B, , , , table-scan, , , C

  8. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Unary operations (R), (R), (R) main memory R Phase I 8 8 , , US, S, S, UB, B, B, , , , table-scan, , , C

  9. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Unary operations (R), (R), (R) main memory Bucket 1 Bucket 2 R Phase I Bucket M 9 9 , , US, S, S, UB, B, B, , , , table-scan, , , C

  10. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Unary operations (R), (R), (R) main memory Bucket 1 Bucket 2 R End of phase I Bucket M 10 10 , , US, S, S, UB, B, B, , , , table-scan, , , C

  11. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Unary operations (R), (R), (R) main memory Bucket 1 Bucket 2 R One bucket per time Phase II Bucket M 11 11 , , US, S, S, UB, B, B, , , , table-scan, , , C

  12. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Unary operations (R), (R), (R) Assumed condition: M is large enough to hold an entire bucket Summary: Memory: M B(R) Cost: 3B(R) main memory Bucket 1 Bucket 2 R One bucket per time R Phase II Bucket M Assume a good hash function 12 12 , , US, S, S, UB, B, B, , , , table-scan, , , C

  13. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, , C , main memory R R S 13 13 , , US, S, S, UB, B, B, , , , table-scan, , , C

  14. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, , C , main memory R Phase I S 14 14 , , US, S, S, UB, B, B, , , , table-scan, , , C

  15. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, , C , main memory Bucket 1 Bucket 2 R Bucket M Phase I S 15 15 , , US, S, S, UB, B, B, , , , table-scan, , , C

  16. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, , C , main memory Bucket 1 Bucket 2 R Bucket M Phase I Bucket 1 Bucket 2 S Bucket M 16 16 , , US, S, S, UB, B, B, , , , table-scan, , , C

  17. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, , C , main memory Bucket 1 Bucket 2 R End of phase I Bucket M Bucket 2 S Bucket 1 Bucket M 17 17 , , US, S, S, UB, B, B, , , , table-scan, , , C

  18. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, , C , main memory Bucket 1 Bucket 2 R Bucket M Phase II Bucket 2 S Bucket 1 Bucket M 18 18 , , US, S, S, UB, B, B, , , , table-scan, , , C

  19. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, , C , main memory Bucket 1 Bucket 2 R Apply the one-pass algorithm if the smaller bucket can fit M Bucket M Phase II Bucket 2 S Bucket 1 Bucket M 19 19 , , US, S, S, UB, B, B, , , , table-scan, , , C

  20. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, , C , main memory Bucket 2 R Bucket 1 Apply the one-pass algorithm if the smaller bucket can fit M Bucket M Phase II Bucket 1 Bucket 2 S Bucket M 20 20 , , US, S, S, UB, B, B, , , , table-scan, , , C

  21. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, , C , Assumed condition: M is large enough to hold the smaller bucket main memory Bucket 2 R Bucket 1 Bucket M Phase II Bucket 1 Bucket 2 S Bucket M 21 21 , , US, S, S, UB, B, B, , , , table-scan, , , C

  22. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, , C , Assumed condition: M is large enough to hold the smaller bucket main memory Bucket 2 R Bucket 1 Bucket M Hash-based algorithm does not work for and C Phase II Bucket 1 Bucket 2 S Bucket M 22 22 , , US, S, S, UB, B, B, , , , table-scan, , , C

  23. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket main memory Bucket 2 R Bucket 1 Bucket M Phase II Bucket 1 Bucket 2 S Bucket M 23 23 , , US, S, S, UB, B, B, , , , table-scan, , , C

  24. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket RUS S \\ the same work for S, S, B, B main memory FOR each bucket index i DO call the one-pass algorithm on the Ri-bucket and Si-bucket Bucket 2 R Bucket 1 Bucket M Phase II Bucket 1 Bucket 2 S Bucket M 24 24 , , US, S, S, UB, B, B, , , , table-scan, , , C

  25. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket R \\ hash based on join attributes S main memory FOR each bucket index i DO call the one-pass algorithm on the Ri-bucket and Si-bucket Bucket 2 R Bucket 1 Bucket M Phase II Bucket 1 Bucket 2 S Bucket M 25 25 , , US, S, S, UB, B, B, , , , table-scan, , , C

  26. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket Summary: main memory Memory: M B(Rsmall) Cost: 3(B(R) + B(S)) Bucket 2 R Bucket 1 Bucket M Phase II Bucket 1 Bucket 2 S Bucket M 26 26 , , US, S, S, UB, B, B, , , , table-scan, , , C

  27. Two-pass hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket Summary: Comments: 1. Memory use is better than sort-based; 2. The output is not sorted; main memory Memory: M B(Rsmall) Cost: 3(B(R) + B(S)) Bucket 2 R Bucket 1 Bucket M 3. Requires a good hash function. Phase II Bucket 1 Bucket 2 S Bucket M 27 27 , , US, S, S, UB, B, B, , , , table-scan, , , C

  28. Hybrid hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket A trick to save some disk I/O s main memory R S 28 28 , , US, S, S, UB, B, B, , , , table-scan, , , C

  29. Hybrid hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket A trick to save some disk I/O s 1. Use fewer buckets to leave some free M space; main memory R Phase I S Some free space 29 29 , , US, S, S, UB, B, B, , , , table-scan, , , C

  30. Hybrid hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket A trick to save some disk I/O s 1. Use fewer buckets to leave some free M space; 2. Use the free M space to hold some buckets so they are not written back to disk (so save Disk I/O s); Use it to hold some buckets main memory R Phase I S 30 30 , , US, S, S, UB, B, B, , , , table-scan, , , C

  31. Hybrid hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket M = 5, keep k = 2 buckets in M, only write D = M k = 3 buckets back to disk A trick to save some disk I/O s 1. Use fewer buckets to leave some free M space; 2. Use the free M space to hold some buckets so they are not written back to disk (so save Disk I/O s); S-buckets not written back to disk main memory R Phase I S Bucket 1 Bucket D 31 31 , , US, S, S, UB, B, B, , , , table-scan, , , C

  32. Hybrid hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket M = 5, keep k = 2 buckets in M, only write D = M k = 3 buckets back to disk A trick to save some disk I/O s 1. Use fewer buckets to leave some free M space; 2. Use the free M space to hold some buckets so they are not written back to disk (so save Disk I/O s); S-buckets not written back to disk main memory R Phase I S Bucket 1 Bucket D 32 32 , , US, S, S, UB, B, B, , , , table-scan, , , C

  33. Hybrid hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket M = 5, keep k = 2 buckets in M, only write D = M k = 3 buckets back to disk A trick to save some disk I/O s 1. Use fewer buckets to leave some free M space; 2. Use the free M space to hold some buckets so they are not written back to disk (so save Disk I/O s); 3. Operations on these buckets are performed directly. main memory R Bucket 1 Bucket D Phase I S Bucket 1 Bucket D Directly operate with S-tuples here. 33 33 , , US, S, S, UB, B, B, , , , table-scan, , , C

  34. Hybrid hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket M = 5, keep k = 2 buckets in M, only write D = M k = 3 buckets back to disk A trick to save some disk I/O s 1. Use fewer buckets to leave some free M space; 2. Use the free M space to hold some buckets so they are not written back to disk (so save Disk I/O s); 3. Operations on these buckets are performed directly. main memory R Bucket 1 Bucket D End of phase I S Bucket 1 Bucket D Only D pairs of buckets left. 34 34 , , US, S, S, UB, B, B, , , , table-scan, , , C

  35. Hybrid hash-based algorithms General framework: 1. (Phase 1. making hash buckets) Hash tuples into M buckets (using one block for each bucket); write the buckets back to disk. 2. (Phase 2. bucketwise operation) apply the operation based on buckets. Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket M = 5, keep k = 2 buckets in M, only write D = M k = 3 buckets back to disk A trick to save some disk I/O s 1. Use fewer buckets to leave some free M space; 2. Use the free M space to hold some buckets so they are not written back to disk (so save Disk I/O s); 3. Operations on these buckets are performed directly. main memory R Bucket 1 Bucket D Phase I S Bucket 1 Bucket D So the tuples in these k = 2 buckets save two disk I/O s 35 35 , , US, S, S, UB, B, B, , , , table-scan, , , C

  36. Hybrid hash-based algorithms How many (k) buckets should be left in M? Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket A trick to save some disk I/O s 1. Use fewer buckets to leave some free M space; 2. Use the free M space to hold some buckets so they are not written back to disk (so save Disk I/O s); 3. Operations on these buckets are performed directly. main memory R Bucket 1 Bucket D Phase I S Bucket 1 Bucket D So the tuples in these k = 2 buckets save two disk I/O s 36 36 , , US, S, S, UB, B, B, , , , table-scan, , , C

  37. Hybrid hash-based algorithms How many (k) buckets should be left in M? 1. Does not matter. More critical is the amount of M space used for holding these buckets; Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket A trick to save some disk I/O s 1. Use fewer buckets to leave some free M space; 2. Use the free M space to hold some buckets so they are not written back to disk (so save Disk I/O s); 3. Operations on these buckets are performed directly. main memory R Bucket 1 Bucket D Phase I S Bucket 1 Bucket D So the tuples in these k buckets save two disk I/O s 37 37 , , US, S, S, UB, B, B, , , , table-scan, , , C

  38. Hybrid hash-based algorithms How many (k) buckets should be left in M? 1. Does not matter. More critical is the amount of M space used for holding these buckets; 2. larger k smaller bucket more buckets more bucket blocks in M less M space for holding buckets Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket A trick to save some disk I/O s 1. Use fewer buckets to leave some free M space; 2. Use the free M space to hold some buckets so they are not written back to disk (so save Disk I/O s); 3. Operations on these buckets are performed directly. main memory R Bucket 1 Bucket D Phase I S Bucket 1 Bucket D So the tuples in these k buckets save two disk I/O s 38 38 , , US, S, S, UB, B, B, , , , table-scan, , , C

  39. Hybrid hash-based algorithms How many (k) buckets should be left in M? 1. Does not matter. More critical is the amount of M space used for holding these buckets; 2. larger k smaller bucket more buckets more bucket blocks in M less M space for holding buckets 3. So k should be as small as possible: k = 1 Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket A trick to save some disk I/O s 1. Use fewer buckets to leave some free M space; 2. Use the free M space to hold some buckets so they are not written back to disk (so save Disk I/O s); 3. Operations on these buckets are performed directly. main memory R Bucket 1 Bucket D Phase I S Bucket 1 Bucket D So the tuples in these k buckets save two disk I/O s 39 39 , , US, S, S, UB, B, B, , , , table-scan, , , C

  40. Hybrid hash-based algorithms How many (k) buckets should be left in M? 1. Does not matter. More critical is the amount of M space used for holding these buckets; 2. larger k smaller bucket more buckets more bucket blocks in M less M space for holding buckets 3. So k should be as small as possible: k = 1 Binary operations on two relations R and S: US, S, S, B, B, Assumed condition: M is large enough to hold the smaller bucket A trick to save some disk I/O s 1. Use fewer buckets to leave some free M space; 2. Use the free M space to hold some buckets so they are not written back to disk (so save Disk I/O s); 3. Operations on these buckets are performed directly. main memory R Bucket 1 Bucket D Phase I Bucket 1 S Bucket D The tuples in this bucket save two disk I/O s 40 40 , , US, S, S, UB, B, B, , , , table-scan, , , C

  41. Hybrid hash-based algorithms: an example Hybrid Hash-Based 1. # buckets = M/2; 2. Use M/2 main memory blocks to hold a bucket B0; 3. Operations on bucket B0 are performed directly. 41 41

  42. Hybrid hash-based algorithms: an example Hybrid Hash-Based 1. # buckets = M/2; 2. Use M/2 main memory blocks to hold a bucket B0; 3. Operations on bucket B0 are performed directly. M = 10, #buckets = 5 blocks/bucket = 4 42 42

  43. Hybrid hash-based algorithms: an example Hybrid Hash-Based 1. # buckets = M/2; 2. Use M/2 main memory blocks to hold a bucket B0; 3. Operations on bucket B0 are performed directly. M = 10, #buckets = 5 blocks/bucket = 4 main memory R S 43 43

  44. Hybrid hash-based algorithms: an example Hybrid Hash-Based 1. # buckets = M/2; 2. Use M/2 main memory blocks to hold a bucket B0; 3. Operations on bucket B0 are performed directly. M = 10, #buckets = 5 blocks/bucket = 4 main memory R S 44 44 Phase I

  45. Hybrid hash-based algorithms: an example Hybrid Hash-Based 1. # buckets = M/2; 2. Use M/2 main memory blocks to hold a bucket B0; 3. Operations on bucket B0 are performed directly. M = 10, #buckets = 5 blocks/bucket = 4 main memory R S 45 45 Phase I

  46. Hybrid hash-based algorithms: an example Hybrid Hash-Based 1. # buckets = M/2; 2. Use M/2 main memory blocks to hold a bucket B0; 3. Operations on bucket B0 are performed directly. M = 10, #buckets = 5 blocks/bucket = 4 main memory R S 46 46 Phase I

  47. Hybrid hash-based algorithms: an example Hybrid Hash-Based 1. # buckets = M/2; 2. Use M/2 main memory blocks to hold a bucket B0; 3. Operations on bucket B0 are performed directly. M = 10, #buckets = 5 blocks/bucket = 4 main memory S R Sgray 47 47 Phase I

  48. Hybrid hash-based algorithms: an example Hybrid Hash-Based 1. # buckets = M/2; 2. Use M/2 main memory blocks to hold a bucket B0; 3. Operations on bucket B0 are performed directly. M = 10, #buckets = 5 blocks/bucket = 4 main memory S R Sgray 48 48 Phase I

  49. Hybrid hash-based algorithms: an example Hybrid Hash-Based 1. # buckets = M/2; 2. Use M/2 main memory blocks to hold a bucket B0; 3. Operations on bucket B0 are performed directly. M = 10, #buckets = 5 blocks/bucket = 4 main memory S R Sgray 49 49 Phase I

  50. Hybrid hash-based algorithms: an example Hybrid Hash-Based 1. # buckets = M/2; 2. Use M/2 main memory blocks to hold a bucket B0; 3. Operations on bucket B0 are performed directly. M = 10, #buckets = 5 blocks/bucket = 4 main memory S R Sgray 50 50 Phase I

Related


No related presentations.

More Related Content