JPH01201722A - Sort processor - Google Patents

Abstract

PURPOSE:To attain a sort in ascending sequence or descending sequence to a column designated to the object of comparison by dividing a record, comparing them and invalidating the comparison result or inverting and accumulating it by designated sort conditions. CONSTITUTION:Signals I and II are timing signals to synchronously operate the title sort processor. Signals A and B shows a data input at the time of dividing the record and comparing and transferring them. An END signal is a signal to show the partitions of the record to be compared successively and the comparison result is accumulated until the END signal becomes a logical value 1. A CMP signal and an A/D signal is signals to designate the sort conditions. When the CMP signal is the logical value 1, the colum inputted to a comparator shows that it is the comparative object at the time of sorting, shows the sort in ascending sequence when the A/D is the logical value 1 and shows the sort in descending sequence when it is 0.

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention relates to the configuration of a sorting processing device, and more specifically,
Divide the records to be sorted into multiple pieces of data and
The present invention relates to a sort processing device characterized in that it is configured such that it is possible to specify whether or not each divided data is to be sorted, and to specify an ascending or descending sort order.

[Conventional technology]

Generally, when the number of records (individual data handled in database processing is called a record) is extremely large, or when multiple databases are to be processed, processing on a general-purpose computer requires an enormous amount of time. For this reason, a sort processing apparatus that speeds up database processing by directly executing part or all of the database processing on hardware is disclosed in, for example, Japanese Patent Laid-Open No. 60-81640.

FIG. 3 shows the configuration of the sort processing device disclosed in the above-mentioned Japanese Patent Application Laid-Open No. 60-81640. In FIG. 0, 1 is a comparison unit, 2 is an inter-unit data transfer path, and 3 is a 1 is a memory, 4 is a second memory, 5 is a comparator, 6 is a first flag register, and 7 is a second flag register.

Records to be sorted are divided into units of data that can be transferred or compared at once by the inter-unit data transfer path 2 and the comparator 5, and are input to a sort processing device consisting of a one-dimensional array of comparison units 1. Each comparison unit) 1 compares input data with corresponding data of a record stored in the first or second memory within its own unit, and accumulates the result in a first flag register.

Whether to compare the record stored in the first or second memory in the own unit with the input record is determined by the second memory.
Of the two records stored in the first and second memories, one is to be compared with the input record, and the other is to be transferred to the adjacent comparison unit. The record to be transferred is output as divided data to the adjacent comparison unit,
It is compared in the adjacent comparison unit as input data in the comparison unit.

As shown above, one conventional sorting processing device is
It is configured so that each of the comparison units 1 connected in a plurality of one-dimensional arrays inputs records to be sorted as a plurality of divided data in a pipeline manner and performs parallel comparison to perform high-speed sorting. be. Also, the upper limit of the record length that can be sorted is the first record length in the comparison unit.
The comparator and the inter-unit data transfer path can be configured depending only on the second memory capacity and regardless of the length of records to be sorted.

[Problem that the invention seeks to solve]

In the above-mentioned conventional technology, since the record input to the sort processing device is divided into multiple pieces of data and the comparison and transfer processing is performed, it is possible to configure the comparator and the data transfer path regardless of the record length to be sorted. can. However, with this conventional method, the purpose was to compare the entire record and sort it in ascending or descending order, so although it is possible to sort long records, it is not possible to compare only a specific column of a record consisting of multiple columns. There was a problem that it was not possible to sort by specifying a target or by complex conditions such as sorting a specific column in ascending order and other columns in descending order.

For this reason, it is necessary to perform preprocessing to extract only the part to be compared from a record, or to sort some columns that make up the record in ascending order, and then to sort other columns in descending order. This was a factor leading to an increase in sorting processing time and complexity of the device.

SUMMARY OF THE INVENTION The present invention aims to solve the above-mentioned problems of the prior art and provides a sorting device that can sort based on complicated sorting conditions.

[Means for solving problems]

