Parallel Database Techniques

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.

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.

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

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Parallel Database Techniques

Summary

Author Biography

Table of Contents

Supplemental Materials