The Gamma Database Machine Project

Computer Sciences Department University of Wisconsin

This research was partially supported by the Defense Advanced Research Projects Agency under contract N00039-86-C-0578, by the National Science Foundation under grant DCR-8512862, by a DARPA/NASA sponsored Graduate Research Assistantship in Parallel Processing, and by research grants from Intel Scientific Computers, Tandem Computers, and Digital Equipment Corporation.

ABSTRACT

This paper describes the design of the Gamma database machine and the techniques employed in its implementation. Gamma is a relational database machine currently operating on an Intel iPSC/2 hypercube with 32 processors and 32 disk drives. Gamma employs three key technical ideas which enable the architecture to be scaled to 100s of processors. First, all relations are horizontally partitioned across multiple disk drives enabling relations to be scanned in parallel. Second, novel parallel algorithms based on hashing are used to implement the complex relational operators such as join and aggregate functions. Third, dataflow scheduling techniques are used to coordinate multioperator queries. By using these techniques it is possible to control the execution of very complex queries with minimal coordination - a necessity for configurations involving a very large number of processors.

In addition to describing the design of the Gamma software, a thorough performance evaluation of the iPSC/2 hypercube version of Gamma is also presented. In addition to measuring the effect of relation size and indices on the response time for selection, join, aggregation, and update queries, we also analyze the performance of Gamma relative to the number of processors employed when the sizes of the input relations are kept constant (speedup) and when the sizes of the input relations are increased proportionally to the number of processors (scaleup). The speedup results obtained for both selection and join queries are linear; thus, doubling the number of processors halves the response time for a query. The scaleup results obtained are also quite encouraging. They reveal that a nearly constant response time can be maintained for both selection and join queries as the workload is increased by adding a proportional number of processors and disks.

Dự án Máy Cơ sở dữ liệu Gamma

David J. DeWitt Shahram Ghandeharizadeh Donovan Schneider Allan Bricker Hui-I Hsiao Rick Rasmussen

Khoa Khoa học Máy tính Đại học Wisconsin

Nghiên cứu này được hỗ trợ một phần bởi Cơ quan Dự án Nghiên cứu Tiên tiến Quốc phòng theo hợp đồng N00039-86-C-0578, bởi Quỹ Khoa học Quốc gia theo tài trợ DCR-8512862, bởi một chương trình Trợ lý Nghiên cứu Sau đại học do DARPA/NASA tài trợ trong lĩnh vực Xử lý Song song, và bởi các khoản tài trợ nghiên cứu từ Intel Scientific Computers, Tandem Computers, và Digital Equipment Corporation.

TÓM TẮT

Bài báo này mô tả thiết kế của máy cơ sở dữ liệu Gamma và các kỹ thuật được sử dụng trong quá trình triển khai nó. Gamma là một máy cơ sở dữ liệu quan hệ hiện đang hoạt động trên một siêu khối Intel iPSC/2 với 32 bộ xử lý và 32 ổ đĩa. Gamma sử dụng ba ý tưởng kỹ thuật then chốt cho phép kiến trúc có thể mở rộng đến hàng trăm bộ xử lý. Thứ nhất, tất cả các quan hệ được phân vùng theo chiều ngang trên nhiều ổ đĩa, cho phép quét các quan hệ song song. Thứ hai, các thuật toán song song mới dựa trên băm được sử dụng để triển khai các toán tử quan hệ phức tạp như phép nối và các hàm tổng hợp. Thứ ba, các kỹ thuật lập lịch luồng dữ liệu được sử dụng để phối hợp các truy vấn đa toán tử. Bằng cách sử dụng các kỹ thuật này, có thể kiểm soát việc thực thi các truy vấn rất phức tạp với sự phối hợp tối thiểu - một yêu cầu cần thiết đối với các cấu hình liên quan đến một số lượng rất lớn bộ xử lý.

Ngoài việc mô tả thiết kế của phần mềm Gamma, bài báo cũng trình bày một đánh giá hiệu năng toàn diện của phiên bản Gamma trên siêu khối iPSC/2. Ngoài việc đo lường ảnh hưởng của kích thước quan hệ và các chỉ mục đến thời gian đáp ứng đối với các truy vấn chọn lọc, nối, tổng hợp và cập nhật, chúng tôi cũng phân tích hiệu năng của Gamma so với số lượng bộ xử lý được sử dụng khi kích thước của các quan hệ đầu vào được giữ không đổi (tăng tốc) và khi kích thước của các quan hệ đầu vào được tăng tỷ lệ thuận với số lượng bộ xử lý (mở rộng quy mô). Các kết quả tăng tốc thu được cho cả truy vấn chọn lọc và truy vấn nối là tuyến tính; do đó, việc tăng gấp đôi số lượng bộ xử lý sẽ giảm một nửa thời gian đáp ứng cho một truy vấn. Các kết quả mở rộng quy mô thu được cũng rất đáng khích lệ. Chúng cho thấy rằng có thể duy trì thời gian đáp ứng gần như không đổi đối với cả truy vấn chọn lọc và truy vấn nối khi tải công việc được tăng lên bằng cách bổ sung một số lượng bộ xử lý và đĩa tỷ lệ thuận.

1 Introduction

1 Giới thiệu

For the last 5 years, the Gamma database machine project has focused on issues associated with the design and implementation of highly parallel database machines. In a number of ways, the design of Gamma is based on what we learned from our earlier database machine DIRECT [DEWI79]. While DIRECT demonstrated that parallelism could be successfully applied to processing database operations, it had a number of serious design deficiencies that made scaling of the architecture to 100s of processors impossible; primarily the use of shared memory and centralized control for the execution of its parallel algorithms [BITT83].

Trong 5 năm qua, dự án máy cơ sở dữ liệu Gamma đã tập trung vào các vấn đề liên quan đến thiết kế và triển khai các máy cơ sở dữ liệu song song cao. Theo nhiều cách, thiết kế của Gamma dựa trên những điều chúng tôi đã học được từ máy cơ sở dữ liệu trước đây của mình, DIRECT [DEWI79]. Mặc dù DIRECT đã chứng minh rằng tính song song có thể được áp dụng thành công vào việc xử lý các thao tác cơ sở dữ liệu, nó có một số thiếu sót nghiêm trọng trong thiết kế khiến việc mở rộng kiến trúc lên hàng trăm bộ xử lý là không thể; chủ yếu là do việc sử dụng bộ nhớ chia sẻ và điều khiển tập trung cho việc thực thi các thuật toán song song của nó [BITT83].

As a solution to the problems encountered with DIRECT, Gamma employs what appear today to be relatively straightforward solutions. Architecturally, Gamma is based on a shared-nothing [STON86] architecture consisting of a number of processors interconnected by a communications network such as a hypercube or a ring, with disks directly connected to the individual processors. It is generally accepted that such architectures can be scaled to incorporate 1000s of processors. In fact, Teradata database machines [TERA85] incorporating a shared-nothing architecture with over 200 processors are already in use. The second key idea employed by Gamma is the use of hash-based parallel algorithms. Unlike the algorithms employed by DIRECT, these algorithms require no centralized control and can thus, like the hardware architecture, be scaled almost indefinitely. Finally, to make the best of the limited I/O bandwidth provided by the current generation of disk drives, Gamma employs the concept of horizontal partitioning [RIES78] (also termed declustering [LIVN87]) to distribute the tuples of a relation among multiple disk drives. This design enables large relations to be processed by multiple processors concurrently without incurring any communications overhead.

Như một giải pháp cho các vấn đề gặp phải với DIRECT, Gamma sử dụng những giải pháp ngày nay có vẻ tương đối đơn giản. Về mặt kiến trúc, Gamma dựa trên kiến trúc không chia sẻ (shared-nothing) [STON86] bao gồm một số bộ xử lý được kết nối với nhau bởi một mạng truyền thông như hypercube hoặc vòng, với các đĩa được kết nối trực tiếp tới từng bộ xử lý riêng lẻ. Người ta nhìn chung chấp nhận rằng các kiến trúc như vậy có thể được mở rộng để tích hợp hàng nghìn bộ xử lý. Trên thực tế, các máy cơ sở dữ liệu Teradata [TERA85] sử dụng kiến trúc không chia sẻ với hơn 200 bộ xử lý đã được đưa vào sử dụng. Ý tưởng then chốt thứ hai được Gamma sử dụng là việc dùng các thuật toán song song dựa trên băm. Không giống như các thuật toán được sử dụng bởi DIRECT, các thuật toán này không yêu cầu điều khiển tập trung và do đó, giống như kiến trúc phần cứng, có thể được mở rộng gần như vô hạn. Cuối cùng, để tận dụng tốt nhất băng thông I/O hạn chế do thế hệ ổ đĩa hiện tại cung cấp, Gamma sử dụng khái niệm phân vùng ngang [RIES78] (còn được gọi là phân cụm lại [LIVN87]) để phân phối các bộ của một quan hệ giữa nhiều ổ đĩa. Thiết kế này cho phép các quan hệ lớn được xử lý bởi nhiều bộ xử lý đồng thời mà không phát sinh bất kỳ chi phí phụ trội truyền thông nào.

After the design of the Gamma software was completed in the fall of 1984, work began on the first prototype which was operational by the fall of 1985. This version of Gamma was implemented on top of an existing multi-computer consisting of 20 VAX 11/750 processors [DEWI84b]. In the period of 1986-1988, the prototype was enhanced through the addition of a number of new operators (e.g. aggregate and update operators), new parallel join methods (Hybrid, Grace, and Sort-Merge [SCHN89a]), and a complete concurrency control mechanism. In addition, we also conducted a number of performance studies of the system during this period [DEWI86, DEWI88, GHAN89, GHAN90]. In the spring of 1989, Gamma was ported to a 32 processor Intel iPSC/2 hypercube and the VAX-based prototype was retired.

Sau khi thiết kế phần mềm Gamma được hoàn thành vào mùa thu năm 1984, công việc bắt đầu trên nguyên mẫu đầu tiên, nguyên mẫu này đã hoạt động vào mùa thu năm 1985. Phiên bản Gamma này được triển khai trên nền một hệ thống đa máy tính hiện có bao gồm 20 bộ xử lý VAX 11/750 [DEWI84b]. Trong giai đoạn 1986-1988, nguyên mẫu được cải tiến thông qua việc bổ sung một số toán tử mới (ví dụ: các toán tử tổng hợp và cập nhật), các phương pháp kết nối song song mới (Hybrid, Grace, và Sort-Merge [SCHN89a]), cùng một cơ chế điều khiển đồng thời hoàn chỉnh. Ngoài ra, chúng tôi cũng tiến hành một số nghiên cứu về hiệu năng của hệ thống trong giai đoạn này [DEWI86, DEWI88, GHAN89, GHAN90]. Vào mùa xuân năm 1989, Gamma được chuyển sang một hypercube Intel iPSC/2 gồm 32 bộ xử lý và nguyên mẫu dựa trên VAX được loại bỏ.

Gamma is similar to a number of other active parallel database machine efforts. In addition to Teradata [TERA85], Bubba [COPE88] and Tandem [TAND88] also utilize a shared-nothing architecture and employ the concept of horizontal partitioning. While Teradata and Tandem also rely on hashing to decentralize the execution of their parallel algorithms, both systems tend to rely on relatively conventional join algorithms such as sort-merge for processing the fragments of the relation at each site. Gamma, XPRS [STON88], and Volcano [GRAE89] each utilize parallel versions of the Hybrid join algorithm [DEWI84a].

Gamma tương tự với một số nỗ lực tích cực khác về máy cơ sở dữ liệu song song. Ngoài Teradata [TERA85], Bubba [COPE88] và Tandem [TAND88] cũng sử dụng kiến trúc không chia sẻ và áp dụng khái niệm phân vùng ngang. Trong khi Teradata và Tandem cũng dựa vào băm để phi tập trung hóa việc thực thi các thuật toán song song của chúng, cả hai hệ thống có xu hướng dựa vào các thuật toán kết nối tương đối truyền thống như sort-merge để xử lý các mảnh của quan hệ tại mỗi vị trí. Gamma, XPRS [STON88], và Volcano [GRAE89] đều sử dụng các phiên bản song song của thuật toán kết nối Hybrid [DEWI84a].

The remainder of this paper is organized as follows. In Section 2 we describe the hardware used by each of the Gamma prototypes and our experiences with each. Section 3 discusses the organization of the Gamma software and describes how multioperator queries are controlled. The parallel algorithms employed by Gamma are described in Section 4 and the techniques we employ for transaction and failure management are contained in Section 5. Section 6 contains a performance study of the 32 processor Intel hypercube prototype. Our conclusions and future research directions are described in Section 7.

Phần còn lại của bài báo này được tổ chức như sau. Trong Section 2, chúng tôi mô tả phần cứng được sử dụng bởi mỗi nguyên mẫu Gamma và kinh nghiệm của chúng tôi với từng nguyên mẫu. Section 3 thảo luận về tổ chức của phần mềm Gamma và mô tả cách các truy vấn nhiều toán tử được điều khiển. Các thuật toán song song được Gamma sử dụng được mô tả trong Section 4 và các kỹ thuật chúng tôi sử dụng cho quản lý giao dịch và sự cố được trình bày trong Section 5. Section 6 trình bày một nghiên cứu về hiệu năng của nguyên mẫu hypercube Intel gồm 32 bộ xử lý. Các kết luận và hướng nghiên cứu tương lai của chúng tôi được mô tả trong Section 7.

2 Hardware Architecture of Gamma

2 Kiến trúc phần cứng của Gamma

2.1. Overview

2.1. Tổng quan

Gamma is based on the concept of a shared-nothing architecture [STON86] in which processors do not share disk drives or random access memory and can only communicate with one another by sending messages through an interconnection network. Mass storage in such an architecture is generally distributed among the processors by connecting one or more disk drives to each processor as shown in Figure 1. There are a number of reasons why the shared-nothing approach has become the architecture of choice. First, there is nothing to prevent the architecture from scaling to 1000s of processors unlike shared-memory machines for which scaling beyond 30-40 processors may be impossible. Second, as demonstrated in [DEWI88, COPE88, TAND88], by associating a small number of

Gamma dựa trên khái niệm về một kiến trúc không chia sẻ (shared-nothing) [STON86] trong đó các bộ xử lý không chia sẻ các ổ đĩa hoặc bộ nhớ truy cập ngẫu nhiên và chỉ có thể giao tiếp với nhau bằng cách gửi các thông điệp qua một mạng liên kết. Lưu trữ khối lượng lớn trong một kiến trúc như vậy thường được phân tán giữa các bộ xử lý bằng cách kết nối một hoặc nhiều ổ đĩa với mỗi bộ xử lý như được minh họa trong Hình 1. Có một số lý do khiến phương pháp không chia sẻ trở thành kiến trúc được lựa chọn. Thứ nhất, không có gì ngăn cản kiến trúc đạt khả năng mở rộng tới hàng nghìn bộ xử lý, không giống như các máy chia sẻ bộ nhớ mà việc mở rộng vượt quá 30-40 bộ xử lý có thể là không khả thi. Thứ hai, như được chứng minh trong [DEWI88, COPE88, TAND88], bằng cách liên kết một số lượng nhỏ

Figure.

ổ đĩa Hình 1 với mỗi bộ xử lý và phân phối các bộ của mỗi quan hệ trên các ổ đĩa, có thể đạt được băng thông I/O tổng hợp rất cao mà không sử dụng các bộ điều khiển đĩa tùy chỉnh [KIM86, PATT88]. Hơn nữa, bằng cách sử dụng công nghệ lưu trữ khối lượng lớn có sẵn trên thị trường, người ta có thể sử dụng công nghệ mới nhất trong các ổ đĩa nhỏ 3 1/2" với bộ điều khiển đĩa tích hợp. Một ưu điểm khác của phương pháp không chia sẻ là không còn cần phải tự xây dựng phần cứng. Gần đây, cả Intel và Ncube đã bổ sung lưu trữ khối lượng lớn vào các sản phẩm đa bộ xử lý dựa trên hypercube của họ.

Figure 1 disks with each processor and distributing the tuples of each relation across the disk drives, it is possible to achieve very high aggregate I/O bandwidths without using custom disk controllers [KIM86, PATT88]. Furthermore, by employing off-the-shelf mass storage technology one can employ the latest technology in small 3 1/2" disk drives with embedded disk controllers. Another advantage of the shared nothing approach is that there is no longer any need to "roll your own" hardware. Recently, both Intel and Ncube have added mass storage to their hypercube-based multiprocessor products.

2.2. Phiên bản Gamma 1.0

2.2. Gamma Version 1.0

Phiên bản ban đầu của Gamma bao gồm 17 bộ xử lý VAX 11/750, mỗi bộ có hai megabyte bộ nhớ. Một vòng token 80 megabit/giây [PROT85] được sử dụng để kết nối các bộ xử lý với nhau và với một VAX khác đang chạy Unix. Bộ xử lý này đóng vai trò là máy chủ cho Gamma. Tám trong số các bộ xử lý được gắn các ổ đĩa Fujitsu 333 megabyte được sử dụng để lưu trữ cơ sở dữ liệu. Các bộ xử lý không có đĩa được sử dụng cùng với các bộ xử lý có đĩa để thực thi các toán tử hàm nối và tổng hợp nhằm khảo sát liệu các bộ xử lý không có đĩa có thể được khai thác hiệu quả hay không.

The initial version of Gamma consisted of 17 VAX 11/750 processors, each with two megabytes of memory. An 80 megabit/second token ring [PROT85] was used to connect the processors to each other and to another VAX running Unix. This processor acted as the host machine for Gamma. Attached to eight of the processors were 333 megabyte Fujitsu disk drives that were used for storing the database. The diskless processors were used along with the processors with disks to execute join and aggregate function operators in order to explore whether diskless processors could be exploited effectively.

Chúng tôi gặp phải một số vấn đề với nguyên mẫu này. Thứ nhất, vòng token có kích thước gói mạng tối đa là 2K byte. Trong phiên bản đầu tiên của nguyên mẫu, kích thước của một trang đĩa được đặt là 2K byte để có thể truyền một trang đĩa "nguyên vẹn" từ một bộ xử lý sang bộ xử lý khác mà không cần sao chép. Điều này yêu cầu, ví dụ, mỗi trang đĩa cũng phải chứa không gian cho phần đầu giao thức được phần mềm giao tiếp giữa các bộ xử lý sử dụng. Mặc dù ban đầu điều này có vẻ là một ý tưởng tốt, chúng tôi nhanh chóng nhận ra rằng lợi ích của kích thước trang đĩa lớn hơn bù đắp nhiều hơn chi phí phải sao chép các bộ từ một trang đĩa vào một gói mạng.

