DEVANG
DEVANG PATEL INSTITUTEOF
PATEL INSTITUTE OFADVANCE
ADVANCETECHNOLOGY
TECHNOLOGY AND
AND RESEARCH
RESEARCH
Chapter : 7
Subject Faculties: Parallel Database Systems
Prof. Kashyap Patel
Assistant Professor,
Department of Computer Engineering.
Devang Patel Institute of Advance Technology And Research
Charotar University of Science and Technology
Outline:
• Parallel Architectures
• Data Placement
• Parallel Query Processing
• Load Balancing
• Fault-Tolerance
• Database Clusters
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
The Database Problem:
• Large volume of data use disk and large main memory
• I/O bottleneck (or memory access bottleneck)
• Speed(disk) << speed(RAM) << speed(microprocessor)
• Predictions
• Moore’s law: processor speed growth (with multicore): 50 % per year
• DRAM capacity growth : 4 × every three years
• Disk throughput : 2 × in the last ten years
• Conclusion : the I/O bottleneck worsens
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
The Solution:
• Increase the I/O bandwidth
• Data partitioning
• Parallel data access
• Origins (1980's): database machines
• Hardware-oriented bad cost-performance failure
• Notable exception : ICL's CAFS Intelligent Search Processor
• 1990's: same solution but using standard hardware components integrated in a
multiprocessor
• Software-oriented
• Standard essential to exploit continuing technology improvements
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Data Server Architecture:
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Objectives of Data Servers:
• Avoid the shortcomings of the traditional DBMS approach
• Centralization of data and application management
• General-purpose OS (not DB-oriented)
• By separating the functions between
• Application server (or host computer)
• Data server (or database computer or back-end computer)
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Parallel Data Processing:
• Three ways of exploiting high-performance multiprocessor systems:
Automatically detect parallelism in sequential programs (e.g., Fortran, OPS5)
Augment an existing language with parallel constructs (e.g., C*, Fortran90)
Offer a new language in which parallelism can be expressed or automatically inferred
• Critique
Hard to develop parallelizing compilers, limited resulting speed-up
Enables the programmer to express parallel computations but too low-level
Can combine the advantages of both (1) and (2)
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Data-based Parallelism:
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Parallel DBMS:
• Loose definition: a DBMS implemented on a tighly coupled multiprocessor
• Alternative extremes
• Straighforward porting of relational DBMS (the software vendor edge)
• New hardware/software combination (the computer manufacturer edge)
• Naturally extends to distributed databases with one server per site
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Parallel DBMS – Objectives:
• Much better cost / performance than mainframe solution
• High-performance through parallelism
• High throughput with inter-query parallelism
• Low response time with intra-operation parallelism
• High availability and reliability by exploiting data replication
• Extensibility with the ideal goals
• Linear speed-up
• Linear scale-up
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Parallel DBMS – Functional Architecture :
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Parallel DBMS Functions:
• Session manager
• Host interface
• Transaction monitoring for OLTP
• Request manager
• Compilation and optimization
• Data directory management
• Semantic data control
• Execution control
• Data manager
• Execution of DB operations
• Transaction management support
• Data management
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Parallel System Architectures:
• Multiprocessor architecture alternatives
• Shared memory (SM)
• Shared disk (SD)
• Shared nothing (SN)
• Hybrid architectures
• Non-Uniform Memory Architecture (NUMA)
• Cluster
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Shared-Memory:
DBMS on symmetric multiprocessors (SMP)
Prototypes: XPRS, Volcano, DBS3
+ Simplicity, load balancing, fast communication
- Network cost, low extensibility
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Shared-Disk:
Origins : DEC's VAXcluster, IBM's IMS/VS Data Sharing
Used first by Oracle with its Distributed Lock Manager
Now used by most DBMS vendors
+ network cost, extensibility, migration from uniprocessor
- complexity, potential performance problem for cache coherency
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Shared-Nothing:
Used by Teradata, IBM, Sybase, Microsoft for OLAP
Prototypes: Gamma, Bubba, Grace, Prisma, EDS
+ Extensibility, availability
- Complexity, difficult load balancing
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Hybrid Architectures:
• Various possible combinations of the three basic architectures are possible to obtain
different trade-offs between cost, performance, extensibility, availability, etc.
• Hybrid architectures try to obtain the advantages of different architectures:
• efficiency and simplicity of shared-memory
• extensibility and cost of either shared disk or shared nothing
• 2 main kinds: NUMA and cluster
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
NUMA:
• Shared-Memory vs. Distributed Memory
• Mixes two different aspects : addressing and memory
• Addressing: single address space vs multiple address spaces
• Physical memory: central vs distributed
• NUMA = single address space on distributed physical memory
• Eases application portability
• Extensibility
• The most successful NUMA is Cache Coherent NUMA (CC-NUMA)
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
CC-NUMA:
• Principle
• Main memory distributed as with shared-nothing
• However, any processor has access to all other processors’ memories
• Similar to shared-disk, different processors can access the same data in a conflicting
update mode, so global cache consistency protocols are needed.
• Cache consistency done in hardware through a special consistent cache interconnect
• Remote memory access very efficient, only a few times (typically between 2 and 3 times) the cost
of local access
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Cluster:
• Combines good load balancing of SM with extensibility of SN
• Server nodes: off-the-shelf components
• From simple PC components to more powerful SMP
• Yields the best cost/performance ratio
• In its cheapest form,
• Fast standard interconnect (e.g., Myrinet and Infiniband) with high bandwidth
(Gigabits/sec) and low latency
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
SN cluster vs SD cluster:
• SN cluster can yield best cost/performance and extensibility
• But adding or replacing cluster nodes requires disk and data reorganization
• SD cluster avoids such reorganization but requires disks to be globally accessible by the
cluster nodes
• Network-attached storage (NAS)
• distributed file system protocol such as NFS, relatively slow and not appropriate for database
management
• Storage-area network (SAN)
• Block-based protocol thus making it easier to manage cache consistency, efficient, but costlier
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Parallel DBMS Techniques:
• Data placement
• Physical placement of the DB onto multiple nodes
• Static vs. Dynamic
• Parallel data processing
• Select is easy
• Join (and all other non-select operations) is more difficult
• Parallel query optimization
• Choice of the best parallel execution plans
• Automatic parallelization of the queries and load balancing
• Transaction management
• Similar to distributed transaction management
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Data Partitioning:
• Each relation is divided in n partitions (subrelations), where n is a function of relation size
and access frequency
• Implementation
• Round-robin
• Maps i-th element to node i mod n
• Simple but only exact-match queries
• B-tree index
• Supports range queries but large index
• Hash function
• Only exact-match queries but small index
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Partitioning Schemes:
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Placement Directory:
• Performs two functions
• F1 (relname, placement attval) = lognode-id
• F2 (lognode-id) = phynode-id
• In either case, the data structure for f1 and f2 should be available when needed at each
node
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Join Processing:
• Three basic algorithms for intra-operator parallelism
• Parallel nested loop join: no special assumption
• Parallel associative join: one relation is declustered on join attribute and equi-join
• Parallel hash join: equi-join
• They also apply to other complex operators such as duplicate elimination, union,
intersection, etc. with minor adaptation
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Parallel Nested Loop Join:
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Parallel Associative Join:
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Parallel Hash Join:
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Parallel Query Optimization:
• The objective is to select the “best” parallel execution plan for a query using the following
components
• Search space
• Models alternative execution plans as operator trees
• Left-deep vs. Right-deep vs. Bushy trees
• Search strategy
• Dynamic programming for small search space
• Randomized for large search space
• Cost model (abstraction of execution system)
• Physical schema info. (partitioning, indexes, etc.)
• Statistics and cost functions
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Load Balancing:
• Problems arise for intra-operator parallelism with skewed data distributions
• attribute data skew (AVS)
• tuple placement skew (TPS)
• selectivity skew (SS)
• redistribution skew (RS)
• join product skew (JPS)
• Solutions
• sophisticated parallel algorithms that deal with skew
• dynamic processor allocation (at execution time)
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Load Balancing in a DB Cluster:
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
The Exadata Database Machine:
• New machine from Oracle with Sun
• Objectives
• OLTP, OLAP, mixed workloads
• Oracle Real Application Cluster
• 8+ servers bi-pro Xeon, 72 GB RAM
• Exadata storage server : intelligent cache
• 14+ cells, each with
• 2 processors, 24 Go RAM
• 385 GB of Flash memory (read is 10* faster than disk)
• 12+ SATA disks of 2 To or 12 SAS disks of 600 GB
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Exadata Architecture:
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
Thank you
DEVANG PATEL INSTITUTE OF ADVANCE TECHNOLOGY AND RESEARCH