The above object of the present invention is to provide a storage means for inputting and storing two records, and a comparison means for dividing the stored two records into a plurality of pieces of data, reading them from the record storage means, and comparing them. Then, inverting or non-inverting the output of the comparing means based on the sorting condition specified in ascending or descending order, limited to the data specified as the subject of comparison among the divided data. and a comparison result accumulating means for accumulating the comparison results of the records and determining the magnitude relationship of the seven records.

Outputting either of the two stored records to an adjacent comparison unit by the output of the comparison result accumulation means;
At the same time, this is achieved by a sort processing device characterized in that it sorts input records based on specified sort conditions by inputting records from the other adjacent comparison unit.

[Effect]

In the sort processing device of the present invention, when records are divided and compared and the obtained comparison results are accumulated for the number of codes, the comparison results are invalidated according to the specified sorting conditions, or the comparison results are reversed and accumulated. As a result, by adding a small circuit to the comparison result accumulation circuit, it is possible to specify a specific column of a record consisting of multiple columns as a comparison target. Furthermore, it is possible to easily realize a sort processing device that can specify sorting in ascending order or descending order for a column designated as a comparison target.

〔Example〕

EMBODIMENT OF THE INVENTION Below, one embodiment of the present invention will be described in detail based on the drawings.

FIG. 1 is a block diagram showing an embodiment of the sorting device of the present invention. Regarding the comparison result accumulation circuit provided after the comparator 5 in the conventional sorting device shown in FIG.
Its configuration is shown in detail. Here, we will explain in detail the configuration and operation of the comparison result accumulation circuit that enables the specification of complex sorting conditions according to the present invention, and will provide a brief explanation of the operating principle of the sorting processing device explained in the prior art section. stay.

In the figure, 10 is a flip-flop circuit, 11 is an AND circuit, 12 is an OR circuit, 13 is an inverter circuit, 14
are logical symbols indicating exclusive OR circuits, and both can be easily realized using known circuits such as TTL.

Further, 5 in FIG. 5 has the same circuit configuration as the comparator shown in FIG. 3, and implementation is easy.

FIG. 2 is a timing diagram explaining the operation of the comparison result accumulation circuit shown in FIG. 1. In the example of FIG.
It shows the operation of comparing integers 1234.1125 digits one by one and accumulating the comparison results for four digits. therefore,
In the example shown in FIG. 2, it is assumed that a record consisting of a four-digit integer is composed of four columns, with each digit forming a column.

The signal names in the figure correspond to those in FIG.

In the following, the roles of each signal will be shown. Signals ① and ② are timing signals for operating the sorting processing device in synchronization. Signals A and B indicate data input when records are divided and compared and transferred. The END signal is a signal that indicates a break between records to be compared continuously, and the E
The comparison results are accumulated until the ND signal becomes a logical value of 1. C
The MP and A/D signals are signals that specify sorting conditions. When the CMP signal has a logical value 1, it indicates that the column input to the comparator (input data of signals A and B) is a comparison target during sorting.

When A/D has a logical value 1, it indicates ascending sorting, and when it has a logical value 0, it indicates descending sorting. In the example in Figure 2.

To compare 4-digit integers.

i) Thousands place is sorted in descending order.

■) Hundreds place is not subject to comparison (That is, the CMP signal has a logic value of O).

ii) The tens place is sorted in ascending order.

1v) The minus digit indicates a case where descending sorting is specified, and the comparison results are accumulated so that the higher-order digits have higher priority.

EQ and GT, which are the outputs of the comparator, are the comparison results of A and B that are input in synchronization with timing I. EQ indicates that the two match, and GT indicates that A is larger than B. is expressed. In reality, the data input at timing ■ is output with a delay of the time required for comparison, but in Figure 1, it is simply shown that the data is output at timing I. These signals are externally applied, and these signals define the operation of the comparison result accumulation circuit.

FE and FG are flip-flops corresponding to the first flag register 6 in the conventional sort processing device shown in FIG. 3, and are flags for accumulating the comparison results for the Lou codes. In the initial state, the flip-flop F
Set E to logic 1 and flip-flop FC to logic 0. When the flip-flop FE has a logical value of 1, it indicates that the two records match as a result of comparison performed from the beginning (higher digits) of the records. When the flip-flop FG has a logic value of 0, it indicates that the data group input from the A side of the comparator is larger than the data group input from the B side from the beginning of the record to the current time, and when the FG has a logic value of 1. Time shows the opposite. However, the value of FG is valid when FE is a logical value of 0, and in the initial state, FB-1
And since FC-0, 1 indicates that both are equal at the beginning position of the record (before comparing the records).