We encountered a number of problems with this prototype. First, the token ring had a maximum network packet size of 2K bytes. In the first version of the prototype the size of a disk page was set to 2K bytes in order to be able to transfer an "intact" disk page from one processor to another without a copy. This required, for example, that each disk page also contain space for the protocol header used by the interprocessor communication software. While this initially appeared to be a good idea, we quickly realized that the benefits of a larger disk page size more than offset the cost of having to copy tuples from a disk page into a network packet.

Vấn đề thứ hai chúng tôi gặp phải là giao diện mạng và Unibus trên 11/750 đều là các nút thắt cổ chai [GERB87, DEWI88]. Mặc dù băng thông của chính vòng token là 80 megabit/giây, Unibus trên 11/750 (nơi giao diện mạng được gắn vào) chỉ có băng thông 4 megabit/giây. Khi thực thi một truy vấn nối mà không có vị từ chọn trên bất kỳ quan hệ đầu vào nào, Unibus trở thành nút thắt cổ chai vì tốc độ truyền các trang từ đĩa cao hơn tốc độ của Unibus [DEWI88]. Giao diện mạng là một nút thắt cổ chai vì nó chỉ có thể đệm hai gói đến tại một thời điểm. Cho đến khi một gói được truyền vào bộ nhớ của VAX, các gói đến khác bị từ chối và phải được giao thức truyền thông truyền lại. Mặc dù cuối cùng chúng tôi đã xây dựng một giao diện tới vòng token được cắm trực tiếp vào bảng nối đa năng của VAX, vào thời điểm bo mạch hoạt động thì các VAX đã lỗi thời và chúng tôi quyết định không chi thêm kinh phí để nâng cấp toàn bộ hệ thống.

The second problem we encountered was that the network interface and the Unibus on the 11/750 were both bottlenecks [GERB87, DEWI88]. While the bandwidth of the token ring itself was 80 megabits/second, the Unibus on the 11/750 (to which the network interface was attached) has a bandwidth of only 4 megabits/second. When processing a join query without a selection predicate on either of the input relations, the Unibus became a bottleneck because the transfer rate of pages from the disk was higher than the speed of the Unibus [DEWI88]. The network interface was a bottleneck because it could only buffer two incoming packets at a time. Until one packet was transferred into the VAX’s memory, other incoming packets were rejected and had to be retransmitted by the communications protocol. While we eventually constructed an interface to the token ring that plugged directly into the backplane of the VAX, by the time the board was operational the VAX’s were obsolete and we elected not to spend additional funds to upgrade the entire system.

Vấn đề nghiêm trọng khác chúng tôi gặp phải với nguyên mẫu này là mỗi bộ xử lý chỉ có 2 megabyte bộ nhớ. Đây đặc biệt là một vấn đề vì hệ điều hành được Gamma sử dụng không cung cấp bộ nhớ ảo. Vấn đề trở nên nghiêm trọng hơn do không gian cho các bảng băm nối, không gian ngăn xếp cho các tiến trình và nhóm bộ đệm được quản lý riêng biệt để tránh xóa các trang nóng khỏi nhóm bộ đệm. Mặc dù việc các không gian này được phần mềm quản lý riêng biệt có những ưu điểm, trong một cấu hình mà bộ nhớ vốn đã hạn chế, việc cân bằng kích thước của ba nhóm bộ nhớ này tỏ ra khó khăn.

The other serious problem we encountered with this prototype was having only 2 megabytes of memory on each processor. This was especially a problem since the operating system used by Gamma does not provide virtual memory. The problem was exacerbated by the fact that space for join hash tables, stack space for processes, and the buffer pool were managed separately in order to avoid flushing hot pages from the buffer pool. While there are advantages to having these spaces managed separately by the software, in a configuration where memory is already tight, balancing the sizes of these three pools of memory proved difficult.

2.3. Phiên bản Gamma 2.0

2.3. Gamma Version 2.0

