Parallel Database Techniques

by Abdelguerfi, Mahdi; Wong, Kam-Fai

• ISBN13: 9780818683985
• ISBN10: 0818683988
• Edition: 1st
• Format: Hardcover
• Copyright: 1998-08-13
• Publisher: Wiley-IEEE Computer Society Pr

Summary

The use of parallel processing technology in the next generation of Database Management Systems (DBMSs) makes it possible to meet new and challenging requirements. Database technology in rapidly expanding new application areas brings unique challenges such as increased functionality and efficient handling of very large heterogeneous databases. Abdelguerfi and Wong present the latest techniques in parallel relational databases illustrating high-performance achievements in parallel database systems. The text is structured according to the overall architecture of a parallel database system presenting various techniques that may be adopted to the design of parallel database software and hardware execution environments. These techniques can directly or indirectly lead to high-performance parallel database implementation. The book's main focus follows the authors' engineering model: A survey of parallel query optimization techniques for requests involving multi-way joins; A new technique for a join operation that can be adopted in the local optimization stage; A framework for recovery in parallel database systems using the ACTA formalism; The architectural details of NCR's new Petabyte multimedia database system; A description of the Super Database Computer (SDC-II); A case study for a shared-nothing parallel database server that analyzes and compares the effectiveness of five data placement techniques.

Author Biography

Mahdi Abdelguerfi is the author of Parallel Database Techniques, published by Wiley. Kam-Fai Wong is the author of Parallel Database Techniques, published by Wiley.

Table of Contents