The values of FE and FC in FIG. 2 will be explained over time. In this example, the thousands digits of the two records are both equal to 1, and even after the comparison, they are FB-1 and FC-0. The hundreds digits of the two records are different, 2 and 1, but
FE because the hundreds place is not subject to comparison (CMP-0).

The value of FG is saved. In the tens place, the A bias input is 3.
Since B input is 2 and is the target of comparison (CMP=1), 9
Normally, the records input from the A side are large (FG=
However, in this example, the tens digit is specified to be in ascending order, so FC=1. In the - digit, the A bias input is small for 4 and 5, but this is because the magnitude relationship between records has already been determined by comparing the tens digit.

- comparison results are not accumulated. To summarize the above, 2
The following table appears.

As shown above, the comparison results are accumulated by the flip-flop FG, and the flip-flop FB assists in indicating whether or not the previous results match. The value of FG for which the accumulation of the roux code is completed is at the end of the record, that is, at END-1.

It is transferred to the second flip-flop FS. FS output F
It defines which of the two records stored in the comparison unit the LG will transfer to the adjacent comparison unit. This mechanism is the same as the prior art shown in FIG. 3, and its explanation will be omitted.

In this embodiment, the comparison result accumulation circuit having the configuration shown in FIG. 1 has been explained as an example. It is sufficient to realize a function that allows at least one specification of whether the data is sorted in ascending order or in descending order, and these functions can be realized with a separate circuit configuration. It is also easy.

〔Effect of the invention〕

As described above (1) According to the present invention, there is a storage means for inputting and storing two records, and a storage means for dividing the stored two records into a plurality of pieces of data and reading them from the record storage means. a comparison means for comparing, and limited to data specified as the subject of comparison among the divided data,
Based on sort conditions specified in ascending or descending order,
a one-dimensional array of comparison units comprising at least a comparison result accumulation means for applying an inversion or non-inversion operation to the output of the comparison means and accumulating the comparison results for the Lou code to determine the magnitude relationship of the records; .

Outputting either of the two stored records to an adjacent comparison unit by the output of the comparison result accumulation means;
At the same time, by inputting records from the other adjacent comparison unit, it is possible to realize a sorting processing apparatus characterized in that the input records are sorted based on specified sorting conditions.

As a result, the sorting device of the present invention can perform complex sorting at once, specifying different sorting conditions for each column, for records consisting of multiple columns, and can shorten the sorting processing time. In addition, the preprocessing circuit that extracts keys from records can be easily configured.

It is also effective in reducing the size of the device.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing an embodiment of a sorting device according to the present invention. FIG. 2 is a timing diagram illustrating the operation of the comparison result accumulation circuit shown in FIG. 1. FIG. 3 is a configuration diagram showing an example of a conventional sort processing device. l...Comparison unit. 2... Inter-unit data transfer path. 3...First memory. 4...Second memory. 5... Comparator. 6...First flag register. 7...Second flag register. 10...Flip-flop circuit. 11...AND circuit. 12...OR circuit. 13... Inverter circuit. 14...A logical symbol indicating an exclusive OR circuit. Patent applicant Nippon Telegraph and Telephone Corporation

Claims (1)

[Claims] Storage means for inputting and storing two records, and comparison means for dividing the stored two records into a plurality of pieces of data and reading them from the record storage means and comparing them. , applying an inversion or non-inversion operation to the output of the comparison means based on a sorting condition specified in ascending order or descending order, limited to the data specified as the subject of comparison among the divided data; a one-dimensional array of comparison units comprising at least a comparison result accumulation means for accumulating comparison results for one record and determining the magnitude relationship of the records; Outputs one of the records stored in to the adjacent comparison unit,
A sorting processing device characterized in that, by simultaneously inputting records from another adjacent comparison unit, input records are sorted based on specified sorting conditions.