In recent years, the amount of data handled by a database management system (DBMS) increased continuously that it is no longer unusual for a DBMS to manage data size of several hundred gigabytes to terabytes [2]. This is due to the growing need for DBMSs to exhibit more sophisticated functionality such as the support of object-oriented, deductive, and multimedia-based application [2]. Also, the evolution of Internet and World Wide Web increases the number of DBMS users to a huge amount. As the size of users and data increases traditional DBMSs that use a single powerful mainframe faced difficulty in meeting the (disk and network) I/O and CPU performance requirement, since it could not scale well to the changes. To achieve the performance requirement, database systems have been increasingly required to make use of parallelism, which fall in one of the two resulting DBMS architecture. These are parallel DBMS and distributed DBMS. A parallel DBMS can be defined as a DBMS implemented on a tightly coupled multiprocessor [3]. A distributed DBMS is defined as the software system that permits the management of distributed database - a collection of multiple, logically interrelated databases distributed over a computer network - and makes the distribution transparent to the users [3]. It is somewhat unclear to distinguish between the two, particularly for shared-nothing parallel DBMS and distributed DBMS - indeed, query operations used for one system can be used in others without significant modification. This paper concentrates on how parallelism is applied to a distributed DBMS, and what is general requirement of a distributed DBMS. However, to establish the background of distributed DBMS, a level of discussion on parallel DBMS is also made.
2. Parallelism in DBMSs
The goals of parallelism are twofold: one is to speedup a processing of a given job (i.e. reduce response time), and the other is to scale up the system to process a larger number of jobs at a time (i.e. increase throughput). Most of traditional DBMS used relational database approach, which was the dominating at the time - it is still dominating database approach. The fact that relational queries are ideally suited to parallel execution gave great interest to many researchers in adopting parallelism in DBMS, and resulted in giving birth to parallel DBMSs. Relational queries consist of uniform operations applied to uniform streams of data [1]. Each operator produces a new relation, so the operators can be composed into highly parallel dataflow graphs [1].
Dataflow approach to relational operators gives both pipelined and partitioned parallelism.
There are two forms of parallelism that can be applied to DBMSs . By streaming the output of one operation into the input of another operator, the two operators can be work in series giving pipelined parallelism [1]. By partitioning the input data among multiple processors and memories, and operator can often be split into many independent operators each working on a part of the data [1]. This partitioned data and execution gives partitioned parallelism [1].
3. Parallel DBMSs The first outcome of adopting parallelism in DBMSs was parallel DBMSs. The systems use multiprocessors with more than one disk storage. Ideally, twice as much hardware can perform the task in half the elapsed time, or twice as much hardware can perform twice as large a talk in the same elapsed time. However, this cannot be achieved. In parallel DBMS, three machine architectures, upon which parallel DBMSs are running, were proposed and used to minimize response time and maximize throughput. These are shared-memory, shared-disk and shared-nothing multiprocessors .
Three types of multiprocessors design Three types of multiprocessors design
In shared-memory multiprocessor architecture, processors share memory and storage disks via interconnection network. In shared-disk architecture, each processor has private memory and share only storage disks via interconnection network. For shared-nothing architecture, each processor has private memory and one or more private disk storage. Among the three architecture, shared-nothing is wining the competition. Shared-nothing multiprocessor moves only question and answer through the network, and thus low traffic is expected in the interconnection network. This gives low network interference among processors, and thus allows high scalability. For shared-memory multiprocessor, network interference is the major problem. Furthermore, partitioning creates many of the skew and load-balancing problems faced by shared-nothing machine; but reaps none of the simpler hardware interconnect benefits. Shared-disk multiprocessor improves network interference problem of shared-memory multiprocessor, however, it only adequate for large read-only databases and for databases where there is no concurrent sharing, and not very efficient for a database application that reads and writes a shared database. When a processor wants a shared disk page for write concurrency control is an issue. To implement this in shared-disk architecture inter-processor communication is necessary for reservation and release. There are many optimizations of this protocol, but they all ends up exchanging reservation messages and exchanging large physical data pages [1]. It creates processor interference and delays, and heavy traffic on the shared interconnection network. In fact, a scheme that other processors wanting to access a data page send message to the server managing the data instead of the described scheme. But this fits more naturally to shared-nothing architecture. Another fact about shared-nothing multiprocessor model is that its architecture is indeed same with the distributed DBMS architecture. Only difference between the two is one operates within an operating system and the other has its own operating system. However, since a special purpose distributed operating system is used for the distributed DBMS, which logically works as a single operating system, all relational database operations used for shared-nothing can be used in distributed DBMS without much modifications.
4. Distributed DBMS Noting that the shared-nothing architecture is the winner of competition of underlying architecture of parallel DBMS, and that the architecture is virtually same with that of distributed DBMS, it seems like distributed DBMSs is more natural way to exercise parallelism. A distributed DBMS more naturally scaleable than a shared-nothing architecture based parallel DBMS in that one can just add more PCs or workstation to the system to scale up. Also, the network I/O bottleneck can be avoided since more than one server can serve clients, (for example, a separate switched gigabit network might be used for server-to-server communication). The problem with this approach is that the underlying network is rather slow and unreliable. But as faster networks like ATM is developed, this would turn out to be a minor problem.
View of a distributed DBMS
Followings are the major issues in distributed DBMS. Many of them could overlap with the issues of general DBMS. (1) Distributed DBMS use data partitioning when they place relation fragments at different network sites [1]. Three (horizontal) partitioning exits, which are range partitioning, round-robin, and hashing. Each one has advantages and disadvantages, and is very application specific. Also, it is possible to vertically partition a relation (i.e. select a set of attribute from a relation and store them in other network site). (2) There is an issue of query processing and optimization. It should be possible for a distributed DBMS to get ordinary query in SQL and generate distributed query plans and performs optimization. Next section will talk about this topic further. (3) Concurrency control is another issue. For example, if a locking-based algorithm is used for concurrency control, it would be hard to manage distributed deadlock. (4) Another issue is reliability control. A distributed reliability protocol should enforce atomicity (all-or-nothing property) of transaction by implementing atomic commitment protocols such as the two-phase commit (2PC). The last issue in distributed DBMS is replication and consistency control. Replication of a server, disk, relation, or relation segment could be made to prevent whole system down when a server down. Here, inconsistency problem may occur. Therefore, a mechanism to enforce consistency should be implemented. One typical very simple protocol is Read-One/Write-All (ROWA) protocol. More advanced protocols, such as quorum-based voting, are available.
5. Query Processing And Optimization Before discussing the query processing, note that the benefits of pipeline parallelism are limited. First, relational pipelines are rarely very long [1]. Second, some relational operators do not emit their first output until they have consumed all their input (Aggregate and Sort operator is an example) [1]. Third, often execution cost of one operator is much greater than that of others. However, partitioned parallelism offers much better opportunities for speedup and scaleup, because it is possible to use divide-and-conquer to turn one big job into many independent little ones. Therefore, when making query processing plan for a distributed DBMS or performing query optimization, the system would focus on exercising partitioned parallelism. When processing a query, distributed DBMS and parallel DBMS analyze the potential parallelism of the request and make query plans using Extended Dataflow Graph (EDG) along with the Engineering Model that the database use. EDG extends a conventional data flow graph (that is, data operation nodes interconnected by data communication arcs) with partition parallelism; as such, one data operation node may be made up of multiple subnodes [2]. As a result, complex and time consuming database operations, such as join, can be executed concurrently in a divide-and-conquer manner [2]. shows an example ERD for a given query on a particular database design. The example assumes that employee relation is partitioned in three fragments (i.e. E1, E2 and E3) and the department relation in two (i.e. D1 and D2).
Extended Dataflow Graph
An EDG is a self-scheduling structure such that one the START signal is sent, the execution of the EDG will run to completion by itself without any external control. The control of the execution of the EDG is completely data driven. In the figure SW stands for Single Wait and GW stands for Global Wait. One thing to note is that an EDG only shows the potential parallelism of a request. The actual parallelism depends on the implementation of a database, and realization of the parallelism is achieved through an engineering model the distributed database employs. An engineering model defines how an EDG is physically executed on a parallel (distributed) database environment [1].
Overall internal architecture of a distributed database system shows a general architecture of a distributed database system. In the architecture, the request manager makes query processing plans and performs the optimization. The role of the request manager is (1) to transform a user's request into a set of semantic equivalent EDGs; (2) to select the "best" EDG from the set; and (3) finally, to translate the EDG into an executable object file. The executable object file is then passed to the data manager and executed [1]. Data manager is actually a distributed database operating system - collection of operating systems running on different machines that cooperate together to simulate a single operating system running on a single machine. Each machine in the system then performs their job, and the result is merged together and passed back to the request manager.
6. Conclusion The project focused on the distributed database system architecture and how parallelism is exercised in the distributed environment. With the help of a distributed database operating system, distributed database system architecture is basically same with shared-nothing parallel machine architecture. The only difference is the speed and reliability of the underlying network. Shared-nothing parallel machine architecture is proven to be the most effective architecture upon which parallel database system should implemented. Since distributed database system architecture is indeed same with that of shared-nothing, and provides more natural scalability than the shared-something architecture by adding one or more computers into the system, distributed database system is likely to be the most effective system. However, because of the complexity of distributed database operating systems and the slow speed and less reliability of LAN, distributed database system was not much used even for a huge database systems. However, advent of more complete and high-performance distributed operating systems, and fast-reliable networks like ATM would bring distributed DBMS more into practice. Distributed system architecture assisted by a high-performance reliable distributed operating system and a fast-reliable network should provide the best environment - in terms of cost, performance and scalability - for exercising parallelism in database.
7. Bibliography [1] David DeWitt and Jim Gray, "Parallel Database Systems: The Future of High Performance Database Systems", Communications of the ACM, Vol. 35, No. 6, June 1992 [2] Mahdi Abdelguerfi and Kam-Fai Wong, "Parallel Database Techniques", http://computer.org/cspress /CATALOG/bp08398/intro.html [3] M. Tamar Ozsu and Patric Valdurez, "Distributed and Parallel Database System", ACM Computing Survey, Vol. 28, No. 1, March 1996. [4] Jignesh Patel, JieBing Yu, Navin Kabra, Kristin tufte, Biswadeep Nag, Josef Burger, Nancy Hall, Karthikeyan Ramasamy, Roger Lueder, Curt Ellmann, Jim Kupsch, Shelly Guo, Johan Larson, David DeWitt and Naughton, "Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation", Computer Sciences Department, University of Wisconsin-Madison.