1 Introduction	1	(12)
1.1 Background	1	(1)
1.2 Parallel Database Systems	2	(6)
1.2.1 Computation Model	2	(2)
1.2.2 Engineering Model	4	(4)
1.3 About this Manuscript	8	(1)
Bibliography	9	(4)
I Request Manager	13	(104)
2 Designing an Optimizer for Parallel Relational Systems	15	(28)
2.1 Introduction	15	(1)
2.2 Overall Design Issues	16	(3)
2.2.1 Design a Simple Parallel Execution Model	16	(1)
2.2.2 The Two-Phase Approach	17	(1)
2.2.3 Parallelizing is Adding Information!	17	(1)
2.2.4 Two-Phase versus Parallel Approaches	18	(1)
2.3 Parallelization	19	(3)
2.3.1 Kinds of Parallelism	19	(2)
2.3.2 Specifying Parallel Execution	21	(1)
2.4 Search Space	22	(6)
2.4.1 Slicing Hash Join Trees	23	(1)
2.4.2 Search Space Size	24	(1)
2.4.3 Heuristics	25	(1)
2.4.4 The Two-Phase Heuristics	26	(2)
2.5 Cost Model	28	(6)
2.5.1 Exceptions to the Principle of Optimality	28	(2)
2.5.2 Resources	30	(1)
2.5.3 Skew and Size Model	31	(1)
2.5.4 The Cost Function	32	(2)
2.6 Search Strategies	34	(3)
2.6.1 Deterministic Search Strategies	35	(1)
2.6.2 Randomized Strategies	35	(2)
2.7 Conclusion	37	(1)
Bibliography	38	(5)
3 New Approaches to Parallel Join Utilizing Page Connectivity Information	43	(34)
3.1 Introduction	43	(3)
3.2 The Environment and a Motivating Example	46	(2)
3.3 The Methodology	48	(9)
3.3.1 Definition of Parameters	49	(1)
3.3.2 The Balancing Algorithm	50	(4)
3.3.3 Schedules for Reading Join Components and Data Pages	54	(3)
3.4 Performance Analysis	57	(14)
3.4.1 The Evaluation Method	57	(2)
3.4.2 Evaluation Results	59	(12)
3.5 Concluding Remarks and Future Work	71	(2)
Bibliography	73	(4)
4 A Performance Evaluation Tool for Parallel Database Systems	77	(16)
4.1 Introduction	77	(1)
4.2 Performance Evaluation Methods	78	(3)
4.2.1 Analytical Modeling	78	(1)
4.2.2 Benchmarks	79	(1)
4.2.3 Observations	80	(1)
4.3 The Software Testpilot	81	(3)
4.3.1 The Experiment Specification	81	(2)
4.3.2 The Performance Assessment Cycle	83	(1)
4.3.3 The System Interface	84	(1)
4.4 The Software Testpilot and Oracle/Ncube	84	(5)
4.4.1 Database System Performance Assessment	85	(2)
4.4.2 The Oracle/Ncube Interface	87	(2)
4.5 Preliminary Results	89	(2)
4.6 Conclusion	91	(1)
Bibliography	92	(1)
5 Load Placement in Distributed High-Performance Database Systems	93	(24)
5.1 Introduction	93	(1)
5.2 Investigated System	94	(6)
5.2.1 System Architecture	94	(3)
5.2.2 Load Scenarios	97	(1)
5.2.3 Trace Analysis	97	(2)
5.2.4 Load Setup	99	(1)
5.3 Load Placement Strategies Investigated	100	(2)
5.4 Scheduling Strategies for Transactions	102	(1)
5.5 Simulation Results	103	(10)
5.5.1 Influence of Scheduling	103	(1)
5.5.2 Evaluation of the Load Placement Strategies	104	(5)
5.5.3 Lessons Learned	109	(2)
5.5.4 Decision Parameters Used	111	(2)
5.6 Conclusion and Open Issues	113	(1)
Bibliography	114	(3)
II Parallel Machine Architecture	117	(66)
6 Modeling Recovery in Client-Server Database Systems	119	(20)
6.1 Introduction	119	(1)
6.2 Uniprocessor Recovery and Formal Approach to Modeling Recovery	120	(8)
6.2.1 Basic Formal Concepts	121	(2)
6.2.2 Logging Mechanisms	123	(1)
6.2.3 Runtime Policies for Ensuring Correctness	124	(1)
6.2.4 Data Structures Maintained for Efficient Recovery	125	(1)
6.2.5 Restart Recovery--The ARIES Approach	126	(2)
6.3 LSN Sequencing Techniques for Multinode Systems	128	(1)
6.4 Recovery in Client-Server Database Systems	129	(7)
6.4.1 Client-Server EXODUS (ESM-CS)	130	(3)
6.4.2 Client-Server ARIES (ARIES/CSA)	133	(2)
6.4.3 Shared Nothing Clients with Disks (CD)	135	(1)
6.4.4 Summary of Recovery Approaches in Client-Server Architectures	136	(1)
6.5 Conclusion	136	(1)
Bibliography	137	(2)
7 Parallel Strategies for a Petabyte Multimedia Database Computer	139	(26)
7.1 Introduction	140	(1)
7.2 Multimedia Data Warehouse, Databases, and Applications	141	(3)
7.2.1 Three Waves of Multimedia Database Development	141	(1)
7.2.2 National Medical Practice Knowledge Bank Application	142	(2)
7.3 Massively Parallel Architecture, Infrastructure, and Technology	144	(2)
7.3.1 Parallelism	145	(1)
7.4 Teradata-MM Architecture, Framework, and New Concepts	146	(9)
7.4.1 Teradata-MM Architecture	146	(1)
7.4.2 Key New Concepts	146	(5)
7.4.3 SQL3	151	(1)
7.4.4 Federated Coordinator	151	(1)
7.4.5 Teradata Multimedia Object Server	152	(3)
7.5 Parallel UDF Execution Analysis	155	(7)
7.5.1 UDF Optimizations	155	(3)
7.5.2 PRAGMA Facility	158	(1)
7.5.3 UDF Value Persistence Facility	159	(1)
7.5.4 Spatial Indices for Content-Based Querying	160	(2)
7.6 Conclusion	162	(1)
Bibliography	162	(3)
8 The MEDUSA Project	165	(18)
8.1 Introduction	165	(1)
8.2 Indexing and Data Partitioning	166	(1)
8.2.1 Standard Systems	166	(1)
8.2.2 Grid Files	167	(1)
8.3 Dynamic Load Balancing	167	(2)
8.3.1 Data Access Frequency	168	(1)
8.3.2 Data Distribution	168	(1)
8.3.3 Query Partitioning	168	(1)
8.4 The MEDUSA Project	169	(5)
8.4.1 The MEDUSA Architecture	169	(1)
8.4.2 Software	169	(3)
8.4.3 Grid File Implementation	172	(2)
8.4.4 Load Balancing Strategy	174	(1)
8.5 MEDUSA Performance Results	174	(6)
8.5.1 Test Configuration	174	(1)
8.5.2 Transaction Throughput	175	(2)
8.5.3 Speedup	177	(3)
8.5.4 Load Balancing Test Results	180	(1)
8.6 Conclusions	180	(1)
Bibliography	181	(2)
III Partitioned Data Store	183	(38)
9 System Software of the Super Database Computer SDC-II	185	(18)
9.1 Introduction	185	(1)
9.2 Architectural Overview of the SDC-II	186	(2)
9.3 Design and Organization of the SDC-II System Software	188	(5)
9.3.1 Parallel Execution Model	188	(1)
9.3.2 I/O Model and Buffer Management Strategy for Bulk Data Transfer	189	(2)
9.3.3 Process Model and Efficient Flow Control Mechanism	191	(1)
9.3.4 Structure of the System Software Components	192	(1)
9.4 Evaluation of the SDC-II System	193	(7)
9.4.1 Details of a Sample Query Processing	193	(4)
9.4.2 Comparison with Commercial Systems	197	(3)
9.5 Conclusion	200	(1)
Bibliography	200	(3)
10 Data Placement in Parallel Database Systems	203	(18)
10.1 Introduction	203	(1)
10.2 Overview of Data Placement Strategies	204	(4)
10.2.1 Declustering and Redistribution	204	(1)
10.2.2 Placement	205	(3)
10.3 Effects of Data Placement	208	(8)
10.3.1 STEADY and TPC-C	208	(1)
10.3.2 Dependence on Number of Processing Elements	209	(3)
10.3.3 Dependence on Database Size	212	(4)
10.4 Conclusions	216	(2)
Bibliography	218	(3)
Contributors	221