JPS61273633A - Joint processing system for decentralized data base - Google Patents

Abstract

PURPOSE:To improve the processing efficiency in a joint process by transmitting the number of tuples at the side having the smaller number of hash sorts with the hash packets at both sites according to the result of the hash sorting. CONSTITUTION:When a hash processing part 3 of a processor 1 is started, the tuples of the desired relation are read successively outpof a data base. These tuples are sorted to one of hash packets 11-0-11-p corresponding to the hash function valve of the prescribed join field value. then the number of tuples are informed to a short informing part 4. The part 4 transfers the number of tuples to a communication processing part 2 and an array comparison part 5. The part 5 receives the number of hash sorts from the site at the remote side and compares them with those at the own site. Then the part 5 transmits the tapples sorted to the packets even with the packet having a small number of hash sorts of the own site. The result of said comparison is sent to a joint processing part 6 for execution of the joint processing with the tuples received from the remote side for the packet whose joint processing should be applied at the own site.

Description

[Detailed Description of the Invention] [Summary] This is a method of join processing between two sites of distributed relational databases. For each site's relation, the tuples are classified by the hash function of the join field, and the number of each tuple in the classified optical hash bucket is notified to the other site. By comparing the number of tuples in each hash bucket at each site, transferring tuples from the side with fewer tuples, and performing join processing at the other site, the amount of transfer can be reduced.

[Industrial application field]

The present invention relates to a processing method for performing a join between two distributed relational database sites in an information processing system.

Relational databases are becoming popular as the main database method of the future.

Also, an information processing system having a so-called distributed database, in which a database is distributed to computers located at sites separated from each other and connected through a communication path, is also well known.

When performing so-called natural join processing on such distributed relational databases, it is essential to transfer data between sites.
It is desirable to reduce the amount of data transferred as much as possible.

[Prior Art and Problems to be Solved by the Invention] As is well known, a relational database consists of one or more relations, and each relation generally consists of one table consisting of a plurality of tuples (tuρIe). Configure.

Each tuple is data composed of one or more fields.

In relational database processing, so-called natural joins between two relations are used.
ral join) operations are used relatively frequently.

A natural join (hereinafter simply referred to as a join) is to search for tuples whose field values are -i in both rules for specified fields of two relations (this is referred to as a join field), and to search for tuples whose field values are -i in both rules. It refers to constructing a new fusion consisting of tuples created by combining fields.

The join process is basically a process of searching for a tupple with a join field that matches the join field value from among all tuples of the second joining fusion for each tupple for all tuples of the first joining fusion. must be done.

In this way, the join process is a process of comparing predetermined fields for all tuples of two relations and combining the matched tuples, so in a distributed database, for example, relation A and When performing a join with relation B, in principle, for example, transfer illusion B from site sb to site Sa, configure copy fusion B° on site Sa, and then create relation A and fusion B'.
The join process will be performed with .

When a distributed database join process is performed in this manner, a large amount of data transfer is required if the relation is large, so methods have been considered to reduce the amount of data transferred.

In a method using hashing, tuples are classified according to appropriate hash function values of join field values to create so-called hash buckets, and this classification is used to perform join processing.

As the hash function, various functions can be used as is well known, but for example, the value of the join field is an integer, and the remainder is used when it is divided by a predetermined integer. It is generated as a table classified by category.

After classifying in this way, it is only necessary to perform join processing between corresponding hash buckets (with the same hash function) created from both relations, and do not take into account hash buckets with different hash function values. It is clear that there is no need to do so.

When performing join processing between two sites, each site
After classifying the hashes of the rules it owns as described above, one site creates a bitmap indicating whether each hash bucket has tuples or not, and one site notifies the other site of the bitmap.

As a result, if at least one of the bitmaps is displayed as having no tuples, there is no need to transfer tuples for that hash bucket, so there is a possibility that the amount of data transferred can be reduced.

However, if both sites have tuples in the corresponding hash bucket, or if both sites do not have tuples, this method does not change the required amount of data to be transferred for that bucket part, so the entire hash bucket If there are tuples in , no reduction in the amount of data transfer can be obtained.

[Means for solving problems]

FIG. 1 is a block diagram showing the configuration of the present invention.

The figure shows the configuration of one site of the distributed database system, and the processing bag W1 of each site is processed by the communication processing unit 2.
can communicate with each other.

The processing device 1 includes a hash processing section 3, a classification number notification section 4,
An array comparison processing section 5 and a join processing section 6 are provided.

[For production]

When the hash processing unit 3 of the processing device 1 of the two required sites is activated for join processing, it sequentially reads tuples of the required relation from the database 10 and corresponds to the hash function value of the predetermined join field value. Hashbucket 11-0.11-1, -111-
Classify the tuple into one of p.

Once all the tuples are classified, the number of tuples in each hash bucket is passed to the classification number notification unit 4.

The classification number notification section 4 passes this to the communication processing section 2 and also transfers it to the sequence comparison processing section 5 so as to transmit it to the other site.

The sequence comparison processing unit 5 receives the number of classifications sent from the other site and compares it with the number of classifications at its own site. the result,
Regarding hash buckets with a small number of classifications on your site,
Send the tuples classified into that bucket to the other site. In addition, the same number of buckets will be sent to the other site only if it is specified that they should be sent from the own site.

Further, the comparison result is passed to the join processing section 6.