Vào mùa thu năm 1988, chúng tôi thay thế nguyên mẫu dựa trên VAX bằng một hypercube iPSC/2 32 bộ xử lý từ Intel. Mỗi bộ xử lý được cấu hình với một CPU 386, 8 megabyte bộ nhớ và một ổ đĩa MAXTOR 4380 330-megabyte (5 1/4"). Mỗi ổ đĩa có một bộ điều khiển SCSI tích hợp cung cấp một bộ đệm RAM 45 Kbyte đóng vai trò là cache đĩa trong các thao tác đọc.

In the fall of 1988, we replaced the VAX-based prototype with a 32 processor iPSC/2 hypercube from Intel. Each processor is configured with a 386 CPU, 8 megabytes of memory, and a 330-megabyte MAXTOR 4380 (5 1/4") disk drive. Each disk drive has an embedded SCSI controller which provides a 45 Kbyte RAM buffer that acts as a disk cache on read operations.

Các nút trong hypercube được liên kết với nhau để tạo thành một hypercube bằng cách sử dụng các mô-đun định tuyến VLSI tùy chỉnh. Mỗi mô-đun hỗ trợ tám¹ kênh giao tiếp song công hoàn toàn, nối tiếp, tin cậy hoạt động ở tốc độ 2.8 megabyte/giây. Các thông điệp nhỏ (<= 100 byte) được gửi dưới dạng datagram. Đối với các thông điệp lớn, phần cứng xây dựng một mạch giao tiếp giữa hai nút, qua đó toàn bộ thông điệp được truyền mà không có chi phí phụ trội của phần mềm hoặc sao chép. Sau khi thông điệp được truyền hoàn toàn, mạch được giải phóng. Độ dài của một thông điệp chỉ bị giới hạn bởi kích thước của bộ nhớ vật lý trên mỗi bộ xử lý. Bảng 1 tóm tắt thời gian truyền từ một tiến trình Gamma tới một tiến trình khác (trên hai nút hypercube khác nhau) đối với nhiều kích thước thông điệp.

The nodes in the hypercube are interconnected to form a hypercube using custom VLSI routing modules. Each module supports eight¹ full-duplex, serial, reliable communication channels operating at 2.8 megabytes/second. Small messages (<= 100 bytes) are sent as datagrams. For large messages, the hardware builds a communications circuit between the two nodes over which the entire message is transmitted without any software overhead or copying. After the message has been completely transmitted, the circuit is released. The length of a message is limited only by the size of the physical memory on each processor. Table 1 summarizes the transmission times from one Gamma process to another (on two different hypercube nodes) for a variety of message sizes.

Bảng 1

Table 1

Việc chuyển đổi phần mềm Gamma sang hypercube bắt đầu vào đầu tháng 12 năm 1988. Vì hầu hết người dùng hypercube Intel có xu hướng chạy một tiến trình duy nhất tại một thời điểm trong khi xử lý dữ liệu số, hệ điều hành do Intel cung cấp chỉ hỗ trợ một số lượng hạn chế các tiến trình nặng. Do đó, chúng tôi bắt đầu quá trình chuyển đổi bằng cách chuyển hệ điều hành của Gamma, NOSE (xem Section 3.5). Để đơn giản hóa việc chuyển đổi, chúng tôi quyết định chạy NOSE như một gói luồng bên trong một tiến trình NX/2 duy nhất nhằm tránh phải chuyển NOSE để chạy trực tiếp trên phần cứng thuần.

The conversion of the Gamma software to the hypercube began in early December 1988. Because most users of the Intel hypercube tend to run a single process at a time while crunching numerical data, the operating system provided by Intel supports only a limited number of heavy weight processes. Thus, we began the conversion process by porting Gamma’s operating system, NOSE (see Section 3.5). In order to simplify the conversion, we elected to run NOSE as a thread package inside a single NX/2 process in order to avoid having to port NOSE to run on the bare hardware directly.

Sau khi NOSE được chạy, chúng tôi bắt đầu chuyển đổi phần mềm Gamma. Quá trình này mất 4-6 tháng-người nhưng kéo dài khoảng 6 tháng vì, trong quá trình chuyển đổi, chúng tôi phát hiện rằng giao diện giữa bộ điều khiển đĩa SCSI và bộ nhớ không thể truyền các khối đĩa lớn hơn 1024 byte (cạm bẫy của việc là một địa điểm thử nghiệm beta). Phần lớn việc chuyển đổi phần mềm Gamma gần như là đơn giản vì, bằng cách chuyển NOSE trước, những khác biệt giữa hai hệ thống trong việc khởi tạo truyền đĩa và thông điệp đã hoàn toàn được ẩn khỏi phần mềm Gamma. Khi chuyển mã sang 386, chúng tôi đã phát hiện một số lỗi ẩn trong phiên bản VAX của mã vì VAX không bắt lỗi khi một con trỏ null bị tham chiếu. Vấn đề lớn nhất mà chúng tôi gặp phải là các nút trên máy tính đa xử lý VAX được đánh số bắt đầu từ 1 trong khi hypercube sử dụng 0 làm địa chỉ logic của nút đầu tiên. Mặc dù chúng tôi nghĩ rằng việc thực hiện các thay đổi cần thiết sẽ tẻ nhạt nhưng đơn giản, chúng tôi đã đi được khoảng một nửa quá trình chuyển đổi trước khi nhận ra rằng chúng tôi phải tìm và thay đổi mọi vòng lặp "for" trong hệ thống mà chỉ số vòng lặp cũng được sử dụng làm địa chỉ của máy mà một thông điệp được gửi tới. Mặc dù điều này nghe có vẻ ngớ ngẩn hiện nay, chúng tôi đã mất vài tuần để tìm tất cả các vị trí cần thay đổi. Nhìn lại, chúng tôi nên để NOSE che giấu những khác biệt giữa hai lược đồ địa chỉ.

¹ On configurations with a mix of compute and I/O nodes, one of the 8 channels is dedicated for communication to the I/O subsystem.

Tuy nhiên, từ góc nhìn của hệ thống cơ sở dữ liệu, có một số lĩnh vực mà Intel có thể cải thiện thiết kế của iPSC/2. Trước hết, nên cung cấp một cơ chế tiến trình nhẹ như một phương án thay thế cho NX/2. Mặc dù điều này gần như chắc chắn sẽ làm tăng thời gian cần thiết để thực hiện việc chuyển đổi, về lâu dài chúng tôi có thể tránh được việc duy trì NOSE. Một vấn đề nghiêm trọng hơn nhiều với phiên bản hiện tại của hệ thống là bộ điều khiển đĩa không thực hiện các truyền DMA trực tiếp vào bộ nhớ. Thay vào đó, khi một khối được đọc từ đĩa, bộ điều khiển đĩa thực hiện một truyền DMA vào một FIFO 4K byte. Khi FIFO đầy một nửa, CPU bị ngắt và nội dung của FIFO được sao chép vào vị trí thích hợp trong bộ nhớ.¹ Mặc dù một lệnh khối được sử dụng cho thao tác sao chép, chúng tôi đã đo được rằng khoảng 10% số chu kỳ CPU khả dụng bị lãng phí để thực hiện thao tác sao chép. Ngoài ra, CPU bị ngắt 13 lần trong quá trình truyền một khối 8 Kbyte, một phần vì sử dụng bộ điều khiển đĩa SCSI và một phần vì FIFO giữa bộ điều khiển đĩa và bộ nhớ.

Once NOSE was running, we began converting the Gamma software. This process took 4-6 man months but lasted about 6 months as, in the process of the conversion, we discovered that the interface between the SCSI disk controller and memory was not able to transfer disk blocks larger than 1024 bytes (the pitfall of being a beta test site). For the most part the conversion of the Gamma software was almost trivial as, by porting NOSE first, the differences between the two systems in initiating disk and message transfers were completely hidden from the Gamma software. In porting the code to the 386, we did discover a number of hidden bugs in the VAX version of the code as the VAX does not trap when a null pointer is dereferenced. The biggest problem we encountered was that nodes on the VAX multicomputer were numbered beginning with 1 while the hypercube uses 0 as the logical address of the first node. While we thought that making the necessary changes would be tedious but straightforward, we were about half way through the port before we realized that we would have to find and change every "for" loop in the system in which the loop index was also used as the address of the machine to which a message was to be set. While this sounds silly now, it took us several weeks to find all the places that had to be changed. In retrospect, we should have made NOSE mask the differences between the two addressing schemes.

Nothing here.

From a database system perspective, however, there are a number of areas in which Intel could improve the design of the iPSC/2. First, a light-weight process mechanism should be provided as an alternative to NX/2. While this would have almost certainly increased the time required to do the port, in the long run we could have avoided maintaining NOSE. A much more serious problem with the current version of the system is that the disk controller does not perform DMA transfers directly into memory. Rather, as a block is read from the disk, the disk controller does a DMA transfer into a 4K byte FIFO. When the FIFO is half full, the CPU is interrupted and the contents of the FIFO are copied into the appropriate location in memory.$^2$ While a block instruction is used for the copy operation, we have measured that about 10% of the available CPU cycles are being wasted doing the copy operation. In addition, the CPU is interrupted 13 times during the transfer of one 8 Kbyte block partially because a SCSI disk controller is used and partially because of the FIFO between the disk controller and memory.

Nothing here.

3 Software Architecture of Gamma

3 Kiến trúc phần mềm của Gamma

In this section, we present an overview of Gamma’s software architecture and describe the techniques that Gamma employs for executing queries in a dataflow fashion. We begin by describing the alternative storage structures provided by the Gamma software. Next, the overall system architecture is described from the top down. After describing the overall process structure, we illustrate the operation of the system by describing the interaction of the

Trong phần này, chúng tôi trình bày tổng quan về kiến trúc phần mềm của Gamma và mô tả các kỹ thuật mà Gamma sử dụng để thực thi các truy vấn theo kiểu luồng dữ liệu. Chúng tôi bắt đầu bằng việc mô tả các cấu trúc lưu trữ thay thế được cung cấp bởi phần mềm Gamma. Tiếp theo, kiến trúc hệ thống tổng thể được mô tả từ trên xuống dưới. Sau khi mô tả cấu trúc tiến trình tổng thể, chúng tôi minh họa hoạt động của hệ thống bằng cách mô tả sự tương tác của

$^2$ Intel was forced to use such a design because the I/O system was added after the system had been completed and the only way of doing I/O was by using a empty socket on the board which did not have DMA access to memory.

thuộc tính phân vùng.

processes during the execution of several different queries. A detailed presentation of the techniques used to control the execution of complex queries is presented in Section 3.4. This is followed by an example which illustrates the execution of a multioperator query. Finally, we briefly describe WiSS, the storage system used to provide low level database services, and NOSE, the underlying operating system.

Khi một truy vấn đang được tối ưu hóa, thông tin phân vùng cho mỗi quan hệ nguồn trong truy vấn được đưa vào kế hoạch truy vấn do bộ tối ưu hóa truy vấn tạo ra. Trong trường hợp các quan hệ được phân vùng theo băm và theo khoảng, thông tin phân vùng này được bộ lập lịch truy vấn (được thảo luận bên dưới) sử dụng để hạn chế số lượng bộ xử lý tham gia vào việc thực thi các truy vấn chọn trên thuộc tính phân vùng. Ví dụ, nếu quan hệ X được phân vùng theo băm trên thuộc tính y, có thể hướng các thao tác chọn với các vị từ có dạng "X.y = Constant" đến một site duy nhất; tránh sự tham gia của bất kỳ site nào khác trong việc thực thi truy vấn. Trong trường hợp các quan hệ được phân vùng theo khoảng, bộ lập lịch truy vấn có thể hạn chế việc thực thi truy vấn chỉ đến những bộ xử lý có khoảng của chúng chồng lấp với khoảng của vị từ chọn (có thể là vị từ bằng hoặc vị từ khoảng).

3.1. Gamma Storage Organizations

Nhìn lại, chúng tôi đã mắc một sai lầm nghiêm trọng khi chọn phân cụm phân tán tất cả các quan hệ trên tất cả các nút có đĩa. Một phương pháp tốt hơn nhiều, như được đề xuất trong [COPE88], là sử dụng "độ nóng" của một quan hệ để xác định mức độ mà quan hệ được phân cụm phân tán. Đáng tiếc, việc bổ sung khả năng như vậy vào phần mềm Gamma tại thời điểm này sẽ đòi hỏi một nỗ lực khá lớn - một nỗ lực mà chúng tôi khó có khả năng thực hiện.

Relations in Gamma are horizontally partitioned [RIES78] across all disk drives in the system. The key idea behind horizontally partitioning each relation is to enable the database software to exploit all the I/O bandwidth provided by the hardware. By declustering$^3$ the tuples of a relation, the task of parallelizing a selection/scan operator becomes trivial as all that is required is to start a copy of the operator on each processor.

3.2. Cấu trúc tiến trình Gamma

The query language of Gamma provides the user with three alternative declustering strategies: round robin, hashed, and range partitioned. With the first strategy, tuples are distributed in a round-robin fashion among the disk drives. This is the default strategy and is used for all relations created as the result of a query. If the hashed partitioning strategy is selected, a randomizing function is applied to the key attribute of each tuple (as specified in the partition command for the relation) to select a storage unit. In the third strategy the user specifies a range of key values for each site. For example, with a 4 disk system, the command partition employee on emp_id (100, 300, 1000) would result in the distribution of tuples shown in Table 2. The partitioning information for each relation is stored in the database catalog. For range and hash-partitioned relations, the name of the partitioning attribute is also kept and, in the case of range-partitioned relations, the range of values of the partitioning attribute for each site (termed a range table).

Cấu trúc tổng thể của các tiến trình khác nhau tạo thành phần mềm Gamma được thể hiện trong Hình 2. Vai trò của mỗi tiến trình được mô tả ngắn gọn bên dưới. Hoạt động của cơ chế phát hiện và phục hồi bế tắc phân tán được trình bày trong các Mục 5.1 và 5.2. Tại thời điểm khởi tạo hệ thống, một tiến trình daemon UNIX cho Trình quản lý Catalog (CM) được khởi tạo cùng với một tập hợp các Tiến trình Lập lịch, một tập hợp các Tiến trình Toán tử, Tiến trình Phát hiện Bế tắc và Tiến trình Phục hồi.

Trình quản lý Catalog

An Example Range Table Table 2

Chức năng của Trình quản lý Catalog là hoạt động như một kho lưu trữ trung tâm cho tất cả thông tin lược đồ khái niệm và nội bộ của mỗi cơ sở dữ liệu. Thông tin lược đồ được tải vào bộ nhớ khi một cơ sở dữ liệu được mở lần đầu. Vì nhiều người dùng có thể mở cùng một cơ sở dữ liệu đồng thời và vì mỗi người dùng có thể cư trú trên một máy khác với máy mà Trình quản lý Catalog đang thực thi, Trình quản lý Catalog chịu trách nhiệm đảm bảo tính nhất quán giữa các bản sao được cache bởi mỗi người dùng.

Once a relation has been partitioned, Gamma provides the normal collection of relational database system access methods including both clustered and non-clustered indices. When the user requests that an index be created on a relation, the system automatically creates an index on each fragment of the relation. Unlike VSAM [WAGN73] and the Tandem file system [ENSC85], Gamma does not require the clustered index for a relation to be constructed on

Trình quản lý truy vấn

$^3$ Declustering is another term for horizontal partitioning that was coined by the Bubba project [LIVN87].

Một tiến trình trình quản lý truy vấn được liên kết với mỗi người dùng Gamma đang hoạt động. Trình quản lý truy vấn chịu trách nhiệm cache thông tin lược đồ cục bộ, cung cấp giao diện cho các truy vấn đặc biệt sử dụng gdl (biến thể của Quel của chúng tôi [STON76]), phân tích cú pháp truy vấn, tối ưu hóa và biên dịch.

the partitioning attribute.

Các tiến trình lập lịch

As a query is being optimized, the partitioning information for each source relation in the query is incorporated into the query plan produced by the query optimizer. In the case of hash and range-partitioned relations, this partitioning information is used by the query scheduler (discussed below) to restrict the number of processors involved in the execution of selection queries on the partitioning attribute. For example, if relation X is hash partitioned on attribute y, it is possible to direct selection operations with predicates of the form "X.y = Constant" to a single site; avoiding the participation of any other sites in the execution of the query. In the case of range-partitioned relations, the query scheduler can restrict the execution of the query to only those processors whose ranges overlap the range of the selection predicate (which may be either an equality or range predicate).

Trong khi thực thi, mỗi truy vấn đa site được điều khiển bởi một tiến trình lập lịch. Tiến trình này chịu trách nhiệm kích hoạt các Tiến trình Toán tử được sử dụng để thực thi các nút của một cây truy vấn đã biên dịch. Các tiến trình lập lịch có thể chạy trên bất kỳ bộ xử lý nào, đảm bảo rằng không có bộ xử lý nào trở thành nút thắt cổ chai. Tuy nhiên, trong thực tế, các tiến trình lập lịch tiêu thụ hầu như không có tài nguyên và có thể chạy một số lượng lớn chúng trên một bộ xử lý duy nhất. Một tiến trình điều phối tập trung được sử dụng để gán các tiến trình lập lịch cho các truy vấn. Những truy vấn mà bộ tối ưu hóa có thể phát hiện là truy vấn một site được gửi trực tiếp đến nút thích hợp để thực thi, bỏ qua tiến trình lập lịch.

In retrospect, we made a serious mistake in choosing to decluster all relations across all nodes with disks. A much better approach, as proposed in [COPE88], is to use the "heat" of a relation to determine the degree to which the relation is declustered. Unfortunately, to add such a capability to the Gamma software at this point in time would require a fairly major effort - one we are not likely to undertake.

3.2. Gamma Process Structure

Tiến trình toán tử

The overall structure of the various processes that form the Gamma software is shown in Figure 2. The role of each process is described briefly below. The operation of the distributed deadlock detection and recovery mechanism are presented in Sections 5.1 and 5.2. At system initialization time, a UNIX daemon process for the Catalog Manager (CM) is initiated along with a set of Scheduler Processes, a set of Operator Processes, the Deadlock Detection Process, and the Recovery Process.

Đối với mỗi toán tử trong một cây truy vấn, ít nhất một Tiến trình Toán tử được sử dụng tại mỗi bộ xử lý tham gia vào việc thực thi toán tử đó. Các toán tử này được chuẩn bị tại thời điểm khởi tạo hệ thống nhằm tránh chi phí phụ trội của việc khởi động các tiến trình tại thời điểm thực thi truy vấn (các tiến trình bổ sung có thể được fork khi cần). Cấu trúc của một tiến trình toán tử và ánh xạ các toán tử quan hệ tới các tiến trình toán tử được thảo luận chi tiết hơn bên dưới. Khi một bộ lập lịch muốn khởi động một toán tử mới trên một nút, nó gửi một yêu cầu đến một cổng truyền thông đặc biệt được gọi là cổng "new task". Khi một yêu cầu được nhận trên cổng này, một tiến trình toán tử nhàn rỗi được gán cho yêu cầu và cổng truyền thông của tiến trình toán tử này được trả về cho tiến trình lập lịch yêu cầu.

Catalog Manager The function of the Catalog Manager is to act as a central repository of all conceptual and internal schema information for each database. The schema information is loaded into memory when a database is first opened. Since multiple users may have the same database open at once and since each user may reside on a machine other than the one on which the Catalog Manager is executing, the Catalog Manager is responsible for insuring consistency among the copies cached by each user.

3.3. Tổng quan về thực thi truy vấn

Query Manager One query manager process is associated with each active Gamma user. The query manager is responsible for caching schema information locally, providing an interface for ad-hoc queries using gdl (our variant of Quel [STON76]), query parsing, optimization, and compilation.

Các giao diện truy vấn đặc biệt và truy vấn nhúng

Scheduler Processes While executing, each multisite query is controlled by a scheduler process. This process is responsible for activating the Operator Processes used to execute the nodes of a compiled query tree. Scheduler processes can be run on any processor, insuring that no processor becomes a bottleneck. In practice, however, scheduler processes consume almost no resources and it is possible to run a large number of them on a single processor. A centralized dispatching process is used to assign scheduler processes to queries. Those queries that the optimizer can detect to be single-site queries are sent directly to the appropriate node for execution, by-passing the scheduling process.

Hai giao diện cho Gamma có sẵn: một ngôn ngữ truy vấn đặc biệt và một giao diện ngôn ngữ truy vấn nhúng trong đó các truy vấn có thể được nhúng vào một chương trình C. Khi người dùng gọi giao diện truy vấn đặc biệt, một tiến trình Trình quản lý truy vấn (QM) được khởi động và ngay lập tức kết nối với tiến trình CM thông qua cơ chế socket Internet UNIX. Khi giao diện truy vấn đã biên dịch được sử dụng, bộ tiền xử lý dịch mỗi truy vấn nhúng thành một kế hoạch truy vấn đã biên dịch được chương trình gọi tại thời gian chạy. Một cơ chế truyền các tham số từ chương trình C đến các kế hoạch truy vấn đã biên dịch tại thời gian chạy cũng được cung cấp.

Gamma Process Structure Figure 2

Thực thi truy vấn

Operator Process For each operator in a query tree, at least one Operator Process is employed at each processor participating in the execution of the operator. These operators are primed at system initialization time in order to avoid the overhead of starting processes at query execution time (additional processes can be forked as needed). The structure of an operator process and the mapping of relational operators to operator processes is discussed in more detail below. When a scheduler wishes to start a new operator on a node, it sends a request to a special communications port known as the "new task" port. When a request is received on this port, an idle operator process is assigned to the request and the communications port of this operator process is returned to the requesting scheduler process.

Gamma sử dụng các kỹ thuật quan hệ truyền thống cho việc phân tích cú pháp truy vấn, tối ưu hóa [SELI79, JARK84], và sinh mã. Quá trình tối ưu hóa được đơn giản hóa phần nào vì Gamma chỉ sử dụng các thuật toán dựa trên băm cho các phép nối và các phép toán phức tạp khác. Các truy vấn được biên dịch thành một cây toán tử sâu trái. Tại thời điểm thực thi, mỗi toán tử được thực thi bởi một hoặc nhiều tiến trình toán tử tại mỗi site tham gia.

3.3. An Overview of Query Execution

Khi thiết kế bộ tối ưu hóa cho phiên bản VAX của Gamma, tập các kế hoạch truy vấn khả dĩ được bộ tối ưu hóa xem xét bị giới hạn chỉ còn các cây sâu trái vì chúng tôi cho rằng không có đủ bộ nhớ để hỗ trợ các kế hoạch sâu phải hoặc dạng bụi rậm. Bằng cách sử dụng kết hợp các cây truy vấn sâu trái và các thuật toán nối dựa trên băm, chúng tôi có thể đảm bảo rằng không quá hai phép toán nối từng hoạt động đồng thời và do đó có thể tối đa hóa lượng bộ nhớ vật lý có thể được cấp phát cho mỗi toán tử nối. Vì giới hạn bộ nhớ này thực sự chỉ là một đặc tính của nguyên mẫu VAX, gần đây chúng tôi đã bắt đầu khảo sát các ảnh hưởng về hiệu năng của các kế hoạch truy vấn sâu phải và dạng bụi rậm [SCHN89b].

Ad-hoc and Embedded Query Interfaces

Như đã thảo luận trong Section 3.1, trong quá trình tối ưu hóa một truy vấn, bộ tối ưu hóa truy vấn nhận biết rằng một số truy vấn nhất định chỉ có thể được hướng tới một tập con các nút trong hệ thống. Trong trường hợp truy vấn một site, truy vấn được QM gửi trực tiếp đến bộ xử lý thích hợp để thực thi. Trong trường hợp truy vấn nhiều site, bộ tối ưu hóa thiết lập một kết nối tới một tiến trình scheduler nhàn rỗi thông qua một tiến trình dispatcher tập trung. Tiến trình dispatcher, bằng cách kiểm soát số lượng scheduler đang hoạt động, triển khai một cơ chế kiểm soát tải đơn giản. Khi đã thiết lập kết nối với một tiến trình scheduler, QM gửi truy vấn đã biên dịch đến tiến trình scheduler và chờ truy vấn hoàn thành thực thi. Tiến trình scheduler, lần lượt, kích hoạt các tiến trình toán tử tại mỗi bộ xử lý truy vấn được chọn để thực thi toán tử. Cuối cùng, QM đọc các kết quả của truy vấn và trả chúng thông qua giao diện truy vấn ad-hoc cho người dùng hoặc thông qua giao diện truy vấn nhúng tới chương trình từ đó truy vấn được khởi tạo.

Two interfaces to Gamma are available: an ad-hoc query language and an embedded query language interface in which queries can be embedded in a C program. When a user invokes the ad-hoc query interface, a Query Manager (QM) process is started which immediately connects itself to the CM process through the UNIX Internet socket mechanism. When the compiled query interface is used, the preprocessor translates each embedded query into a compiled query plan which is invoked at run-time by the program. A mechanism for passing parameters from the C program to the compiled query plans at run time is also provided.

3.4. Cấu trúc Toán tử và Tiến trình

Query Execution

Các thuật toán cho tất cả các toán tử quan hệ được viết như thể chúng sẽ được chạy trên một bộ xử lý duy nhất. Như được trình bày trong Figure 3, đầu vào của một Tiến trình Toán tử là một luồng các tuple và đầu ra là một luồng các tuple được phân kênh thông qua một cấu trúc mà chúng tôi gọi là bảng phân tách. Khi tiến trình bắt đầu thực thi, nó liên tục đọc các tuple từ luồng đầu vào, xử lý từng tuple, và sử dụng một bảng phân tách để định tuyến tuple kết quả tới tiến trình được chỉ ra trong bảng phân tách.¹ Khi tiến trình phát hiện kết thúc luồng đầu vào, trước tiên nó đóng các luồng đầu ra rồi gửi một thông điệp điều khiển tới tiến trình scheduler của nó cho biết rằng nó đã hoàn thành thực thi. Việc đóng các luồng đầu ra có tác dụng phụ là gửi các thông điệp "end of stream" tới từng tiến trình đích.

Gamma uses traditional relational techniques for query parsing, optimization [SELI79, JARK84], and code generation. The optimization process is somewhat simplified as Gamma only employs hash-based algorithms for joins and other complex operations. Queries are compiled into a left-deep tree of operators. At execution time, each operator is executed by one or more operator processes at each participating site.

Figure 3

In designing the optimizer for the VAX version of Gamma, the set of possible query plans considered by the optimizer was restricted to only left-deep trees because we felt that there was not enough memory to support right-deep or bushy plans. By using a combination of left-deep query trees and hash-based join algorithms, we were able to insure that no more than two join operations were ever active simultaneously and hence were able to maximize the amount of physical memory which could be allocated to each join operator. Since this memory limitation was really only an artifact of the VAX prototype, we have recently begun to examine the performance implications of right deep and bushy query plans [SCHN89b].

Bảng phân tách định nghĩa một ánh xạ các giá trị tới một tập các tiến trình đích. Gamma sử dụng ba kiểu bảng phân tách khác nhau tùy thuộc vào kiểu thao tác đang được thực hiện [DEWI86]. Là một ví dụ về một dạng bảng phân tách, hãy xem xét việc sử dụng bảng phân tách được trình bày trong Figure 4 kết hợp với việc thực thi một phép nối sử dụng 4 bộ xử lý. Mỗi tiến trình tạo ra các tuple cho phép nối sẽ áp dụng một hàm băm cho thuộc tính nối của mỗi tuple đầu ra để tạo ra một giá trị trong khoảng từ 0 đến 3. Giá trị này sau đó được sử dụng làm chỉ mục vào bảng phân tách để lấy địa chỉ của tiến trình đích sẽ nhận tuple.

As discussed in Section 3.1, in the process of optimizing a query, the query optimizer recognizes that certain queries can be directed to only a subset of the nodes in the system. In the case of a single site query, the query is sent directly by the QM to the appropriate processor for execution. In the case of a multiple site query, the optimizer establishes a connection to an idle scheduler process through a centralized dispatcher process. The dispatcher process, by controlling the number of active schedulers, implements a simple load control mechanism. Once it has established a connection with a scheduler process, the QM sends the compiled query to the scheduler process and waits for the query to complete execution. The scheduler process, in turn, activates operator processes at each query processor selected to execute the operator. Finally, the QM reads the results of the query and returns them through the ad-hoc query interface to the user or through the embedded query interface to the program from which the query was initiated.

3.4. Operator and Process Structure

Một Ví dụ về Bảng Phân Tách Figure 4

The algorithms for all the relational operators are written as if they were to be run on a single processor. As shown in Figure 3, the input to an Operator Process is a stream of tuples and the output is a stream of tuples that is demultiplexed through a structure we term a split table. Once the process begins execution, it continuously reads tuples from its input stream, operates on each tuple, and uses a split table to route the resulting tuple to the process indicated in the split table.$^4$ When the process detects the end of its input stream, it first closes the output streams and then sends a control message to its scheduler process indicating that it has completed execution. Closing the output streams has the side effect of sending "end of stream" messages to each of the destination processes.

Một Ví dụ

Figure.

Là một ví dụ về cách các truy vấn được thực thi, hãy xem xét truy vấn được trình bày trong Figure 5. Trong Figure 6, các tiến trình được sử dụng để thực thi truy vấn được trình bày cùng với luồng dữ liệu giữa các tiến trình khác nhau cho một cấu hình Gamma bao gồm hai bộ xử lý có đĩa và hai bộ xử lý không có đĩa. Vì hai quan hệ đầu vào A và B được phân vùng trên các đĩa gắn với các bộ xử lý P1 và P2, các toán tử chọn và quét được khởi tạo trên cả hai bộ xử lý P1 và P2. Các bảng phân tách cho cả toán tử chọn và quét đều chứa hai mục nhập vì hai bộ xử lý đang được sử dụng cho thao tác nối. Các bảng phân tách cho mỗi phép chọn và quét là giống hệt nhau - định tuyến các tuple có giá trị thuộc tính nối băm thành 0 (các đường nét đứt) tới P3 và các tuple có giá trị băm thành 1 (các đường liền) tới P4. Toán tử nối thực thi theo hai giai đoạn. Trong giai đoạn đầu tiên, được gọi là giai đoạn Building, các tuple từ quan hệ bên trong (A trong ví dụ này) được chèn vào một bảng băm nằm trong bộ nhớ bằng cách băm trên giá trị thuộc tính nối. Sau khi giai đoạn đầu tiên hoàn thành, giai đoạn probing của phép nối được khởi tạo, trong đó các tuple từ quan hệ bên ngoài được sử dụng để thăm dò bảng băm nhằm tìm các tuple khớp.¹ Vì quan hệ kết quả được phân vùng trên hai đĩa, bảng phân tách cho mỗi toán tử nối chứa hai mục nhập và các tuple của C được phân phối theo cách round-robin giữa P1 và P2.

Figure 3

Figure 5

The split table defines a mapping of values to a set of destination processes. Gamma uses three different types of split tables depending on the type of operation being performed [DEWI86]. As an example of one form of split table, consider the use of the split table shown in Figure 4 in conjunction with the execution of a join operation using 4 processors. Each process producing tuples for the join will apply a hash function to the join attribute of each output tuple to produce a value between 0 and 3. This value is then used as an index into the split table to obtain the address of the destination process that should receive the tuple.

Figure 6

\footnotetext{4 Tuples are actually sent as 8K byte batches, except for the last batch.}

Một trong những vấn đề chính với nguyên mẫu DIRECT là mỗi trang dữ liệu được xử lý đều yêu cầu ít nhất một thông điệp điều khiển đến một bộ lập lịch tập trung. Trong Gamma, nút thắt này hoàn toàn được tránh. Trên thực tế, số lượng thông điệp điều khiển cần thiết để thực thi một truy vấn xấp xỉ bằng ba lần số lượng toán tử trong truy vấn nhân với số lượng bộ xử lý được sử dụng để thực thi mỗi toán tử. Ví dụ, hãy xem Hình 7, trong đó mô tả luồng điều khiển của các thông điệp điều khiển¹ từ một tiến trình bộ lập lịch đến các tiến trình trên các bộ xử lý P1 và P3 trong Hình 6 (một tập thông điệp giống hệt sẽ được truyền từ bộ lập lịch đến P2 và P4). Bộ lập lịch bắt đầu bằng cách khởi tạo giai đoạn xây dựng của phép nối và toán tử chọn trên quan hệ A. Khi cả hai toán tử này hoàn thành, bộ lập lịch tiếp theo khởi tạo toán tử lưu trữ, giai đoạn thăm dò của phép nối và việc quét quan hệ B. Khi mỗi toán tử này hoàn thành, một thông điệp kết quả được trả về cho người dùng.

Hình 7

An Example Split Table Figure 4

3.5. Hệ điều hành và Hệ thống lưu trữ

An Example

Gamma được xây dựng trên một hệ điều hành được thiết kế đặc biệt để hỗ trợ các hệ quản trị cơ sở dữ liệu. NOSE cung cấp nhiều tiến trình nhẹ với bộ nhớ dùng chung. Một chính sách lập lịch không chiếm quyền được sử dụng để giúp ngăn chặn các đoàn xe [BLAS79] xảy ra. NOSE cung cấp giao tiếp giữa các tiến trình NOSE bằng cách sử dụng phần cứng truyền thông điệp đáng tin cậy của siêu khối Intel iPSC/2. Các dịch vụ file trong NOSE dựa trên Wisconsin Storage System (WiSS) [CHOU85]. Các phần tới hạn của WiSS được bảo vệ bằng cơ chế semaphore do NOSE cung cấp.

As an example of how queries are executed, consider the query shown in Figure 5. In Figure 6, the processes used to execute the query are shown along with the flow of data between the various processes for a Gamma configuration consisting of two processors with disks and two processors without disks. Since the two input relations A and B are partitioned across the disks attached to processors P1 and P2, selection and scan operators are initiated on both processors P1 and P2. The split tables for both the select and scan operators each contain two entries since two processors are being used for the join operation. The split tables for each selection and scan are identical - routing tuples whose join attribute values hash to 0 (dashed lines) to P3 and those which hash to 1 (solid lines) to P4. The join operator executes in two phases. During the first phase, termed the Building phase, tuples from the inner relation (A in this example) are inserted into a memory-resident hash table by hashing on the join attribute value. After the first phase has completed, the probing phase of the join is initiated in which tuples from the outer relation are used to probe the hash table for matching tuples.$^5$ Since the result relation is partitioned across two disks, the split table for each join operator contains two entries and tuples of C are distributed in a round-robin fashion among P1 and P2.

Các dịch vụ file do WiSS cung cấp bao gồm các file tuần tự có cấu trúc, các file luồng byte như trong UNIX, các chỉ mục B+, các mục dữ liệu dài, một tiện ích sắp xếp và một cơ chế quét. Một file tuần tự là một chuỗi các bản ghi. Các bản ghi có thể thay đổi về độ dài (lên đến một trang), và có thể được chèn và xóa tại các vị trí tùy ý trong một file tuần tự. Tùy chọn, mỗi file có thể có một hoặc nhiều chỉ mục liên kết, ánh xạ các giá trị khóa tới các định danh bản ghi của các bản ghi trong file chứa giá trị khớp. Một thuộc tính được lập chỉ mục có thể được chỉ định làm thuộc tính phân cụm cho file. Cơ chế quét tương tự như cơ chế được System R’s RSS [ASTR76] cung cấp, ngoại trừ việc các vị từ được trình tối ưu hóa truy vấn biên dịch thành ngôn ngữ máy 386 để tối đa hóa hiệu năng.

Figure.

Nothing here.

Figure 5

Nothing here.

$^5$ This is actually a description of the simple hash join algorithm. The operation of the hybrid hash join algorithm is contained in Section 4.

Nothing here.

Figure 6

Nothing here.

One of the main problems with the DIRECT prototype was that every data page processed required at least one control message to a centralized scheduler. In Gamma this bottleneck is completely avoided. In fact, the number of control messages required to execute a query is approximately equal to three times the number of operators in the query times the number of processors used to execute each operator. As an example, consider Figure 7 which depicts the flow of control messages$^6$ from a scheduler process to the processes on processors P1 and P3 in Figure 6 (an identical set of messages would flow from the scheduler to P2 and P4). The scheduler begins by initiating the building phase of the join and the selection operator on relation A. When both these operators have completed, the scheduler next initiates the store operator, the probing phase of the join, and the scan of relation B. When each of these operators has completed, a result message is returned to the user.

Nothing here.

\footnotetext{ $^6$ The "Initiate" message is sent to a "new operator" port on each processor. A dispatching processes accepts incoming messages on this port and assigns the operator to a process. The process which is assigned, replies to the scheduler with an "ID" message which indicates the private port number of the operator process. Future communications to the operator by the scheduler use this private port number. }

Nothing here.

Figure 7

Nothing here.

3.5. Operating and Storage System

Nothing here.

Gamma is built on top of an operating system designed specifically for supporting database management systems. NOSE provides multiple, lightweight processes with shared memory. A non-preemptive scheduling policy is used to help prevent convoys [BLAS79] from occurring. NOSE provides communications between NOSE processes using the reliable message passing hardware of the Intel iPSC/2 hypercube. File services in NOSE are based on the Wisconsin Storage System (WiSS) [CHOU85]. Critical sections of WiSS are protected using the semaphore mechanism provided by NOSE.

Nothing here.

The file services provided by WiSS include structured sequential files, byte-stream files as in UNIX, B+ indices, long data items, a sort utility, and a scan mechanism. A sequential file is a sequence of records. Records may vary in length (up to one page in length), and may be inserted and deleted at arbitrary locations within a sequential file. Optionally, each file may have one or more associated indices which map key values to the record identifiers of the records in the file that contain a matching value. One indexed attribute may be designated as a clustering attribute for the file. The scan mechanism is similar to that provided by System R’s RSS [ASTR76] except that the predicates are compiled by the query optimizer into 386 machine language to maximize performance.

Nothing here.

4 Query Processing Algorithms

4 Các thuật toán xử lý truy vấn

4.1. Selection Operator

4.1. Toán tử Selection

Since all relations are declustered over multiple disk drives, parallelizing the selection operation involves simply initiating a selection operator on the set of relevant nodes with disks. When the predicate in the selection clause is on the partitioning attribute of the relation and the relation is hash or range partitioned, the scheduler can direct the selection operator to a subset of the nodes. If either the relation is round-robin partitioned or the selection predicate is not on the partitioning attribute, a selection operator must be initiated on all nodes over which the relation is declustered. To enhance performance, Gamma employs a one page read-ahead mechanism when scanning the pages of a file sequentially or through a clustered index. This mechanism enables the processing of one page to be overlapped with the I/O for the subsequent page.

Vì tất cả các quan hệ đều được giải cụm trên nhiều ổ đĩa, việc song song hóa thao tác selection chỉ đơn giản là khởi tạo một toán tử selection trên tập các nút liên quan có đĩa. Khi vị từ trong mệnh đề selection nằm trên thuộc tính phân vùng của quan hệ và quan hệ được phân vùng bằng hash hoặc theo khoảng, bộ lập lịch có thể điều hướng toán tử selection đến một tập con các nút. Nếu quan hệ được phân vùng round-robin hoặc vị từ selection không nằm trên thuộc tính phân vùng, một toán tử selection phải được khởi tạo trên tất cả các nút mà quan hệ được giải cụm. Để cải thiện hiệu năng, Gamma sử dụng một cơ chế đọc trước một trang khi quét các trang của một file theo tuần tự hoặc thông qua một chỉ mục phân cụm. Cơ chế này cho phép việc xử lý một trang được chồng lấp với thao tác I/O của trang tiếp theo.

4.2. Join Operator

4.2. Toán tử Join

The multiprocessor join algorithms provided by Gamma are based on concept of partitioning the two relations to be joined into disjoint subsets called buckets [GOOD81, KITS83, BRAT84]. by applying a hash function to the join attribute of each tuple. The partitioned buckets represent disjoint subsets of the original relations and have the important characteristic that all tuples with the same join attribute value are in the same bucket. We have implemented parallel versions of four join algorithms on the Gamma prototype: sort-merge, Grace [KITS83], Simple [DEWI84], and Hybrid [DEWI84]. While all four algorithms employ this concept of hash-based partitioning, the actual join computation depends on the algorithm. The parallel hybrid join algorithm is described in the following section. Additional information on all four parallel algorithms and their relative performance can be found in [SCHN89a]. Since this study found that the Hybrid hash join almost always provides the best performance, it is now the default algorithm in Gamma and is described in more detail in the following section. Since these hash-based join algorithms cannot be used to execute non-equijoin operations, such operations are not currently supported. To remedy this situation, we are in the process of designing a parallel non-equijoin algorithm for Gamma.

Các thuật toán join đa bộ xử lý do Gamma cung cấp dựa trên khái niệm phân vùng hai quan hệ cần được join thành các tập con rời nhau gọi là buckets [GOOD81, KITS83, BRAT84]. bằng cách áp dụng một hàm hash lên thuộc tính join của mỗi bộ. Các bucket đã được phân vùng biểu diễn các tập con rời nhau của các quan hệ ban đầu và có đặc tính quan trọng là tất cả các bộ có cùng giá trị thuộc tính join đều nằm trong cùng một bucket. Chúng tôi đã triển khai các phiên bản song song của bốn thuật toán join trên nguyên mẫu Gamma: sort-merge, Grace [KITS83], Simple [DEWI84], và Hybrid [DEWI84]. Mặc dù cả bốn thuật toán đều sử dụng khái niệm phân vùng dựa trên hash này, phép tính join thực tế phụ thuộc vào thuật toán. Thuật toán join hybrid song song được mô tả trong phần tiếp theo. Thông tin bổ sung về cả bốn thuật toán song song và hiệu năng tương đối của chúng có thể được tìm thấy trong [SCHN89a]. Vì nghiên cứu này cho thấy Hybrid hash join gần như luôn cung cấp hiệu năng tốt nhất, nó hiện là thuật toán mặc định trong Gamma và được mô tả chi tiết hơn trong phần tiếp theo. Vì các thuật toán join dựa trên hash này không thể được sử dụng để thực thi các thao tác non-equijoin, các thao tác như vậy hiện chưa được hỗ trợ. Để khắc phục tình trạng này, chúng tôi đang trong quá trình thiết kế một thuật toán non-equijoin song song cho Gamma.

Hybrid Hash-Join

Hybrid Hash-Join

A centralized Hybrid hash-join algorithm [DEWI84] operates in three phases. In the first phase, the algorithm uses a hash function to partition the inner (smaller) relation, R, into N buckets. The tuples of the first bucket are used to build an in-memory hash table while the remaining N-1 buckets are stored in temporary files. A good hash function produces just enough buckets to ensure that each bucket of tuples will be small enough to fit entirely in main memory. During the second phase, relation S is partitioned using the hash function from step 1. Again, the last N-1 buckets are stored in temporary files while the tuples in the first bucket are used to immediately probe the in-memory hash table built during the first phase. During the third phase, the algorithm joins the remaining N-1 buckets from relation R with their respective buckets from relation S. The join is thus broken up into a series of smaller joins; each of which hopefully can be computed without experiencing join overflow. The size of the smaller relation determines the number of buckets; this calculation is independent of the size of the larger relation.

Một thuật toán Hybrid hash-join tập trung [DEWI84] hoạt động trong ba giai đoạn. Trong giai đoạn đầu tiên, thuật toán sử dụng một hàm hash để phân vùng quan hệ bên trong (nhỏ hơn), R, thành N bucket. Các bộ của bucket đầu tiên được sử dụng để xây dựng một bảng hash trong bộ nhớ trong khi N-1 bucket còn lại được lưu trong các file tạm thời. Một hàm hash tốt tạo ra vừa đủ số lượng bucket để đảm bảo rằng mỗi bucket các bộ sẽ đủ nhỏ để hoàn toàn vừa với bộ nhớ chính. Trong giai đoạn thứ hai, quan hệ S được phân vùng bằng cách sử dụng hàm hash từ bước 1. Một lần nữa, N-1 bucket cuối cùng được lưu trong các file tạm thời trong khi các bộ trong bucket đầu tiên được sử dụng để ngay lập tức dò tìm bảng hash trong bộ nhớ được xây dựng trong giai đoạn đầu tiên. Trong giai đoạn thứ ba, thuật toán join các bucket $N-1$ còn lại từ quan hệ $R$ với các bucket tương ứng của chúng từ quan hệ $S$. Do đó, phép join được chia thành một chuỗi các phép join nhỏ hơn; mỗi phép trong số đó hy vọng có thể được tính toán mà không gặp phải tràn join. Kích thước của quan hệ nhỏ hơn xác định số lượng bucket; phép tính này độc lập với kích thước của quan hệ lớn hơn.

Our parallel version of the Hybrid hash join algorithm is similar to the centralized algorithm described above. A partitioning split table first separates the joining relations into N logical buckets. The number of buckets is chosen such that the tuples corresponding to each logical bucket will fit in the aggregate memory of the joining processors. The N-1 buckets intended for temporary storage on disk are each partitioned across all available disk sites. Likewise, a joining split table will be used to route tuples to their respective joining processor (these processors do not necessarily have attached disks), thus parallelizing the joining phase. Furthermore, the partitioning of the inner relation, R, into buckets is overlapped with the insertion of tuples from the first bucket of R into memory-resident hash tables at each of the join nodes. In addition, the partitioning of the outer relation, S, into buckets is overlapped with the joining of the first bucket of S with the first bucket of R. This requires that the partitioning split table for R and S be enhanced with the joining split table as tuples in the first bucket must be sent to those processors being used to effect the join. Of course, when the remaining N-1 buckets are joined, only the joining split table will be needed. Figure 8 depicts relation R being partitioned into N buckets across k disk sites where the first bucket is to be joined on m processors (m may be less than, equal to, or greater than k).

Phiên bản song song của thuật toán Hybrid hash join của chúng tôi tương tự như thuật toán tập trung được mô tả ở trên. Một bảng tách phân vùng trước tiên tách các quan hệ join thành $N$ bucket logic. Số lượng bucket được chọn sao cho các bộ tương ứng với mỗi bucket logic sẽ vừa trong bộ nhớ tổng hợp của các bộ xử lý join. Các bucket $N-1$ được dành cho việc lưu trữ tạm thời trên đĩa đều được phân vùng trên tất cả các vị trí đĩa khả dụng. Tương tự, một bảng tách join sẽ được sử dụng để định tuyến các bộ đến bộ xử lý join tương ứng của chúng (các bộ xử lý này không nhất thiết có đĩa gắn kèm), do đó song song hóa giai đoạn join. Hơn nữa, việc phân vùng quan hệ bên trong, $R$, thành các bucket được chồng lấp với việc chèn các bộ từ bucket đầu tiên của $R$ vào các bảng hash cư trú trong bộ nhớ tại mỗi nút join. Ngoài ra, việc phân vùng quan hệ bên ngoài, $S$, thành các bucket được chồng lấp với việc join bucket đầu tiên của $S$ với bucket đầu tiên của $R$. Điều này yêu cầu bảng tách phân vùng cho $R$ và $S$ được tăng cường bằng bảng tách join vì các bộ trong bucket đầu tiên phải được gửi đến những bộ xử lý được sử dụng để thực hiện phép join. Tất nhiên, khi các bucket $N-1$ còn lại được join, chỉ cần bảng tách join. Figure 8 mô tả quan hệ $R$ được phân vùng thành $N$ bucket trên $k$ vị trí đĩa trong đó bucket đầu tiên được join trên $m$ bộ xử lý ($m$ có thể nhỏ hơn, bằng, hoặc lớn hơn $k$).

4.3. Aggregate Operations

4.3. Các thao tác Aggregate

Gamma implements scalar aggregates by having each processor compute its piece of the result in parallel. The partial results are then sent to a single process which combines these partial results into the final answer. Aggregate functions are computed in two steps. First, each processor computes a piece of the result by calculating a value for each of the partitions. Next, the processors redistribute the partial results by hashing on the "group by" attribute. The result of this step is to collect the partial results for each partition at a single site so that the final result for each partition can be computed.

Gamma triển khai các aggregate vô hướng bằng cách cho mỗi bộ xử lý tính toán phần kết quả của nó song song. Các kết quả từng phần sau đó được gửi đến một process duy nhất, process này kết hợp các kết quả từng phần này thành đáp án cuối cùng. Các hàm aggregate được tính toán theo hai bước. Đầu tiên, mỗi bộ xử lý tính toán một phần của kết quả bằng cách tính một giá trị cho từng phân vùng. Tiếp theo, các bộ xử lý phân phối lại các kết quả từng phần bằng cách băm trên thuộc tính "group by". Kết quả của bước này là thu thập các kết quả từng phần cho mỗi phân vùng tại một vị trí duy nhất để có thể tính toán kết quả cuối cùng cho mỗi phân vùng.

4.4. Update Operators

4.4. Các toán tử cập nhật

For the most part, the update operators (replace, delete, and append) are implemented using standard techniques. The only exception occurs when a replace operator modifies the partitioning attribute of a tuple. In this case, rather than writing the modified tuple back into the local fragment of the relation, the modified tuple is passed through a split table to determine which site should contain the tuple.

Phần lớn, các toán tử cập nhật (thay thế, xóa và thêm vào) được triển khai bằng cách sử dụng các kỹ thuật chuẩn. Ngoại lệ duy nhất xảy ra khi một toán tử thay thế sửa đổi thuộc tính phân vùng của một bộ. Trong trường hợp này, thay vì ghi bộ đã sửa đổi trở lại vào phân mảnh cục bộ của quan hệ, bộ đã sửa đổi được truyền qua một bảng phân tách để xác định site nào nên chứa bộ đó.

5 Transaction and Failure Management

5 Quản lý giao dịch và sự cố

In this section we describe the mechanisms that Gamma uses for transaction and failure management. While the locking mechanisms are fully operational, the recovery system is currently being implemented. We expect to begin the implementation of the failure management mechanism in early 1990.

Trong phần này chúng tôi mô tả các cơ chế mà Gamma sử dụng cho việc quản lý giao dịch và sự cố. Trong khi các cơ chế khóa đã hoàn toàn hoạt động, hệ thống phục hồi hiện đang được triển khai. Chúng tôi dự kiến bắt đầu triển khai cơ chế quản lý sự cố vào đầu năm 1990.

5.1. Concurrency Control in Gamma

5.1. Kiểm soát đồng thời trong Gamma

Concurrency control in Gamma is based on two-phase locking [GRAY78]. Currently, two lock granularities, file, and page, and five lock modes, S, X, IS, IX, and SIX are provided. Each site in Gamma has its own local lock manager and deadlock detector. The lock manager maintains a lock table and a transaction wait-for-graph. The cost of setting a lock varies from approximately 100 instructions, if there is no conflict, to 250 instructions if the lock request conflicts with the granted group. In this case, the wait-for-graph must be checked for deadlock and the transaction that requested the lock must be suspended via a semaphore mechanism.

Kiểm soát đồng thời trong Gamma dựa trên khóa hai pha [GRAY78]. Hiện tại, hai mức chi tiết của khóa, file và page, cùng năm chế độ khóa, S, X, IS, IX và SIX được cung cấp. Mỗi site trong Gamma có bộ quản lý khóa cục bộ và bộ phát hiện bế tắc riêng. Bộ quản lý khóa duy trì một bảng khóa và một đồ thị chờ-để-giao dịch. Chi phí thiết lập một khóa thay đổi từ khoảng 100 lệnh, nếu không có xung đột, đến 250 lệnh nếu yêu cầu khóa xung đột với nhóm đã được cấp quyền. Trong trường hợp này, đồ thị chờ-để phải được kiểm tra bế tắc và giao dịch yêu cầu khóa phải được tạm dừng thông qua cơ chế semaphore.

In order to detect multisite deadlocks, Gamma uses a centralized deadlock detection algorithm. Periodically, the centralized deadlock detector sends a message to each node in the configuration, requesting the local transaction wait-for-graph of that node. Initially, the period for running the centralized deadlock detector is set at one second. Each time the deadlock detector fails to find a global deadlock, this interval is doubled and each time a deadlock is found the current value of the interval is halved. The upper bound of the interval is limited to 60 seconds and the lower bound is 1 second. After collecting the wait-for-graph from each site, the centralized deadlock detector creates a global transaction wait-for-graph. Whenever a cycle is detected in the global wait-for-graph, the centralized deadlock manager chooses to abort the transaction holding the fewest number of locks.

Để phát hiện các bế tắc đa site, Gamma sử dụng một thuật toán phát hiện bế tắc tập trung. Định kỳ, bộ phát hiện bế tắc tập trung gửi một thông điệp đến mỗi nút trong cấu hình, yêu cầu đồ thị chờ-để-giao dịch cục bộ của nút đó. Ban đầu, khoảng thời gian chạy bộ phát hiện bế tắc tập trung được đặt là một giây. Mỗi lần bộ phát hiện bế tắc không tìm thấy một bế tắc toàn cục, khoảng thời gian này được nhân đôi và mỗi lần phát hiện thấy một bế tắc thì giá trị hiện tại của khoảng thời gian được chia đôi. Cận trên của khoảng thời gian được giới hạn ở 60 giây và cận dưới là 1 giây. Sau khi thu thập đồ thị chờ-để từ mỗi site, bộ phát hiện bế tắc tập trung tạo ra một đồ thị chờ-để-giao dịch toàn cục. Bất cứ khi nào một chu trình được phát hiện trong đồ thị chờ-để toàn cục, bộ quản lý bế tắc tập trung chọn hủy giao dịch đang giữ số lượng khóa ít nhất.

5.2. Recovery Architecture and Log Manager

5.2. Kiến trúc phục hồi và Bộ quản lý nhật ký

The algorithms currently being implemented for coordinating transaction commit, abort, and rollback operate as follows. When an operator process updates a record, it also generates a log record which records the change of the database state. Associated with every log record is a log sequence number (LSN) which is composed of a node number and a local sequence number. The node number is statically determined at the system configuration time whereas the local sequence number, termed current LSN, is a monotonically increasing value.

Các thuật toán hiện đang được triển khai để phối hợp xác nhận, hủy bỏ và quay lui giao dịch hoạt động như sau. Khi một tiến trình toán tử cập nhật một bản ghi, nó cũng tạo ra một bản ghi nhật ký ghi lại sự thay đổi của trạng thái cơ sở dữ liệu. Liên kết với mỗi bản ghi nhật ký là một số thứ tự nhật ký (LSN), được tạo thành từ một số nút và một số thứ tự cục bộ. Số nút được xác định tĩnh tại thời điểm cấu hình hệ thống, trong khi số thứ tự cục bộ, được gọi là current LSN, là một giá trị tăng đơn điệu.

Log records are sent by the query processors to one or more Log Managers (each running on a separate processor) which merges the log records it receives to form a single log stream. If M is the number of log processors being used, query processor i will direct its log records to the (i mod M) log processor [AGRA85]. Because this algorithm selects the log processor statically and a query processor always sends its log records to the same log processor, the recovery process at a query processing node can easily determine where to request the log records for processing a transaction abort.

Các bản ghi nhật ký được gửi bởi các bộ xử lý truy vấn đến một hoặc nhiều Bộ quản lý nhật ký (mỗi bộ chạy trên một bộ xử lý riêng), các bộ này hợp nhất các bản ghi nhật ký nhận được để tạo thành một luồng nhật ký duy nhất. Nếu M là số lượng bộ xử lý nhật ký đang được sử dụng, bộ xử lý truy vấn i sẽ chuyển các bản ghi nhật ký của nó đến bộ xử lý nhật ký (i mod M) [AGRA85]. Vì thuật toán này chọn bộ xử lý nhật ký một cách tĩnh và một bộ xử lý truy vấn luôn gửi các bản ghi nhật ký của nó đến cùng một bộ xử lý nhật ký, tiến trình phục hồi tại một nút xử lý truy vấn có thể dễ dàng xác định nơi yêu cầu các bản ghi nhật ký để xử lý việc hủy bỏ một giao dịch.

When a page of log records is filled, it is written to disk. The Log Manager maintains a table, called the Flushed Log Table, which contains, for each node, the LSN of the last log record from that node that has been flushed to disk. These values are returned to the nodes either upon request or when they can be piggybacked on another message. Query processing nodes save this information in a local variable, termed the Flushed LSN.

Khi một page của các bản ghi nhật ký đầy, nó được ghi xuống disk. Bộ quản lý nhật ký duy trì một bảng, được gọi là Flushed Log Table, chứa, đối với mỗi nút, LSN của bản ghi nhật ký cuối cùng từ nút đó đã được ghi xuống disk. Các giá trị này được trả về các nút theo yêu cầu hoặc khi chúng có thể được ghép kèm trong một thông điệp khác. Các nút xử lý truy vấn lưu thông tin này trong một biến cục bộ, được gọi là Flushed LSN.

The buffer managers at the query processing nodes observe the WAL protocol [GRAY78]. When a dirty page needs to be forced to disk, the buffer manager first compares the page’s LSN with the local value of Flushed LSN. If the page LSN of a page is smaller or equal to the Flushed LSN, that page can be safely written to disk. Otherwise, either a different dirty page must be selected, or a message must be sent to the Log Manager to flush the corresponding log record(s) of the dirty page. Only after the Log Manager acknowledges that the log record has been written to the log disk will the dirty data page be written back to disk. In order to reduce the time spent waiting for a reply from the Log Manager, the buffer manager always keeps T (a pre-selected threshold) clean and unfixed buffer pages available. When buffer manager notices that the number of clean, unfixed buffer pages has fallen below T, a process, termed local log manager, is activated. This process sends a message to the Log Manager to flush one or more log records so that the number of clean and unfixed pages plus the number of dirty pages that can be safely written to to disk is greater than T.

Các bộ quản lý bộ đệm tại các nút xử lý truy vấn tuân theo giao thức WAL [GRAY78]. Khi một page bẩn cần được ép ghi xuống disk, bộ quản lý bộ đệm trước tiên so sánh LSN của page với giá trị cục bộ của Flushed LSN. Nếu LSN của page của một page nhỏ hơn hoặc bằng Flushed LSN, page đó có thể được ghi an toàn xuống disk. Ngược lại, hoặc một page bẩn khác phải được chọn, hoặc một thông điệp phải được gửi đến Bộ quản lý nhật ký để xóa các bản ghi nhật ký tương ứng của page bẩn. Chỉ sau khi Bộ quản lý nhật ký xác nhận rằng bản ghi nhật ký đã được ghi vào disk nhật ký thì page dữ liệu bẩn mới được ghi trở lại disk. Để giảm thời gian chờ phản hồi từ Bộ quản lý nhật ký, bộ quản lý bộ đệm luôn giữ sẵn T (một ngưỡng được chọn trước) page bộ đệm sạch và không cố định. Khi bộ quản lý bộ đệm nhận thấy số lượng page bộ đệm sạch, không cố định đã giảm xuống dưới T, một tiến trình, được gọi là local log manager, được kích hoạt. Tiến trình này gửi một thông điệp đến Bộ quản lý nhật ký để xóa một hoặc nhiều bản ghi nhật ký sao cho số lượng page sạch và không cố định cộng với số lượng page bẩn có thể được ghi an toàn xuống disk lớn hơn T.

The scheduler process for a query is responsible for sending commit or abort records to the appropriate Log Managers. If a transaction completes successfully, a commit record for the transaction is generated by its scheduler and sent to each relevant Log Manager which employs a group commit protocol. On the other hand, if a transaction is aborted by either the system or the user, its scheduler will send an abort message to all query processors that participated in its execution. The recovery process at each of the participating nodes responds by requesting the log records generated by the node from its Log Manager (the LSN of each log record contains the originating node number). As the log records are received, the recovery process undoes the log records in reverse chronological order using the ARIES undo algorithm [MOHA89]. The ARIES algorithms are also used as the basis for checkpointing and restart recovery.

Tiến trình bộ lập lịch cho một truy vấn chịu trách nhiệm gửi các bản ghi xác nhận hoặc hủy bỏ đến các Bộ quản lý nhật ký thích hợp. Nếu một giao dịch hoàn thành thành công, một bản ghi xác nhận cho giao dịch đó được tạo bởi bộ lập lịch của nó và được gửi đến mỗi Bộ quản lý nhật ký liên quan, sử dụng một giao thức xác nhận nhóm. Mặt khác, nếu một giao dịch bị hủy bỏ bởi hệ thống hoặc người dùng, bộ lập lịch của nó sẽ gửi một thông điệp hủy bỏ đến tất cả các bộ xử lý truy vấn đã tham gia vào việc thực thi của nó. Tiến trình phục hồi tại mỗi nút tham gia phản hồi bằng cách yêu cầu các bản ghi nhật ký được tạo bởi nút đó từ Bộ quản lý nhật ký của nó (LSN của mỗi bản ghi nhật ký chứa số nút khởi tạo). Khi các bản ghi nhật ký được nhận, tiến trình phục hồi hoàn tác các bản ghi nhật ký theo thứ tự thời gian ngược bằng cách sử dụng thuật toán undo ARIES [MOHA89]. Các thuật toán ARIES cũng được sử dụng làm cơ sở cho việc tạo điểm kiểm tra và phục hồi khởi động lại.

5.3. Failure Management

5.3. Quản lý sự cố

To help insure availability of the system in the event of processor and/or disk failures, Gamma employs a new availability technique termed chained declustering [HSIA90]. Like Tandem’s mirrored disk mechanism [BORG81] and Teradata’s interleaved declustering mechanism [TERA85, COPE89], chained declustering employs both a primary and backup copy of each relation. All three systems can sustain the failure of a single processor or disk without suffering any loss in data availability. In [HSIA90], we show that chained declustering provides a higher degree of availability than interleaved declustering and, in the event of a processor or disk failure, does a better job of distributing the workload of the broken node. The mirrored disk mechanism, while providing the highest level of availability, does a very poor job of distributing the load of a failed processor.

Để giúp đảm bảo tính sẵn sàng của hệ thống trong trường hợp xảy ra sự cố với bộ xử lý và/hoặc đĩa, Gamma sử dụng một kỹ thuật sẵn sàng mới được gọi là phân mảnh theo chuỗi [HSIA90]. Giống như cơ chế đĩa nhân bản của Tandem [BORR81] và cơ chế phân mảnh xen kẽ của Teradata [TERA85, COPE89], phân mảnh theo chuỗi duy trì cả bản sao chính và bản sao dự phòng của mỗi quan hệ. Cả ba hệ thống đều có thể chịu được sự cố của một bộ xử lý hoặc đĩa đơn lẻ mà không chịu bất kỳ sự mất mát nào về tính sẵn sàng của dữ liệu. Trong [HSIA90], chúng tôi chỉ ra rằng phân mảnh theo chuỗi cung cấp mức độ sẵn sàng cao hơn so với phân mảnh xen kẽ và, trong trường hợp xảy ra sự cố với bộ xử lý hoặc đĩa, phân phối tải công việc của nút bị hỏng tốt hơn. Cơ chế đĩa nhân bản, mặc dù cung cấp mức độ sẵn sàng cao nhất, lại phân phối tải của một bộ xử lý bị hỏng rất kém.

Data Placement with Chained Declustering

Bố trí dữ liệu với phân mảnh theo chuỗi

With chained declustering, nodes (a processor with one or more disks) are divided into disjoint groups called relation-clusters and tuples of each relation are declustered among the drives that form one of the relation clusters. Two physical copies of each relation, termed the primary copy and the backup copy, are maintained. As an example, consider Figure 9 where M, the number of disks in the relation cluster, is equal to 8. The tuples in the primary copy of relation R are declustered using one of Gamma’s three partitioning strategies with tuples in the i-th primary fragment (designated Ri) stored on the {i mod M}-th disk drive. The backup copy is declustered using the same partitioning strategy but the i-th backup fragment (designated ri) is stored on the {(i + 1) mod M}-th disk. We term this data replication method chained declustering because the disks are linked together, by the fragments of a relation, like a chain.

Với phân mảnh theo chuỗi, các nút (một bộ xử lý với một hoặc nhiều đĩa) được chia thành các nhóm rời nhau gọi là các cụm-quan hệ và các bộ của mỗi quan hệ được phân mảnh giữa các ổ đĩa tạo thành một trong các cụm quan hệ. Hai bản sao vật lý của mỗi quan hệ, được gọi là bản sao chính và bản sao dự phòng, được duy trì. Ví dụ, xét Figure 9 trong đó M, số lượng đĩa trong cụm quan hệ, bằng 8. Các bộ trong bản sao chính của quan hệ R được phân mảnh bằng một trong ba chiến lược phân vùng của Gamma, với các bộ trong mảnh chính thứ i (được ký hiệu là Ri) được lưu trữ trên ổ đĩa thứ {i mod M}. Bản sao dự phòng được phân mảnh bằng cùng một chiến lược phân vùng nhưng mảnh dự phòng thứ i (được ký hiệu là ri) được lưu trữ trên đĩa thứ {(i + 1) mod M}. Chúng tôi gọi phương pháp sao chép dữ liệu này là phân mảnh theo chuỗi vì các đĩa được liên kết với nhau bởi các mảnh của một quan hệ, giống như một chuỗi.

Chained Declustering (Relation Cluster Size = 8) Figure 9

Sự khác biệt giữa cơ chế phân mảnh theo chuỗi và phân mảnh xen kẽ [TERA85, COPE89] được minh họa bởi Figure 10. Trong Figure 10, các mảnh từ bản sao chính của R được phân mảnh trên toàn bộ 8 ổ đĩa bằng cách băm trên một thuộc tính "key". Với cơ chế phân mảnh xen kẽ, tập hợp các đĩa được chia thành các đơn vị có kích thước N gọi là các cụm. Như được minh họa trong Figure 10, trong đó N=4, mỗi mảnh dự phòng được chia nhỏ thành N-1 mảnh con và mỗi mảnh con được đặt trên một đĩa khác nhau trong cùng một cụm, khác với đĩa chứa mảnh chính.

The difference between the chained and interleaved declustering mechanisms [TERA85, COPE89] is illustrated by Figure 10. In Figure 10, the fragments from the primary copy of R are declustered across all 8 disk drives by hashing on a "key" attribute. With the interleaved declustering mechanism the set of disks are divided into units of size N called clusters. As illustrated by Figure 10, where N=4, each backup fragment is subdivided into N-1 sub-fragments and each subfragment is placed on a different disk within the same cluster other than the disk containing the primary fragment.

Vì cả phân mảnh xen kẽ và phân mảnh theo chuỗi đều có thể chịu được sự cố của một đĩa hoặc bộ xử lý đơn lẻ, vậy sự khác biệt giữa hai cơ chế này là gì? Trong trường hợp sự cố của một nút đơn lẻ (bộ xử lý hoặc đĩa), cả hai chiến lược phân mảnh theo chuỗi và phân mảnh xen kẽ đều có khả năng phân phối đồng đều tải công việc của cụm giữa các nút hoạt động còn lại. Ví dụ, với kích thước cụm là 8, khi một bộ xử lý hoặc đĩa gặp sự cố, tải trên mỗi nút còn lại sẽ tăng thêm 1/7th. Khi đó có thể kết luận rằng kích thước cụm nên được làm lớn nhất có thể; cho đến khi, tất nhiên, chi phí phụ trội của tính song song bắt đầu lấn át các lợi ích thu được. Mặc dù điều này đúng đối với phân mảnh theo chuỗi, tính sẵn sàng của chiến lược xen kẽ tỷ lệ nghịch với kích thước cụm, vì sự cố của bất kỳ hai bộ xử lý hoặc đĩa nào sẽ làm cho dữ liệu không thể truy cập được. Do đó, việc tăng gấp đôi kích thước cụm để giảm một nửa (xấp xỉ) mức tăng tải trên các nút còn lại khi xảy ra sự cố có tác dụng phụ (rất tiêu cực) là làm tăng gấp đôi xác suất dữ liệu thực sự không sẵn sàng. Vì lý do này, Teradata khuyến nghị kích thước cụm là 4 hoặc 8 bộ xử lý.

Interleaved Declustering (Cluster Size = 4) Figure 10

Figure 11 minh họa cách tải công việc được cân bằng trong trường hợp xảy ra sự cố nút (nút 1 trong ví dụ này) với cơ chế phân mảnh theo chuỗi. Trong chế độ hoạt động bình thường, các yêu cầu đọc được chuyển đến các mảnh của bản sao chính và các thao tác ghi cập nhật cả hai bản sao. Khi xảy ra sự cố, các phần của cả mảnh chính và mảnh dự phòng được sử dụng cho các thao tác đọc. Ví dụ, với sự cố của nút 1, mảnh chính R1 không còn có thể được truy cập và do đó mảnh dự phòng r1 trên nút 2 phải được sử dụng để xử lý các truy vấn vốn thường được chuyển đến R1. Tuy nhiên, thay vì yêu cầu nút 2 xử lý tất cả các truy cập đến cả R2 và r1, phân mảnh theo chuỗi giảm tải 6/7-ths số truy cập đến R2 bằng cách chuyển hướng chúng đến r2 trên nút 3. Ngược lại, 5/7-ths số truy cập đến R3 trên nút 3 được gửi đến R4 thay thế. Việc gán lại tải công việc động này dẫn đến mức tăng 1/7-th trong tải công việc của mỗi nút còn lại trong cụm. Vì kích thước cụm quan hệ có thể được tăng lên mà không bị phạt, có thể làm cho mức tăng tải này nhỏ đến mức mong muốn.

Since interleaved and chained declustering can both sustain the failure of a single disk or processor, what then is the difference between the two mechanisms? In the case of a single node (processor or disk) failure both the chained and interleaved declustering strategies are able to uniformly distribute the workload of the cluster among the remaining operational nodes. For example, with a cluster size of 8, when a processor or disk fails, the load on each remaining node will increase by 1/7th. One might conclude then that the cluster size should be made as large as possible; until, of course, the overhead of the parallelism starts to overshadow the benefits obtained. While this is true for chained declustering, the availability of the interleaved strategy is inversely proportional to the cluster size. since the failure of any two processors or disk will render data unavailable. Thus, doubling the cluster size in order to halve (approximately) the increase in the load on the remaining nodes when a failure occurs has the (quite negative) side effect of doubling the probability that data will actually be unavailable. For this reason, Teradata recommends a cluster size of 4 or 8 processors.

Figure 11 illustrates how the workload is balanced in the event of a node failure (node 1 in this example) with the chained declustering mechanism. During the normal mode of operation, read requests are directed to the fragments of the primary copy and write operations update both copies. When a failure occurs, pieces of both the primary and backup fragments are used for read operations. For example, with the failure of node 1, primary fragment R1 can no longer be accessed and thus its backup fragment r1 on node 2 must be used for processing queries that would normally have been directed to R1. However, instead of requiring node 2 to process all accesses to both R2 and r1, chained declustering offloads 6/7-ths of the accesses to R2 by redirecting them to r2 at node 3. In turn, 5/7-ths of access to R3 at node 3 are sent to R4 instead. This dynamic reassignment of the workload results in an increase of 1/7-th in the workload of each remaining node in the cluster. Since the relation cluster size can be increased without penalty, it is possible to make this load increase as small as is desired.

Sử dụng mảnh với phân mảnh theo chuỗi Sau sự cố của nút 1 (Kích thước cụm quan hệ = 8) Figure 11

Điều làm cho lược đồ này hấp dẫn hơn nữa là việc gán lại các mảnh đang hoạt động không phát sinh I/O đĩa cũng như di chuyển dữ liệu. Chỉ một số giá trị cận và con trỏ/chỉ mục trong một bảng điều khiển nằm trong bộ nhớ cần được thay đổi, và các sửa đổi này có thể được thực hiện rất nhanh chóng và hiệu quả.

Fragment Utilization with Chained Declustering After the Failure of Node 1 (Relation Cluster Size = 8) Figure 11

Ví dụ được trình bày trong Hình 11 cung cấp một cái nhìn rất đơn giản hóa về cách cơ chế phân cụm phân mảnh theo chuỗi thực sự cân bằng tải công việc trong trường hợp một nút gặp sự cố. Trong thực tế, các truy vấn không thể chỉ đơn giản truy cập một phần tùy ý của một mảnh dữ liệu, đặc biệt khi xét đến sự đa dạng của các cơ chế phân vùng và chỉ mục được cung cấp bởi phần mềm Gamma. Trong [HSIA90], chúng tôi mô tả cách tất cả các tổ hợp của các kiểu truy vấn, phương thức truy cập và phân vùng

What makes this scheme even more attractive is that the reassignment of active fragments incurs neither disk I/O nor data movement. Only some of the bound values and pointers/indices in a memory resident control table must be changed and these modifications can be done very quickly and efficiently.

Nothing here.

The example shown in Figure 11 provides a very simplified view of how the chained declustering mechanism actually balances the workload in the event of a node failure. In reality, queries cannot simply access an arbitrary fraction of a data fragment, especially given the variety of partitioning and index mechanisms provided by the Gamma software. In [HSIA90], we describe how all combinations of query types, access methods, and partitioning mechanisms can be handled.

Nothing here.

6 Performance Studies

6 Các nghiên cứu về hiệu năng

6.1. Introduction and Experiment Overview

6.1. Giới thiệu và Tổng quan về Thí nghiệm

To evaluate the performance of the hypercube version of Gamma three different metrics were used. First, the set of Wisconsin [BITT83] benchmark queries were run on a 30 processor configuration using three different sizes of relations: 100,000, 1 million, and 10 million tuples. While absolute performance is one measure of a database system, speedup and scaleup are also useful metrics for multiprocessor database machines [ENGL89]. Speedup is an interesting metric because it indicates whether additional processors and disks results in a corresponding decrease in the response time for a query. For a subset of the Wisconsin benchmark queries, we conducted speedup experiments by varying the number of processors from 1 to 30 while the size of the test relations was fixed at 1 million tuples. For the same set of queries, we also conducted scaleup experiments by varying the number of processors from 5 to 30 while the size of the test relations was increased from 1 to 6 million tuples, respectively. Scaleup is a valuable metric as it indicates whether a constant response time can be maintained as the workload is increased by adding a proportional number of processors and disks. [ENGL89] describes a similar set of tests on Release 2 of Tandem’s NonStop SQL system.

Để đánh giá hiệu năng của phiên bản siêu khối của Gamma, ba độ đo khác nhau đã được sử dụng. Trước tiên, tập các truy vấn phép đo chuẩn Wisconsin [BITT83] được chạy trên một cấu hình gồm 30 bộ xử lý với ba kích thước khác nhau của các quan hệ: 100,000, 1 triệu, và 10 triệu bộ. Trong khi hiệu năng tuyệt đối là một độ đo của một hệ thống cơ sở dữ liệu, tăng tốc và mở rộng quy mô cũng là các độ đo hữu ích cho các máy cơ sở dữ liệu đa bộ xử lý [ENGL89]. Tăng tốc là một độ đo thú vị vì nó chỉ ra liệu các bộ xử lý và ổ đĩa bổ sung có dẫn đến sự giảm tương ứng trong thời gian đáp ứng của một truy vấn hay không. Đối với một tập con các truy vấn phép đo chuẩn Wisconsin, chúng tôi đã tiến hành các thí nghiệm tăng tốc bằng cách thay đổi số lượng bộ xử lý từ 1 đến 30 trong khi kích thước của các quan hệ kiểm tra được cố định ở 1 triệu bộ. Với cùng tập truy vấn đó, chúng tôi cũng tiến hành các thí nghiệm mở rộng quy mô bằng cách thay đổi số lượng bộ xử lý từ 5 đến 30 trong khi kích thước của các quan hệ kiểm tra lần lượt được tăng từ 1 đến 6 triệu bộ. Mở rộng quy mô là một độ đo có giá trị vì nó chỉ ra liệu một thời gian đáp ứng không đổi có thể được duy trì khi tải công việc được tăng lên bằng cách thêm một số lượng bộ xử lý và ổ đĩa tỷ lệ thuận hay không. [ENGL89] mô tả một tập kiểm tra tương tự trên Release 2 của hệ thống NonStop SQL của Tandem.

The benchmark relations used for the experiments were based on the standard Wisconsin Benchmark relations [BITT83]. Each relation consists of tuples that are 208 bytes wide. We constructed 100,000, 1 million, and 10 million tuple versions of the benchmark relations. Two copies of each relation were created and loaded. Except where noted otherwise, tuples were declustered by hash partitioning on the Unique1 attribute. In all cases, the results presented represent the average response time of a number of equivalent queries. Gamma was configured to use a disk page size of 8K bytes and a buffer pool of 2 megabytes.

Các quan hệ phép đo chuẩn được sử dụng cho các thí nghiệm dựa trên các quan hệ phép đo chuẩn Wisconsin tiêu chuẩn [BITT83]. Mỗi quan hệ bao gồm các bộ có độ rộng 208 byte. Chúng tôi đã xây dựng các phiên bản 100,000, 1 triệu, và 10 triệu bộ của các quan hệ phép đo chuẩn. Hai bản sao của mỗi quan hệ được tạo và nạp. Ngoại trừ trường hợp được ghi chú khác, các bộ được phân tán bằng cách phân vùng băm trên thuộc tính Unique1. Trong mọi trường hợp, các kết quả được trình bày biểu diễn thời gian đáp ứng trung bình của một số truy vấn tương đương. Gamma được cấu hình để sử dụng kích thước trang đĩa 8K byte và một nhóm bộ đệm 2 megabyte.

The results of all queries were stored in the database. We avoided returning data to the host in order to avoid having the speed of the communications link between the host and the database machine or the host processor itself affect the results. By storing the result relations in the database, the impact of these factors was minimized - at the expense of incurring the cost of declustering and storing the result relations.

Kết quả của tất cả các truy vấn được lưu trữ trong cơ sở dữ liệu. Chúng tôi tránh trả dữ liệu về máy chủ để tránh việc tốc độ của liên kết truyền thông giữa máy chủ và máy cơ sở dữ liệu hoặc chính bộ xử lý máy chủ ảnh hưởng đến kết quả. Bằng cách lưu trữ các quan hệ kết quả trong cơ sở dữ liệu, tác động của các yếu tố này được giảm thiểu - với chi phí phải chịu thêm chi phí phân tán và lưu trữ các quan hệ kết quả.

6.2. Selection Queries

6.2. Các truy vấn lựa chọn

Performance Relative to Relation Size

Hiệu năng tương đối so với kích thước quan hệ

The first set of selection tests were designed to determine how Gamma would respond as the size of the source relations was increased while the machine configuration was kept at 30 processors with disks. Ideally, the response time of a query should grow as a linear function of the size of input and result relations. For these tests six different selection queries were run on three sets of relations containing, respectively, 100,000, 1 million, and 10 million tuples. The first two queries have a selectivity factor of 1% and 10% and do not employ any indices. The third and fourth queries have the same selectivity factors but use a clustered index to locate the qualifying tuples. The fifth query has a selectivity factor of 1% and employs a non-clustered index to locate the desired tuples. There is no 10% selection through a non-clustered index query as the Gamma query optimizer chooses to use a sequential scan for this query. The last query uses a clustered index to retrieve a single tuple. Except for the last query, the predicate of each query specifies a range of values and, thus, since the input relations were declustered by hashing, the query must be sent to all the nodes.

Tập kiểm tra lựa chọn đầu tiên được thiết kế để xác định cách Gamma phản hồi khi kích thước của các quan hệ nguồn được tăng lên trong khi cấu hình máy được giữ ở mức 30 bộ xử lý với các ổ đĩa. Lý tưởng nhất, thời gian đáp ứng của một truy vấn nên tăng theo một hàm tuyến tính của kích thước các quan hệ đầu vào và kết quả. Đối với các kiểm tra này, sáu truy vấn lựa chọn khác nhau được chạy trên ba tập quan hệ chứa lần lượt 100,000, 1 triệu, và 10 triệu bộ. Hai truy vấn đầu tiên có hệ số chọn lọc là 1% và 10% và không sử dụng bất kỳ chỉ mục nào. Truy vấn thứ ba và thứ tư có cùng các hệ số chọn lọc nhưng sử dụng một chỉ mục phân cụm để định vị các bộ thỏa mãn. Truy vấn thứ năm có hệ số chọn lọc 1% và sử dụng một chỉ mục không phân cụm để định vị các bộ mong muốn. Không có truy vấn lựa chọn 10% thông qua chỉ mục không phân cụm vì bộ tối ưu hóa truy vấn của Gamma chọn sử dụng quét tuần tự cho truy vấn này. Truy vấn cuối cùng sử dụng một chỉ mục phân cụm để lấy một bộ duy nhất. Ngoại trừ truy vấn cuối cùng, vị từ của mỗi truy vấn chỉ định một miền giá trị và do đó, vì các quan hệ đầu vào được phân tán bằng băm, truy vấn phải được gửi đến tất cả các nút.

The results from these tests are tabulated in Table 3. For the most part, the execution time for each query scales as a fairly linear function of the size of the input and output relations. There are, however, several cases where the scaling is not perfectly linear. Consider, first the 1% non-indexed selection. While the increase in response time as the size of the input relation is increased from 1 to 10 million tuples is almost perfectly linear (8.16 secs. to 81.15 secs.), the increase from 100,000 tuples to 1 million tuples (0.45 sec. to 8.16 sec) is actually sub-linear. The 10% selection using a clustered index is another example where increasing the size of the input relation by a factor of ten results in more than a ten-fold increase in the response time for the query. This query takes 5.02 seconds on the 1 million tuple relation and 61.86 seconds on the 10 million tuple relation. To understand why this happens one must consider the impact of seek time on the execution time of the query. Since two copies of each relation were loaded, when two one million tuple relations are declustered over 30 disk drives, the fragments occupy approximately 53 cylinders (out of 1224) on each disk drive. Two ten million tuple relations fill about 530 cylinders on each drive. As each page of the result relation is written to disk, the disk heads must be moved from their current position over the input relation to a free block on the disk. Thus, with the 10 million tuple relation, the cost of writing each output page is much higher.

Các kết quả từ các kiểm tra này được lập bảng trong Bảng 3. Phần lớn, thời gian thực thi của mỗi truy vấn mở rộng theo một hàm khá tuyến tính của kích thước các quan hệ đầu vào và đầu ra. Tuy nhiên, có một số trường hợp việc mở rộng không hoàn toàn tuyến tính. Trước tiên hãy xét phép lựa chọn 1% không có chỉ mục. Trong khi sự tăng thời gian đáp ứng khi kích thước quan hệ đầu vào được tăng từ 1 đến 10 triệu bộ gần như hoàn toàn tuyến tính (8.16 secs. đến 81.15 secs.), sự tăng từ 100,000 bộ đến 1 triệu bộ (0.45 sec. đến 8.16 sec) thực sự là dưới tuyến tính. Phép lựa chọn 10% sử dụng chỉ mục phân cụm là một ví dụ khác trong đó việc tăng kích thước quan hệ đầu vào lên một hệ số mười dẫn đến mức tăng lớn hơn mười lần trong thời gian đáp ứng của truy vấn. Truy vấn này mất 5.02 giây trên quan hệ 1 triệu bộ và 61.86 giây trên quan hệ 10 triệu bộ. Để hiểu tại sao điều này xảy ra, cần xem xét tác động của thời gian tìm kiếm lên thời gian thực thi của truy vấn. Vì hai bản sao của mỗi quan hệ đã được nạp, khi hai quan hệ một triệu bộ được phân tán trên 30 ổ đĩa, các mảnh chiếm xấp xỉ 53 cylinder (trong số 1224) trên mỗi ổ đĩa. Hai quan hệ mười triệu bộ lấp đầy khoảng 530 cylinder trên mỗi ổ đĩa. Khi mỗi trang của quan hệ kết quả được ghi vào đĩa, các đầu đọc đĩa phải được di chuyển từ vị trí hiện tại của chúng trên quan hệ đầu vào đến một khối trống trên đĩa. Vì vậy, với quan hệ 10 triệu bộ, chi phí ghi mỗi trang đầu ra cao hơn nhiều.

As expected, the use of a clustered B-tree index always provides a significant improvement in performance. One observation to be made from Table 3 is the relative consistency of the execution time of the selection queries through a clustered index. Notice that the execution time for a 10% selection on the 1 million tuple relation is almost identical to the execution time of the 1% selection on the 10 million tuple relation. In both cases, 100,000 tuples are retrieved and stored, resulting in identical I/O and CPU costs.

Như mong đợi, việc sử dụng chỉ mục B-tree phân cụm luôn cung cấp sự cải thiện đáng kể về hiệu năng. Một nhận xét rút ra từ Bảng 3 là tính nhất quán tương đối của thời gian thực thi của các truy vấn lựa chọn thông qua chỉ mục phân cụm. Lưu ý rằng thời gian thực thi của một phép lựa chọn 10% trên quan hệ 1 triệu bộ gần như giống hệt thời gian thực thi của phép lựa chọn 1% trên quan hệ 10 triệu bộ. Trong cả hai trường hợp, 100,000 bộ được lấy và lưu trữ, dẫn đến chi phí I/O và CPU giống hệt nhau.

The final row of Table 3 presents the time required to select a single tuple using a clustered index and return it to the host. Since the selection predicate is on the partitioning attribute, the query is directed to a single node, avoiding the overhead of starting the query on all 30 processors. The response for this query increases significantly as the

Hàng cuối cùng của Bảng 3 trình bày thời gian cần thiết để chọn một bộ từ đơn bằng cách sử dụng chỉ mục phân cụm và trả nó về máy chủ. Vì vị từ chọn nằm trên thuộc tính phân vùng, truy vấn được hướng đến một nút duy nhất, tránh chi phí phụ trội của việc khởi động truy vấn trên tất cả 30 bộ xử lý. Thời gian đáp ứng cho truy vấn này tăng đáng kể khi kích thước

Table 3 - Selection Queries 30 Processors With Disks (All Execution Times in Seconds)

Bảng 3 - Các truy vấn chọn 30 Bộ xử lý với các đĩa (Tất cả thời gian thực thi tính bằng giây)

relation size is increased from 1 million to 10 million tuples because the height of the B-tree increases from two to three levels.

của quan hệ được tăng từ 1 triệu lên 10 triệu bộ từ vì chiều cao của B-tree tăng từ hai lên ba mức.

Speedup Experiments

Các thí nghiệm tăng tốc

In this section we examine how the response time for both the nonindexed and indexed selection queries on the 1 million tuple relation$^7$ is affected by the number of processors used to execute the query. Ideally, one would like to see a linear improvement in performance as the number of processors is increased from 1 to 30. Increasing the number of processors increases both the aggregate CPU power and I/O bandwidth available, while reducing the number of tuples that must be processed by each processor.

Trong phần này, chúng tôi xem xét cách thời gian đáp ứng của cả các truy vấn chọn không có chỉ mục và có chỉ mục trên quan hệ 1 triệu bộ từ¹ bị ảnh hưởng bởi số lượng bộ xử lý được sử dụng để thực thi truy vấn. Lý tưởng nhất là có thể thấy sự cải thiện tuyến tính về hiệu năng khi số lượng bộ xử lý được tăng từ 1 lên 30. Việc tăng số lượng bộ xử lý làm tăng cả công suất CPU tổng hợp và băng thông I/O khả dụng, đồng thời giảm số lượng bộ từ phải được xử lý bởi mỗi bộ xử lý.

In Figure 12, the average response times for the non-indexed 1% and 10% selection queries on the one million tuple relation are presented. As expected, the response time for each query decreases as the number of nodes is increased. The response time is higher for the 10% selection due to the cost of declustering and storing the result relation. While one could always store result tuples locally, by partitioning all result relations in a round-robin (or hashed) fashion one can ensure that the fragments of every result relation each contain approximately the same number of tuples. The speedup curves corresponding to Figure 12 are presented in Figure 13. In Figure 14, the average response time is presented as a function of the number of processors for the following three queries: a 1% selection through a clustered index, a 10% selection through a clustered index, and a 1% selection through a non-clustered index, all accessing the 1 million tuple relation. The corresponding speedup curves are presented in Figure 15.

Trong Hình 12, thời gian đáp ứng trung bình cho các truy vấn chọn không có chỉ mục 1% và 10% trên quan hệ một triệu bộ từ được trình bày. Như mong đợi, thời gian đáp ứng của mỗi truy vấn giảm khi số lượng nút được tăng lên. Thời gian đáp ứng cao hơn đối với phép chọn 10% do chi phí của việc phân cụm lại và lưu trữ quan hệ kết quả. Mặc dù luôn có thể lưu trữ các bộ từ kết quả cục bộ, bằng cách phân vùng tất cả các quan hệ kết quả theo cách round-robin (hoặc băm), có thể đảm bảo rằng các mảnh của mỗi quan hệ kết quả chứa xấp xỉ cùng một số lượng bộ từ. Các đường cong tăng tốc tương ứng với Hình 12 được trình bày trong Hình 13. Trong Hình 14, thời gian đáp ứng trung bình được trình bày như một hàm của số lượng bộ xử lý cho ba truy vấn sau: một phép chọn 1% thông qua chỉ mục phân cụm, một phép chọn 10% thông qua chỉ mục phân cụm, và một phép chọn 1% thông qua chỉ mục không phân cụm,

\footnotetext{7 The 1 million tuple relation was used for these experiments because the 10 million tuple relation would not fit on 1 disk drive.}

Hình 12

Of the speedup curves presented in Figures 13 and 14, three queries are superlinear, one is slightly sublinear, and one is significantly sublinear. Consider first the 10% selection via a relation scan, the 1% selection through a non-clustered index, and the 10% selection through a clustered index. As discussed above, the source of the superlinear speedups exhibited by these queries is due to significant differences in the time the various configurations spend seeking. With one processor, the 1 million tuple relation occupies approximately 66% of the disk. When the same relation is declustered over 30 disk drives, it occupies about 2% of each disk. In the case of the 1% non-clustered index selection, each tuple selected requires a random seek. With one processor, the range of the each random seek is approximately 800 cylinders while with 30 processors the range of the seek is limited to about 27 cylinders. Since the seek time is proportional to the square root of the distance traveled by the disk head [GRAY88], reducing the size of the relation fragment on each disk significantly reduces the amount of time that the query spends seeking.

Hình 13 chỉ mục phân cụm, tất cả đều truy cập quan hệ 1 triệu bộ từ. Các đường cong tăng tốc tương ứng được trình bày trong Hình 15.

A similar effect also happens with the 10% clustered index selection. In this case, once the index has been used to locate the tuples satisfying the query, each input page will produce one output page and at some point the buffer pool will be filled with dirty output pages. In order to write an output page, the disk head must be moved from its position over the input relation to the position on the disk where the output pages are to be placed. The relative cost of this seek decreases proportionally as the number of processors increases, resulting in a superlinear speedup for the query. The 10% non-indexed selection shown in Figure 13 is also superlinear for similar reasons. The reason that this query is not affected to the same degree is that, without an index, the seek time is a smaller fraction of the overall execution time of the query.

Trong số các đường cong tăng tốc được trình bày trong Hình 13 và 14, ba truy vấn là siêu tuyến tính, một truy vấn hơi dưới tuyến tính, và một truy vấn dưới tuyến tính đáng kể. Trước tiên, hãy xem xét phép chọn 10% thông qua quét quan hệ, phép chọn 1% thông qua chỉ mục không phân cụm, và phép chọn 10% thông qua chỉ mục phân cụm. Như đã thảo luận ở trên, nguồn gốc của các mức tăng tốc siêu tuyến tính thể hiện bởi các truy vấn này là do sự khác biệt đáng kể về thời gian mà các cấu hình khác nhau dành cho việc tìm kiếm. Với một bộ xử lý, quan hệ 1 triệu bộ từ chiếm xấp xỉ 66% đĩa. Khi cùng quan hệ đó được phân cụm lại trên 30 ổ đĩa, nó chiếm khoảng 2% của mỗi đĩa. Trong trường hợp chọn chỉ mục không phân cụm 1%, mỗi bộ từ được chọn yêu cầu một lần tìm kiếm ngẫu nhiên. Với một bộ xử lý, phạm vi của mỗi lần tìm kiếm ngẫu nhiên xấp xỉ 800 cylinder, trong khi với 30 bộ xử lý, phạm vi của lần tìm kiếm bị giới hạn khoảng 27 cylinder. Vì thời gian tìm kiếm tỷ lệ với căn bậc hai của khoảng cách mà đầu đĩa di chuyển [GRAY88], việc giảm kích thước của mảnh quan hệ trên mỗi đĩa làm giảm đáng kể lượng thời gian mà truy vấn dành cho việc tìm kiếm.

The 1% selection through a clustered index exhibits sublinear speedups because the cost of initiating a select and store operator on each processor (a total of 0.24 seconds for 30 processors) becomes a significant fraction of the total execution as the number of processors is increased.

Một hiệu ứng tương tự cũng xảy ra với phép chọn chỉ mục phân cụm 10%. Trong trường hợp này, một khi chỉ mục đã được sử dụng để định vị các bộ từ thỏa mãn truy vấn, mỗi trang đầu vào sẽ tạo ra một trang đầu ra và tại một thời điểm nào đó vùng bộ đệm sẽ được lấp đầy bằng các trang đầu ra bẩn. Để ghi một trang đầu ra, đầu đĩa phải được di chuyển

Scaleup Experiments

Hình 14

In the final set of selection experiments the number of processors was varied from 5 to 30 while the size of the input relations was increased from 1 million to 6 million tuples, respectively. As shown in Figure 16, the response time for each of the five selection queries remains almost constant. The slight increase in response time is due to the overhead of initiating a selection and store operator at each site. Since a single process is used to initiate the execution of a query, as the number of processors employed is increased, the load on this process is increased proportionally. Switching to a tree-based, query initiation scheme [GERB87] would distribute this overhead among all the processors.

Hình 15 từ vị trí của nó trên quan hệ đầu vào đến vị trí trên đĩa nơi các trang đầu ra được đặt. Chi phí tương đối của lần tìm kiếm này giảm tỷ lệ thuận khi số lượng bộ xử lý tăng lên, dẫn đến mức tăng tốc siêu tuyến tính cho truy vấn. Phép chọn không có chỉ mục 10% được thể hiện trong Hình 13 cũng siêu tuyến tính vì các lý do tương tự. Lý do truy vấn này không bị ảnh hưởng ở cùng mức độ là vì, không có chỉ mục, thời gian tìm kiếm chiếm một phần nhỏ hơn trong tổng thời gian thực thi của truy vấn.

RESPONSE TIME (SECONDS)

Phép chọn 1% thông qua chỉ mục phân cụm thể hiện các mức tăng tốc dưới tuyến tính vì chi phí khởi tạo toán tử chọn và lưu trữ trên mỗi bộ xử lý (tổng cộng 0.24 giây cho 30 bộ xử lý) trở thành một phần đáng kể của tổng quá trình thực thi khi số lượng bộ xử lý được tăng lên.

Figure 16

Các thí nghiệm mở rộng quy mô

6.3. Join Queries

Trong tập cuối cùng của các thí nghiệm selection, số lượng bộ xử lý được thay đổi từ 5 đến 30 trong khi kích thước của các quan hệ đầu vào được tăng tương ứng từ 1 triệu đến 6 triệu bộ. Như được thể hiện trong Figure 16, thời gian phản hồi cho mỗi trong năm truy vấn selection vẫn gần như không đổi. Sự gia tăng nhỏ trong thời gian phản hồi là do chi phí phụ trội của việc khởi tạo toán tử selection và store tại mỗi site. Vì một process đơn được sử dụng để khởi tạo việc thực thi của một truy vấn, khi số lượng bộ xử lý được sử dụng tăng lên, tải trên process này cũng tăng theo tỷ lệ. Chuyển sang sơ đồ khởi tạo truy vấn dựa trên cây [GERB87] sẽ phân phối chi phí phụ trội này giữa tất cả các bộ xử lý.

Like the selection queries in the previous section, we conducted three sets of join experiments. First, for two different join queries, we varied the size of the input relations while the configuration of processors was kept constant. Next, for one join query a series of speedup and scaleup experiments were conducted. For each of these tests, two different partitionings of the input relations were used. In the first case, the input relations were declustered by hashing on the join attribute. In the second case, the input relations were declustered using a different attribute. The hybrid join algorithm was used for all queries.

Figure 16

Performance Relative to Relation Size

6.3. Các truy vấn Join

The first join query [BITT83], joinABprime, is a simple join of two relations: A and Bprime. The A relation contains either 100,000, 1 million, or 10 million tuples. The Bprime relation contains, respectively, 10,000, 100,000, or 1 million tuples. The result relation has the same number of tuples as the Bprime relation.\footnote{For each join operation, the result relation contains all the fields of both input relations and thus the result tuples are 416 bytes wide.} The second query, joinAselB, is composed of one join and one selection. A and B have the same number of tuples and the selection on B reduces the size of B to the size of the Bprime relation in the corresponding joinABprime query. The result relation for this query has the same number of tuples as in the corresponding joinABprime query. As an example, if A has 10 million tuples, then joinABprime joins A with a Bprime relation that contains 1 million tuples, while in joinAselB the selection on B restricts B from 10 million tuples to 1 million tuples and then joins the result with A.

Giống như các truy vấn selection trong phần trước, chúng tôi đã tiến hành ba tập thí nghiệm join. Trước tiên, đối với hai truy vấn join khác nhau, chúng tôi thay đổi kích thước của các quan hệ đầu vào trong khi cấu hình của các bộ xử lý được giữ không đổi. Tiếp theo, đối với một truy vấn join, một loạt các thí nghiệm speedup và scaleup đã được tiến hành. Với mỗi phép kiểm tra này, hai cách phân vùng khác nhau của các quan hệ đầu vào đã được sử dụng. Trong trường hợp thứ nhất, các quan hệ đầu vào được decluster bằng cách băm trên thuộc tính join. Trong trường hợp thứ hai, các quan hệ đầu vào được decluster bằng cách sử dụng một thuộc tính khác. Thuật toán join lai được sử dụng cho tất cả các truy vấn.

The first variation of the join queries tested involved no indices and used a non-partitioning attribute for both the join and selection attributes. Thus, before the join can be performed, the two input relations must be redistributed by hashing on the join attribute value of each tuple. The results from these tests are contained in the first 2 rows of Table 4. The second variation of the join queries also did not employ any indices but, in this case, the relations were hash partitioned on the joining attribute; enabling the redistribution phase of the join to be skipped. The results for these tests are contained in last 2 rows of Table 4.

Hiệu năng tương đối so với kích thước quan hệ

The results in Table 4 indicate that the execution time of each join query increases in a fairly linear fashion as the size of the input relations are increased. Gamma does not exhibit linearity for the 10 million tuple queries because the size of the inner relation (208 megabytes) is twice as large as the total available space for hash tables. Hence, the Hybrid join algorithm needs two buckets to process these queries. While the tuples in the first bucket can be placed directly into memory-resident hash tables, the second bucket must be written to disk (see Section 4.2).

Truy vấn join đầu tiên [BITT83], joinABprime, là một phép join đơn giản của hai quan hệ: A và Bprime. Quan hệ A chứa lần lượt 100,000, 1 triệu, hoặc 10 triệu bộ. Quan hệ Bprime chứa tương ứng 10,000, 100,000, hoặc 1 triệu bộ. Quan hệ kết quả có cùng số lượng bộ như quan hệ Bprime.¹ Truy vấn thứ hai, joinAselB, bao gồm một phép join và một phép selection. A và B có cùng số lượng bộ và phép

As expected, the version of each query in which the partitioning attribute was used as the join attribute ran faster. From these results one can estimate a lower bound on the aggregate rate at which data can be redistributed by the Intel iPSC/2 hypercube. Consider the version of the joinABprime query in which a million tuple relation is

selection trên B làm giảm kích thước của B xuống kích thước của quan hệ Bprime trong truy vấn joinABprime tương ứng. Quan hệ kết quả của truy vấn này có cùng số lượng bộ như trong truy vấn joinABprime tương ứng. Ví dụ, nếu A có 10 triệu bộ, thì joinABprime thực hiện join A với một quan hệ Bprime chứa 1 triệu bộ, trong khi trong joinAselB phép selection trên B giới hạn B từ 10 triệu bộ xuống 1 triệu bộ và sau đó thực hiện join kết quả với A.

Table 4 - Join Queries 30 Processors With Disks (All Execution Times in Seconds)

Biến thể đầu tiên của các truy vấn join được kiểm tra không sử dụng chỉ mục và sử dụng một thuộc tính không phân vùng cho cả thuộc tính join và thuộc tính selection. Do đó, trước khi phép join có thể được thực hiện, hai quan hệ đầu vào phải được phân phối lại bằng cách băm trên giá trị thuộc tính join của mỗi bộ. Kết quả từ các phép kiểm tra này được trình bày trong 2 hàng đầu tiên của Table 4. Biến thể thứ hai của các truy vấn join cũng không sử dụng bất kỳ chỉ mục nào nhưng trong trường hợp này, các quan hệ được phân vùng băm trên thuộc tính join; cho phép bỏ qua giai đoạn phân phối lại của phép join. Kết quả cho các phép kiểm tra này được trình bày trong 2 hàng cuối của Table 4.

Các kết quả trong Table 4 chỉ ra rằng thời gian thực thi của mỗi truy vấn join tăng theo cách gần tuyến tính khi kích thước của các quan hệ đầu vào tăng lên. Gamma không thể hiện tính tuyến tính đối với các truy vấn 10 triệu bộ vì kích thước của quan hệ bên trong (208 megabyte) lớn gấp hai lần không gian khả dụng tổng cộng cho các bảng băm. Vì vậy, thuật toán join Hybrid cần hai bucket để xử lý các truy vấn này. Trong khi các bộ trong bucket đầu tiên có thể được đặt trực tiếp vào các bảng băm cư trú trong bộ nhớ, bucket thứ hai phải được ghi ra disk (xem Section 4.2).

joined with a 100,000 tuple relation. This query requires 28.69 seconds when the join is not on the partitioning attribute. During the execution of this query, 1.1 million 208 byte tuples must be redistributed by hashing on the join attribute, yielding an aggregate total transfer rate of 7.9 megabytes/second during the processing of this query. This should not be construed, however, as an accurate estimate of the maximum obtainable interprocessor communications bandwidth as the CPUs may be the limiting factor (the disks are not likely to be the limiting factor as from Table 3 one can estimate that the aggregate bandwidth of the 30 disks to be about 25 megabytes/second).

Như dự kiến, phiên bản của mỗi truy vấn trong đó thuộc tính phân vùng được sử dụng làm thuộc tính join chạy nhanh hơn. Từ các kết quả này, có thể ước lượng một cận dưới về tốc độ tổng hợp mà dữ liệu có thể được phân phối lại bởi hypercube Intel iPSC/2. Xét phiên bản của truy vấn joinABprime trong đó một quan hệ một triệu bộ được

Speedup Experiments

Table 4 - Các truy vấn Join 30 Bộ xử lý với Disk (Tất cả thời gian thực thi tính bằng giây)

For the join speedup experiments, we used the joinABprime query with a 1 million tuple A relation and a 100,000 tuple Bprime relation. The number of processors was varied from five to thirty. Since with fewer than five processors two or more buckets are needed, including the execution time for one processor (which needs 5 buckets) would have made the response times for five or more processors appear artificially fast; resulting in superlinear speedup curves.

The resulting response times are plotted in Figure 17 and the corresponding speedup curves are presented in Figure 18. From the shape of these graphs it is obvious that the execution time for the query is significantly reduced as additional processors are employed. Several factors prevent the system from achieving perfectly linear speedups.

join với một quan hệ 100,000 bộ. Truy vấn này cần 28.69 giây khi phép join không được thực hiện trên thuộc tính phân vùng. Trong quá trình thực thi truy vấn này, 1.1 triệu bộ 208 byte phải được phân phối lại bằng cách băm trên thuộc tính join, tạo ra tốc độ truyền tổng hợp là 7.9 megabyte/giây trong quá trình xử lý truy vấn này. Tuy nhiên, điều này không nên được xem là một ước lượng chính xác về băng thông truyền thông giữa các bộ xử lý tối đa có thể đạt được vì các CPU có thể là yếu tố giới hạn (các disk khó có khả năng là yếu tố giới hạn vì từ Table 3 có thể ước lượng rằng băng thông tổng hợp của 30 disk là khoảng 25 megabyte/giây).

PROCESSORS WITH DISKS hash partitioned on non-join attribute hash partitioned on join attribute Figure 17)

Các thí nghiệm Speedup

Figure.

Đối với các thí nghiệm speedup của join, chúng tôi sử dụng truy vấn joinABprime với một quan hệ A có 1 triệu bộ và một quan hệ Bprime có 100,000 bộ. Số lượng bộ xử lý được thay đổi từ năm đến ba mươi. Vì với ít hơn năm bộ xử lý cần hai hoặc nhiều bucket, việc bao gồm thời gian thực thi cho một bộ xử lý (cần 5 bucket) sẽ khiến thời gian phản hồi cho năm hoặc nhiều bộ xử lý xuất hiện nhanh một cách giả tạo; dẫn đến các đường cong speedup siêu tuyến tính.

First, the cost of starting four operator tasks (two scans, one join, and one store) on each processor increases as a function of the number of processors used. Second, the effect of short-circuiting local messages diminishes as the number of processors is increased. For example, consider a five processor configuration and the non-partitioning attribute version of the JoinABprime query. As each processor repartitions tuples by hashing on the join attribute, 1/5th of the input tuples it processes are destined for itself and will be short-circuited by the communications software. In addition, as the query produces tuples of the result relation (which is partitioned in a round-robin manner), they too will be short circuited. As the number of processors is increased, the number of short-circuited packets decreases to the point where, with 30 processors, only 1/30th of the packets will be short-circuited. Because these intra-node packets are less expensive than their corresponding inter-node packets, smaller configurations will benefit more from short-circuiting. In the case of a partitioning-attribute joins, all input tuples will short-circuit the network along with a fraction of the output tuples.

Thời gian đáp ứng thu được được biểu diễn trong Hình 17 và các đường cong tăng tốc tương ứng được trình bày trong Hình 18. Từ hình dạng của các đồ thị này, rõ ràng rằng thời gian thực thi của truy vấn được giảm đáng kể khi sử dụng thêm các bộ xử lý. Một số yếu tố ngăn hệ thống đạt được mức tăng tốc tuyến tính hoàn hảo.

Scaleup Experiments

Hình 17

The JoinABprime query was also used for the join scaleup experiments. For these tests, the number of processors was varied from 5 to 30 while the size of the A relation was varied from 1 million to 6 million tuples in increments of 1 million tuples and the size of Bprime relation was varied from 100,000 to 600,000 tuples in increments of 100,000. For each configuration, only one join bucket was needed. The results of these tests are presented in Figure 19. Three factors contribute to the slight increase in response times. First, the task of initiating 4 processes at each site is performed by a single processor. Second, as the number of processors increases, the effects of short-circuiting messages during the execution of these queries diminishes - especially in the case when the join attribute is not the partitioning attribute. Finally, the response time may be being limited by the speed of the communications network.

Hình 18

RESPONSE TIME (SECONDS) hash partitioned on non-join attribute hash partitioned on join attribute

Thứ nhất, chi phí khởi động bốn tác vụ toán tử (hai phép quét, một phép nối, và một phép lưu trữ) trên mỗi bộ xử lý tăng theo số lượng bộ xử lý được sử dụng. Thứ hai, ảnh hưởng của việc bỏ qua các thông điệp cục bộ giảm khi số lượng bộ xử lý tăng lên. Ví dụ, xét một cấu hình năm bộ xử lý và phiên bản thuộc tính không phân vùng của truy vấn JoinABprime. Khi mỗi bộ xử lý phân vùng lại các bộ bằng cách băm trên thuộc tính nối, 1/5 số bộ đầu vào mà nó xử lý được dành cho chính nó và sẽ được phần mềm truyền thông bỏ qua. Ngoài ra, khi truy vấn tạo ra các bộ của quan hệ kết quả (được phân vùng theo cách vòng tròn), chúng cũng sẽ được bỏ qua. Khi số lượng bộ xử lý tăng lên, số lượng gói tin được bỏ qua giảm đến mức với 30 bộ xử lý, chỉ 1/30 số gói tin được bỏ qua. Vì các gói tin nội nút này ít tốn kém hơn so với các gói tin liên nút tương ứng, các cấu hình nhỏ hơn sẽ hưởng lợi nhiều hơn từ việc bỏ qua. Trong trường hợp các phép nối theo thuộc tính phân vùng, tất cả các bộ đầu vào sẽ bỏ qua mạng cùng với một phần các bộ đầu ra.

PROCESSORS WITH DISKS

Các thí nghiệm mở rộng quy mô

Figure 19

Truy vấn JoinABprime cũng được sử dụng cho các thí nghiệm mở rộng quy mô của phép nối. Đối với các phép thử này, số lượng bộ xử lý được thay đổi từ 5 đến 30 trong khi kích thước của quan hệ A được thay đổi từ 1 triệu đến 6 triệu bộ theo các bước tăng 1 triệu bộ và kích thước của quan hệ Bprime được thay đổi từ 100,000 đến 600,000 bộ theo các bước tăng 100,000. Với mỗi cấu hình, chỉ cần một bucket nối. Kết quả của các phép thử này được trình bày trong Hình 19. Ba yếu tố góp phần làm tăng nhẹ thời gian đáp ứng. Thứ nhất, tác vụ khởi tạo 4 tiến trình tại mỗi site được thực hiện bởi một bộ xử lý duy nhất. Thứ hai, khi số lượng bộ xử lý tăng lên, ảnh hưởng của việc bỏ qua thông điệp trong quá trình thực thi các truy vấn này giảm đi - đặc biệt trong trường hợp thuộc tính nối không phải là thuộc tính phân vùng. Cuối cùng, thời gian đáp ứng có thể bị giới hạn bởi tốc độ của mạng truyền thông.

6.4. Aggregate Queries

Hình 19

Our aggregate tests included a mix of scalar aggregate and aggregate function queries run on the 30 processor configuration. The first query computes the minimum of a non-indexed attribute. The next two queries compute, respectively, the sum and minimum of an attribute after partitioning the relation into 20 subsets. Three sizes of input relations were used: 100,000, 1 million, and 10 million tuples. The results from these tests are contained in Table 5. Since the scalar aggregates and aggregate function operators are executed using algorithms that are similar to those used by the selection and join operators, respectively, no speedup or scaleup experiments were conducted.

6.4. Các truy vấn tổng hợp

Table 5 - Aggregate Queries 30 Processors with Disks (All Execution Times in Seconds)

Các phép thử tổng hợp của chúng tôi bao gồm sự kết hợp giữa các truy vấn tổng hợp vô hướng và các truy vấn hàm tổng hợp chạy trên cấu hình 30 bộ xử lý. Truy vấn đầu tiên tính giá trị nhỏ nhất của một thuộc tính không có chỉ mục. Hai truy vấn tiếp theo lần lượt tính tổng và giá trị nhỏ nhất của một thuộc tính sau khi phân vùng quan hệ thành 20 tập con. Ba kích thước của quan hệ đầu vào được sử dụng: 100,000, 1 triệu, và 10 triệu bộ. Kết quả từ các phép thử này được chứa trong Bảng 5. Vì các toán tử tổng hợp vô hướng và toán tử hàm tổng hợp được thực thi bằng các thuật toán tương tự như các thuật toán được sử dụng bởi các toán tử chọn và nối, tương ứng, nên không tiến hành các thí nghiệm tăng tốc hoặc mở rộng quy mô.

Bảng 5 - Các truy vấn tổng hợp 30 Bộ xử lý với Đĩa (Tất cả thời gian thực thi tính bằng giây)

6.5. Update Queries

The next set of tests included a mix of append, delete, and modify queries on three different sizes of relations: 100,000, 1 million, and 10 million tuples. The results of these tests are presented in Table 6. Since Gamma’s recovery mechanism is not yet operational, these results should be viewed accordingly.

6.5. Các truy vấn cập nhật

The first query appends a single tuple to a relation on which no indices exist. The second appends a tuple to a relation on which one index exists. The third query deletes a single tuple from a relation, using a clustered B-tree index to locate the tuple to be deleted. In the first query no indices exist and hence no indices need to be updated, whereas in the second and third queries, one index needs to be updated.

Tập các phép thử tiếp theo bao gồm sự kết hợp giữa các truy vấn thêm, xóa và sửa đổi trên ba kích thước quan hệ khác nhau: 100,000, 1 triệu, và 10 triệu bộ. Kết quả của các phép thử này được trình bày trong Bảng 6. Vì cơ chế phục hồi của Gamma vẫn chưa hoạt động, các kết quả này cần được xem xét tương ứng.

The fourth through sixth queries test the cost of modifying a tuple in three different ways. In all three tests, a non-clustered index exists on the unique2 attribute, and, in addition, a clustered index exists on the Unique1 attribute. In the first case, the modified attribute is the partitioning attribute, thus requiring that the modified tuple be relocated. Furthermore, since the tuple is relocated, the secondary index must also be updated. The second modify query modifies a non-partitioning, nonindexed attribute. The third modify query modifies an attribute on which a non-clustered index has been constructed, using the index to locate the tuple to be modified.

Truy vấn đầu tiên thêm một bộ đơn vào một quan hệ không tồn tại chỉ mục nào. Truy vấn thứ hai thêm một bộ vào một quan hệ có một chỉ mục tồn tại. Truy vấn thứ ba xóa một bộ đơn khỏi một quan hệ, sử dụng chỉ mục B-tree phân cụm để định vị bộ cần xóa. Trong truy vấn đầu tiên không có chỉ mục nào tồn tại và do đó không cần cập nhật chỉ mục nào, trong khi ở truy vấn thứ hai và thứ ba, một chỉ mục cần được cập nhật.

Table 6 - Update Queries 30 Processors With Disks (All Execution Times in Seconds)

Các truy vấn thứ tư đến thứ sáu kiểm tra chi phí sửa đổi một bộ theo ba cách khác nhau. Trong cả ba phép thử, một chỉ mục không phân cụm tồn tại trên thuộc tính unique2, và ngoài ra, một chỉ mục phân cụm tồn tại trên thuộc tính Unique1. Trong trường hợp đầu tiên, thuộc tính được sửa đổi là thuộc tính phân vùng, do đó yêu cầu bộ được sửa đổi phải được định vị lại. Hơn nữa, vì bộ được định vị lại, chỉ mục thứ cấp cũng phải được cập nhật. Truy vấn sửa đổi thứ hai sửa đổi một thuộc tính không phân vùng, không có chỉ mục. Truy vấn sửa đổi thứ ba sửa đổi một thuộc tính trên đó một chỉ mục không phân cụm đã được xây dựng, sử dụng chỉ mục để định vị bộ cần sửa đổi.

Bảng 6 - Các truy vấn cập nhật 30 Bộ xử lý Với Đĩa (Tất cả thời gian thực thi tính bằng giây)

Nothing here.

7 Conclusions and Future Research Directions

7 Các kết luận và hướng nghiên cứu trong tương lai

In this paper we have described the design and implementation of the Gamma database machine. Gamma employs a shared-nothing architecture in which each processor has one or more disks and the processors can communicate with each other only by sending messages via an interconnection network. While a previous version of the Gamma software ran on a collection of VAX 11/750s interconnected via a 80 mbit/second token ring, currently the system runs on an Intel iPSC/2 hypercube with 32 processors and 32 disk drives.

Trong bài báo này, chúng tôi đã mô tả thiết kế và triển khai của máy cơ sở dữ liệu Gamma. Gamma sử dụng kiến trúc không chia sẻ (shared-nothing) trong đó mỗi bộ xử lý có một hoặc nhiều đĩa và các bộ xử lý chỉ có thể giao tiếp với nhau bằng cách gửi thông điệp thông qua một mạng liên kết. Trong khi phiên bản trước của phần mềm Gamma chạy trên một tập hợp các VAX 11/750 được liên kết với nhau thông qua một vòng token 80 mbit/giây, hiện tại hệ thống chạy trên một siêu khối iPSC/2 của Intel với 32 bộ xử lý và 32 ổ đĩa.

Gamma employs three key ideas which enable the architecture to be scaled to 100s of processors. First, all relations are horizontally partitioned across multiple disk drives which are attached to separate processors; enabling relations to be scanned in parallel without any specialized hardware. In addition, in order to enable the database design to be tuned to the needs of the application, three alternative partitioning strategies are provided. The second major contribution of the Gamma software is its extensive use of hash-based parallel algorithms for processing complex relational operators such as joins and aggregate functions. Finally, the system employs unique dataflow scheduling techniques to coordinate the execution of multioperator queries. These techniques make it possible to control the execution of very complex queries with minimal coordination - a necessity for configurations involving a large number of processors

Gamma sử dụng ba ý tưởng then chốt cho phép kiến trúc được mở rộng tới hàng trăm bộ xử lý. Thứ nhất, tất cả các quan hệ được phân vùng ngang trên nhiều ổ đĩa được gắn với các bộ xử lý riêng biệt; cho phép các quan hệ được quét song song mà không cần bất kỳ phần cứng chuyên dụng nào. Ngoài ra, để cho phép thiết kế cơ sở dữ liệu được điều chỉnh theo nhu cầu của ứng dụng, ba chiến lược phân vùng thay thế được cung cấp. Đóng góp lớn thứ hai của phần mềm Gamma là việc sử dụng rộng rãi các thuật toán song song dựa trên băm để xử lý các toán tử quan hệ phức tạp như các phép nối và các hàm tổng hợp. Cuối cùng, hệ thống sử dụng các kỹ thuật lập lịch luồng dữ liệu độc đáo để phối hợp việc thực thi các truy vấn đa toán tử. Các kỹ thuật này giúp có thể kiểm soát việc thực thi các truy vấn rất phức tạp với sự phối hợp tối thiểu - một yêu cầu cần thiết đối với các cấu hình liên quan đến số lượng lớn bộ xử lý

In addition to describing the design of the Gamma software, we have also presented a thorough performance evaluation of the iPSC/2 hypercube version of Gamma. Three sets of experiments were performed. First, with a constant machine configuration of 30 processors, the response for the standard set of Wisconsin benchmark queries was measured for 3 different sizes of relations. For a subset of these queries we also measured the performance of the system relative to the number of processors employeed when the sizes of the input relations are kept constant (speedup) and when the sizes of the input relations are increased proportionally to the number of processors (scaleup). The speedup results obtained for both selection and join queries are almost perfectly linear; thus doubling the number of processors halves the response time for a query. The scaleup results obtained are also quite encouraging. They reveal that a constant response time can be maintained for both selection and join queries as the workload is increased by adding a proportional number of processors and disks.

Ngoài việc mô tả thiết kế của phần mềm Gamma, chúng tôi cũng đã trình bày một đánh giá hiệu năng toàn diện của phiên bản Gamma trên siêu khối iPSC/2. Ba nhóm thí nghiệm đã được thực hiện. Thứ nhất, với một cấu hình máy cố định gồm 30 bộ xử lý, thời gian đáp ứng cho tập truy vấn chuẩn của phép đo chuẩn Wisconsin được đo với 3 kích thước khác nhau của các quan hệ. Đối với một tập con các truy vấn này, chúng tôi cũng đo hiệu năng của hệ thống tương ứng với số lượng bộ xử lý được sử dụng khi kích thước của các quan hệ đầu vào được giữ cố định (tăng tốc) và khi kích thước của các quan hệ đầu vào được tăng tỷ lệ thuận với số lượng bộ xử lý (mở rộng quy mô). Các kết quả tăng tốc thu được cho cả truy vấn chọn và truy vấn nối gần như tuyến tính hoàn hảo; do đó tăng gấp đôi số lượng bộ xử lý sẽ giảm một nửa thời gian đáp ứng cho một truy vấn. Các kết quả mở rộng quy mô thu được cũng rất đáng khích lệ. Chúng cho thấy thời gian đáp ứng không đổi có thể được duy trì cho cả các truy vấn chọn và truy vấn nối khi tải công việc được tăng lên bằng cách thêm số lượng bộ xử lý và đĩa tỷ lệ thuận.

We currently have a number of new projects underway. First, we plan on implementing the chained declustering mechanism and evaluating its effectiveness. With respect to processing queries, we have designed [SCHN89b] and are currently evaluating alternative strategies for processing queries involving multiple join operations. For example, consider a query involving 10 joins on a machine with 100 processors. Is it better to use all 100 processors for each join (allocating 1/10 of the memory on each processor to each join), or to use 10 processors for each join (in which case each join operator will have full use of the memory at each processor)? Finally, we are studying several new partitioning mechanisms that combine the best features of the hash and range partitioning strategies.

Hiện tại chúng tôi đang tiến hành một số dự án mới. Thứ nhất, chúng tôi dự định triển khai cơ chế phân cụm liên kết và đánh giá tính hiệu quả của nó. Liên quan đến việc xử lý truy vấn, chúng tôi đã thiết kế [SCHN89b] và hiện đang đánh giá các chiến lược thay thế để xử lý các truy vấn liên quan đến nhiều phép nối. Ví dụ, xét một truy vấn liên quan đến 10 phép nối trên một máy có 100 bộ xử lý. Liệu tốt hơn là sử dụng tất cả 100 bộ xử lý cho mỗi phép nối (phân bổ 1/10 bộ nhớ trên mỗi bộ xử lý cho mỗi phép nối), hay sử dụng 10 bộ xử lý cho mỗi phép nối (trong trường hợp này mỗi toán tử nối sẽ được sử dụng toàn bộ bộ nhớ tại mỗi bộ xử lý)? Cuối cùng, chúng tôi đang nghiên cứu một số cơ chế phân vùng mới kết hợp các đặc điểm tốt nhất của các chiến lược phân vùng băm và phân vùng theo khoảng.

8 Acknowledgements

8 Lời cảm ơn

Like all large systems projects, a large number of people beyond those listed as authors made this paper possible. Bob Gerber deserves special recognition for his work on the design of Gamma plus his leadership on the implementation of the first prototype. The query optimizer was implemented by M. Muralikrishna. Rajiv Jauhari implemented the read-ahead mechanism to improve the performance of sequential scans. Anoop Sharma implemented both the aggregate algorithms and the embedded query interface. Goetz Graefe and Joanna Chen implemented a predicate compiler. They deserve special credit for being willing to debug the machine code produced by the compiler.

Giống như mọi dự án hệ thống lớn, một số lượng lớn người ngoài những người được liệt kê là tác giả đã làm cho bài báo này có thể thực hiện được. Bob Gerber xứng đáng nhận được sự ghi nhận đặc biệt vì công việc của ông trong việc thiết kế Gamma cùng với vai trò lãnh đạo của ông trong việc triển khai nguyên mẫu đầu tiên. Bộ tối ưu hóa truy vấn được M. Muralikrishna triển khai. Rajiv Jauhari đã triển khai cơ chế đọc trước để cải thiện hiệu năng của các phép quét tuần tự. Anoop Sharma đã triển khai cả các thuật toán tổng hợp và giao diện truy vấn nhúng. Goetz Graefe và Joanna Chen đã triển khai một trình biên dịch vị từ. Họ xứng đáng nhận được sự ghi nhận đặc biệt vì đã sẵn sàng gỡ lỗi mã máy do trình biên dịch tạo ra.

We would also like to thank Jim Gray and Susan Englert of Tandem Computers for the use of their Wisconsin benchmark relation generator. Without this generator the tests we conducted would simply not have been possible as previously we had no way of generating relations larger than 1 million tuples.

Chúng tôi cũng muốn cảm ơn Jim Gray và Susan Englert của Tandem Computers vì đã cho phép sử dụng bộ sinh quan hệ phép đo chuẩn Wisconsin của họ. Nếu không có bộ sinh này, các phép kiểm thử mà chúng tôi tiến hành đơn giản là không thể thực hiện được, vì trước đó chúng tôi không có cách nào tạo ra các quan hệ lớn hơn 1 triệu bộ.