High-Performance Parallel Database Processing and Grid Databases

David Taniar, PhD, lectures in information technology at Monash University, Australia. Dr. Taniar has published extensively in the field of high- performance parallel databases and is the Editor in Chief of the International Journal of Data Warehousing and Mining. Clement H. C. Leung, PhD, is Foundation Chair in Computer Science at Victoria University, Australia. Dr. Leung previously held the Established Chair in Computer Science at the University of London.Wenny Rahayu, PhD, is Associate Professor at La Trobe University, Australia, and actively works in the areas of database design and implementation, covering object-relational databases and Web databases.Sushant Goel, PhD, is a software consultant and holds a PhD in computer systems engineering from RMIT University, Australia. His research interests are in grid transaction management and software development processes, such as agile computing.

• Preface xvPart I Introduction1. Introduction 31.1. A Brief Overview: Parallel Databases and Grid Databases 41.2. Parallel Query Processing: Motivations 51.3. Parallel Query Processing: Objectives 71.3.1. Speed Up 71.3.2. Scale Up 81.3.3. Parallel Obstacles 101.4. Forms of Parallelism 121.4.1. Interquery Parallelism 131.4.2. Intraquery Parallelism 141.4.3. Intraoperation Parallelism 151.4.4. Interoperation Parallelism 151.4.5. Mixed Parallelism—A More Practical Solution 181.5. Parallel Database Architectures 191.5.1. Shared-Memory and Shared-Disk Architectures 201.5.2. Shared-Nothing Architecture 221.5.3. Shared-Something Architecture 231.5.4. Interconnection Networks 241.6. Grid Database Architecture 261.7. Structure of this Book 291.8. Summary 301.9. Bibliographical Notes 301.10. Exercises 312. Analytical Models 332.1. Cost Models 332.2. Cost Notations 342.2.1. Data Parameters 342.2.2. Systems Parameters 362.2.3. Query Parameters 372.2.4. Time Unit Costs 372.2.5. Communication Costs 382.3. Skew Model 392.4. Basic Operations in Parallel Databases 432.4.1. Disk Operations 442.4.2. Main Memory Operations 452.4.3. Data Computation and Data Distribution 452.5. Summary 472.6. Bibliographical Notes 472.7. Exercises 47Part II Basic Query Parallelism3. Parallel Search 513.1. Search Queries 513.1.1. Exact-Match Search 523.1.2. Range Search Query 533.1.3. Multiattribute Search Query 543.2. Data Partitioning 543.2.1. Basic Data Partitioning 553.2.2. Complex Data Partitioning 603.3. Search Algorithms 693.3.1. Serial Search Algorithms 693.3.2. Parallel Search Algorithms 733.4. Summary 743.5. Bibliographical Notes 753.6. Exercises 754. Parallel Sort and GroupBy 774.1. Sorting, Duplicate Removal, and Aggregate Queries 784.1.1. Sorting and Duplicate Removal 784.1.2. Scalar Aggregate 794.1.3. GroupBy 804.2. Serial External Sorting Method 804.3. Algorithms for Parallel External Sort 834.3.1. Parallel Merge-All Sort 834.3.2. Parallel Binary-Merge Sort 854.3.3. Parallel Redistribution Binary-Merge Sort 864.3.4. Parallel Redistribution Merge-All Sort 884.3.5. Parallel Partitioned Sort 904.4. Parallel Algorithms for GroupBy Queries 924.4.1. Traditional Methods (Merge-All and Hierarchical Merging) 924.4.2. Two-Phase Method 934.4.3. Redistribution Method 944.5. Cost Models for Parallel Sort 964.5.1. Cost Models for Serial External Merge-Sort 964.5.2. Cost Models for Parallel Merge-All Sort 984.5.3. Cost Models for Parallel Binary-Merge Sort 1004.5.4. Cost Models for Parallel Redistribution Binary-Merge Sort 1014.5.5. Cost Models for Parallel Redistribution Merge-All Sort 1024.5.6. Cost Models for Parallel Partitioned Sort 1034.6. Cost Models for Parallel GroupBy 1044.6.1. Cost Models for Parallel Two-Phase Method 1044.6.2. Cost Models for Parallel Redistribution Method 1074.7. Summary 1094.8. Bibliographical Notes 1104.9. Exercises 1105. Parallel Join 1125.1. Join Operations 1125.2. Serial Join Algorithms 1145.2.1. Nested-Loop Join Algorithm 1145.2.2. Sort-Merge Join Algorithm 1165.2.3. Hash-Based Join Algorithm 1175.2.4. Comparison 1205.3. Parallel Join Algorithms 1205.3.1. Divide and Broadcast-Based Parallel Join Algorithms 1215.3.2. Disjoint Partitioning-Based Parallel Join Algorithms 1245.4. Cost Models 1285.4.1. Cost Models for Divide and Broadcast 1285.4.2. Cost Models for Disjoint Partitioning 1295.4.3. Cost Models for Local Join 1305.5. Parallel Join Optimization 1325.5.1. Optimizing Main Memory 1325.5.2. Load Balancing 1335.6. Summary 1345.7. Bibliographical Notes 1355.8. Exercises 136Part III Advanced Parallel Query Processing6. Parallel GroupBy-Join 1416.1. Groupby-Join Queries 1416.1.1. Groupby Before Join 1426.1.2. Groupby After Join 1426.2. Parallel Algorithms for Groupby-Before-Join Query Processing 1436.2.1. Early Distribution Scheme 1436.2.2. Early GroupBy with Partitioning Scheme 1456.2.3. Early GroupBy with Replication Scheme 1466.3. Parallel Algorithms for Groupby-After-Join Query Processing 1486.3.1. Join Partitioning Scheme 1486.3.2. GroupBy Partitioning Scheme 1506.4. Cost Model Notations 1516.5. Cost Model for Groupby-Before-Join Query Processing 1536.5.1. Cost Models for the Early Distribution Scheme 1536.5.2. Cost Models for the Early GroupBy with Partitioning Scheme 1566.5.3. Cost Models for the Early GroupBy with Replication Scheme 1586.6. Cost Model for “Groupby-After-Join” Query Processing 1596.6.1. Cost Models for the Join Partitioning Scheme 1596.6.2. Cost Models for the GroupBy Partitioning Scheme 1616.7. Summary 1636.8. Bibliographical Notes 1646.9. Exercises 1647. Parallel Indexing 1677.1. Parallel Indexing–an Internal Perspective on Parallel Indexing Structures 1687.2. Parallel Indexing Structures 1697.2.1. Nonreplicated Indexing (NRI) Structures 1697.2.2. Partially Replicated Indexing (PRI) Structures 1717.2.3. Fully Replicated Indexing (FRI) Structures 1787.3. Index Maintenance 1807.3.1. Maintaining a Parallel Nonreplicated Index 1827.3.2. Maintaining a Parallel Partially Replicated Index 1827.3.3. Maintaining a Parallel Fully Replicated Index 1887.3.4. Complexity Degree of Index Maintenance 1887.4. Index Storage Analysis 1887.4.1. Storage Cost Models for Uniprocessors 1897.4.2. Storage Cost Models for Parallel Processors 1917.5. Parallel Processing of Search Queries using Index 1927.5.1. Parallel One-Index Search Query Processing 1927.5.2. Parallel Multi-Index Search Query Processing 1957.6. Parallel Index Join Algorithms 2007.6.1. Parallel One-Index Join 2007.6.2. Parallel Two-Index Join 2037.7. Comparative Analysis 2077.7.1. Comparative Analysis of Parallel Search Index 2077.7.2. Comparative Analysis of Parallel Index Join 2137.8. Summary 2167.9. Bibliographical Notes 2177.10. Exercises 2178. Parallel Universal Qualification—Collection Join Queries 2198.1. Universal Quantification and Collection Join 2208.2. Collection Types and Collection Join Queries 2228.2.1. Collection-Equi Join Queries 2228.2.2. Collection–Intersect Join Queries 2238.2.3. Subcollection Join Queries 2248.3. Parallel Algorithms for Collection Join Queries 2258.4. Parallel Collection-Equi Join Algorithms 2258.4.1. Disjoint Data Partitioning 2268.4.2. Parallel Double Sort-Merge Collection-Equi Join Algorithm 2278.4.3. Parallel Sort-Hash Collection-Equi Join Algorithm 2288.4.4. Parallel Hash Collection-Equi Join Algorithm 2328.5. Parallel Collection-Intersect Join Algorithms 2338.5.1. Non-Disjoint Data Partitioning 2348.5.2. Parallel Sort-Merge Nested-Loop Collection-Intersect Join Algorithm 2448.5.3. Parallel Sort-Hash Collection-Intersect Join Algorithm 2458.5.4. Parallel Hash Collection-Intersect Join Algorithm 2468.6. Parallel Subcollection Join Algorithms 2468.6.1. Data Partitioning 2478.6.2. Parallel Sort-Merge Nested-Loop Subcollection Join Algorithm 2488.6.3. Parallel Sort-Hash Subcollection Join Algorithm 2498.6.4. Parallel Hash Subcollection Join Algorithm 2518.7. Summary 2528.8. Bibliographical Notes 2528.9. Exercises 2549. Parallel Query Scheduling and Optimization 2569.1. Query Execution Plan 2579.2. Subqueries Execution Scheduling Strategies 2599.2.1. Serial Execution Among Subqueries 2599.2.2. Parallel Execution Among Subqueries 2619.3. Serial vs. Parallel Execution Scheduling 2649.3.1. Nonskewed Subqueries 2649.3.2. Skewed Subqueries 2659.3.3. Skewed and Nonskewed Subqueries 2679.4. Scheduling Rules 2699.5. Cluster Query Processing Model 2709.5.1. Overview of Dynamic Query Processing 2719.5.2. A Cluster Query Processing Architecture 2729.5.3. Load Information Exchange 2739.6. Dynamic Cluster Query Optimization 2759.6.1. Correction 2769.6.2. Migration 2809.6.3. Partition 2819.7. Other Approaches to Dynamic Query Optimization 2849.8. Summary 2859.9. Bibliographical Notes 2869.10. Exercises 286Part IV Grid Databases10. Transactions in Distributed and Grid Databases 29110.1. Grid Database Challenges 29210.2. Distributed Database Systems and Multidatabase Systems 29310.2.1. Distributed Database Systems 29310.2.2. Multidatabase Systems 29710.3. Basic Definitions on Transaction Management 29910.4. Acid Properties of Transactions 30110.5. Transaction Management in Various Database Systems 30310.5.1. Transaction Management in Centralized and Homogeneous Distributed Database Systems 30310.5.2. Transaction Management in Heterogeneous Distributed Database Systems 30510.6. Requirements in Grid Database Systems 30710.7. Concurrency Control Protocols 30910.8. Atomic Commit Protocols 31010.8.1. Homogeneous Distributed Database Systems 31010.8.2. Heterogeneous Distributed Database Systems 31310.9. Replica Synchronization Protocols 31410.9.1. Network Partitioning 31510.9.2. Replica Synchronization Protocols 31610.10. Summary 31810.11. Bibliographical Notes 31810.12. Exercises 31911. Grid Concurrency Control 32111.1. A Grid Database Environment 32111.2. An Example 32211.3. Grid Concurrency Control 32411.3.1. Basic Functions Required by GCC 32411.3.2. Grid Serializability Theorem 32511.3.3. Grid Concurrency Control Protocol 32911.3.4. Revisiting the Earlier Example 33311.3.5. Comparison with Traditional Concurrency Control Protocols 33411.4. Correctness of GCC Protocol 33611.5. Features of GCC Protocol 33811.6. Summary 33911.7. Bibliographical Notes 33911.8. Exercises 33912. Grid Transaction Atomicity and Durability 34112.1. Motivation 34212.2. Grid Atomic Commit Protocol (Grid-ACP) 34312.2.1. State Diagram of Grid-ACP 34312.2.2. Grid-ACP Algorithm 34412.2.3. Early-Abort Grid-ACP 34612.2.4. Discussion 34812.2.5. Message and Time Complexity Comparison Analysis 34912.2.6. Correctness of Grid-ACP 35012.3. Handling Failure of Sites with Grid-ACP 35112.3.1. Model for Storing Log Files at the Originator and Participating Sites 35112.3.2. Logs Required at the Originator Site 35212.3.3. Logs Required at the Participant Site 35312.3.4. Failure Recovery Algorithm for Grid-ACP 35312.3.5. Comparison of Recovery Protocols 35912.3.6. Correctness of Recovery Algorithm 36112.4. Summary 36512.5. Bibliographical Notes 36612.6. Exercises 36613. Replica Management in Grids 36713.1. Motivation 36713.2. Replica Architecture 36813.2.1. High-Level Replica Management Architecture 36813.2.2. Some Problems 36913.3. Grid Replica Access Protocol (GRAP) 37113.3.1. Read Transaction Operation for GRAP 37113.3.2. Write Transaction Operation for GRAP 37213.3.3. Revisiting the Example Problem 37513.3.4. Correctness of GRAP 37713.4. Handling Multiple Partitioning 37813.4.1. Contingency GRAP 37813.4.2. Comparison of Replica Management Protocols 38113.4.3. Correctness of Contingency GRAP 38313.5. Summary 38413.6. Bibliographical Notes 38513.7. Exercises 38514. Grid Atomic Commitment in Replicated Data 38714.1. Motivation 38814.1.1. Architectural Reasons 38814.1.2. Motivating Example 38814.2. Modified Grid Atomic Commitment Protocol 39014.2.1. Modified Grid-ACP 39014.2.2. Correctness of Modified Grid-ACP 39314.3. Transaction Properties in Replicated Environment 39514.4. Summary 39714.5. Bibliographical Notes 39714.6. Exercises 398Part V Other Data-Intensive Applications15. Parallel Online Analytic Processing (OLAP) and Business Intelligence 40115.1. Parallel Multidimensional Analysis 40215.2. Parallelization of ROLLUP Queries 40515.2.1. Analysis of Basic Single ROLLUP Queries 40515.2.2. Analysis of Multiple ROLLUP Queries 40915.2.3. Analysis of Partial ROLLUP Queries 41115.2.4. Parallelization Without Using ROLLUP 41215.3. Parallelization of CUBE Queries 41215.3.1. Analysis of Basic CUBE Queries 41315.3.2. Analysis of Partial CUBE Queries 41615.3.3. Parallelization Without Using CUBE 41715.4. Parallelization of Top-N and Ranking Queries 41815.5. Parallelization of Cume_Dist Queries 41915.6. Parallelization of NTILE and Histogram Queries 42015.7. Parallelization of Moving Average and Windowing Queries 42215.8. Summary 42415.9. Bibliographical Notes 42415.10. Exercises 42516. Parallel Data Mining—Association Rules and Sequential Patterns 42716.1. From Databases To Data Warehousing To Data Mining: A Journey 42816.2. Data Mining: A Brief Overview 43116.2.1. Data Mining Tasks 43116.2.2. Querying vs. Mining 43316.2.3. Parallelism in Data Mining 43616.3. Parallel Association Rules 44016.3.1. Association Rules: Concepts 44116.3.2. Association Rules: Processes 44416.3.3. Association Rules: Parallel Processing 44816.4. Parallel Sequential Patterns 45016.4.1. Sequential Patterns: Concepts 45216.4.2. Sequential Patterns: Processes 45616.4.3. Sequential Patterns: Parallel Processing 45916.5. Summary 46116.6. Bibliographical Notes 46116.7. Exercises 46217. Parallel Clustering and Classification 46417.1. Clustering and Classification 46417.1.1. Clustering 46417.1.2. Classification 46517.2. Parallel Clustering 46717.2.1. Clustering: Concepts 46717.2.2. k-Means Algorithm 46817.2.3. Parallel k-Means Clustering 47117.3. Parallel Classification 47717.3.1. Decision Tree Classification: Structures 47717.3.2. Decision Tree Classification: Processes 48017.3.3. Decision Tree Classification: Parallel Processing 48817.4. Summary 49517.5. Bibliographical Notes 49817.6. Exercises 498Permissions 501List of Conferences and Journals 507Bibliography 511Index 541