The join processing unit 6 selects the tuples and hash buckets 11-0 received from the other site regarding the hash buckets to which the own site should perform join processing based on the comparison result.
- 11-Sequentially execute join processing with the tuples of p.

With the above control, even if there are tuples in the hash buckets of both sites as a result of hash classification, the smaller tuples are always transmitted, so the number of tuples in the corresponding hash bucket is generally smaller than the amount of data to be transmitted. You will get a reduction.

〔Example〕

The join process is started, for example, by inputting a known database inquiry command to the command processing unit 12 in FIG. 1 from a terminal device or the like.

The command processing unit 12 analyzes the command, identifies the relations to be joined, detects the sites that hold them, passes the results and other join specification conditions to the hash processing unit 3, and If the relation is at another site, it is transmitted to the desired partner site via the communication processing unit 2.

At the other site, this information is sent to the communication processing unit 2 of that site.
The received data is passed to the hash processing section 3, and the hash processing sections 3 at the two sites start processing in this manner.

The hash processing unit 3 reads the tuples of the specified relation from the database 10, and calculates a predetermined hash function value from the value of the specified join field.

As the hash function, for example, the content of the join field is assumed to be an integer, and the remainder of that value by the integer p+1 is used, and both sites must use the same function.

In this case, the processing device 1 has a function value of 0.1. p+1 hash buckets 11-0 to 11-p corresponding to -p
and classifies tuples into corresponding buckets according to the function value obtained from the join field as described above.

When the specified relation is classified by hashing, each hash bucket 1 accumulated during the classification process is
A tuple number array of p+1 elements consisting of tuples from 1-0 to 11-p is passed to the classification number notification unit 4.

The classification number notification unit 4 transfers the tuple number array to the rearrangement comparison processing unit 5 of the own site and the other site.

As a result of the above control being performed at both sites, the sequence comparison processing units 5 at both sites have tuple number arrays at both sites.

The sequence comparison processing unit 5 compares the tuple number arrays of both sites, and for each corresponding hash bucket, the site with the smaller number of tuples sends the tuples of its own site classified there to the other site. Process as follows.

For hash buckets with the same number of tuples, for example, the site addresses of both sites are compared, and the rule is to send the hash bucket's nuple from the site with the larger address value to the site with the smaller address value.

With the above control, if the number of tuples of at least one of the pairs is 0, the transmission of evening and noples does not occur for that pair of no\ and noshubakesoto, as in the conventional case.

Transmission of the tuples to the other site is completed by sequentially transmitting only the tuples of the hash buckets that require transmission, for example from the no\nosh buckets 11-0 to 11-p.

At both sites, the join processing unit 6 receives the tuples received from the other site via the communication processing unit 2, and the join control information (for example, the hash for receiving Yu/Nople) of the comparison result passed from the array comparison processing unit 5. (buckets and information indicating the number of received nodes/noples), join processing is executed for the required tuples and nodes, and the tuples generated by the join processing are transferred to the site specified by the command and created as a new site. A relation is configured.

An example of the above processing is shown in FIG. The figure assumes that a join process is performed between relation A on site Sa and relation B on site sb, and hash buckets ^o, Als At and Bo,
The case of classification into B+ and Bz is shown.

As a result, if the values shown in Ha and Hb are obtained as the tuple number array, the sequence comparison processing unit 5 of both sites will:
Comparing the corresponding terms of a and Hb, site Sa transmits the 8-tuple of hash bucket A2 to site sb.

Site sb detects that the number of tuples in hash buckets B0 and Bl is smaller than hash bucket AO%^, respectively, but since the number of tuples in hash bucket node B1 is O, there is no transmission, and only 3 tuples of Bo. is sent to site Sa.

From the above, in the present invention, the total number of tuples to be transmitted is 8+3
=11.

If this example is processed using the conventional method, the number of transmission tuples will be 3+10=13 (the transfer direction is from site Sb to
Sa), or 6+8=14 (sites 5a-5b
), so it is clear that the present invention can reduce the number of transmission buckets.

〔Effect of the invention〕

As is clear from the above description, according to the present invention, in join processing of a distributed database, the number of tuples required to be transmitted is reduced, resulting in a reduction in required communication capacity and processing time. When transferring join results to a site, the amount of communication required during the join process is greatly reduced, and this has a significant industrial effect of improving system economics and processing efficiency.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of an embodiment of the present invention, and FIG. 2 is an explanatory diagram of an operation example. In the figure, 1 is a processing unit, 2 is an IL communication processing unit, 3 is a hash processing unit, 4 is a classification number notification unit, 5 is an array comparison processing unit, 6 is a join processing unit, 10 is a database, 11-θ~ 11-p is a hash bucket, 12 is a command processing unit

Claims (1)

[Claims] Consisting of a plurality of sites connected to each other by communication paths,
In natural join processing of relations held in two different sites in an information processing system having a relational database (10) distributed among the sites, each site uses the tuples of the relation in its own site as join field values. means (3) for classifying into hash buckets (11-0 to 11-p) determined by a predetermined hash function; means (4) for notifying the other site of the number of tuples classified into each hash bucket; Regarding the hash bucket, compare the number of tuples notified from the other site and the number of tuples classified from the relation of your own site, and select the site with the smaller number of tuples, or one of the predetermined sites if the number of tuples is equal. means (5) for transferring the tuples classified into the hash bucket from the site to the other party's site; and means (5) for performing a join process using the transferred tuples and the tuples of the own site classified in the corresponding bucket. 6) A distributed database join processing method characterized by having the following.