Data driven parallel sorting system and method

A data driven parallel sorting method includes distributing input data records to n partitions one by one in a circular manner. Each partition corresponds to a parallel sorting process with an allocated memory chunk sized to store m data records. The method also includes sorting, in parallel, current data records in respective memory chunks in respective partitions. The method also includes in response to distribution of data records of └m/n┘ rounds, circularly controlling one of the n partitions, and writing data records that have been sorted in the memory chunk of the partition into a mass storage as an ordered data chunk, and emptying the memory chunk. The method also includes in response to all data records being distributed, writing data chunks that have been sorted in respective memory chunks into the mass storage, and performing a merge sort on all ordered data chunks in the mass storage.

PRIORITY

This application claims priority to China Patent Application No. 201310154333.5, filed Apr. 28, 2013, and all the benefits accruing therefrom under 35 U.S.C. § 119, the contents of which in its entirety are herein incorporated by reference.

BACKGROUND

The present invention relates generally to the field of parallel computation, and more specifically, to a data driven parallel sorting system and method.

A parallel sorting algorithm is an algorithm that improves sorting efficiency using the parallel computation capability of a computer. The parallel sorting is applicable in fields such as database, extraction-transformation-load (ETL), etc. A parallel sorting algorithm typically adopts a divide and conquer approach. That is, a parallel sorting algorithm divides a sequence to be sorted into a certain number of sub-sequences, orders each sub-sequence, and then merges ordered sub-sequences to produce an entirely ordered sequence.

When parallel sorting is used, data is often distributed to multiple partitions. Each partition corresponds to a sorting process which is, for example, a procedure or a thread. For each partition, the sorting process sorts the data that was distributed to the partition. The sorting process of each respective partition is performed in parallel. Then merge sorting is applied to ordered data across all partitions, to complete the sorting of all data. The merge sorting may utilize various contemporaneous merge sorting algorithms, as long as the sort algorithm merges a plurality of ordered sequences into one ordered sequence.

Parallel sorting is often applied in a data warehouse. For example, it may sort input stream data from a plurality of databases residing in a data warehouse. The input stream data is composed of data records, which may be sorted according to a particular field. In such an application, the volume of data can be very large, and it may not be possible to accommodate all the data records in memory at the same time during sorting.

SUMMARY

One aspect of various embodiments disclosed herein provides a data driven parallel sorting method. The method includes distributing input data records to n partitions one by one in a circular manner. Each partition corresponds to one of a plurality of parallel sorting processes and has an allocated memory chunk. The memory chunk is sized to store m data records. The method also includes sorting, in parallel, current data records in respective memory chunks in respective partitions. The method also includes in response to data records of └m/n┘ rounds being distributed, circularly controlling one of said n partitions, and writing data records that have been sorted in the memory chunk of the partition into a mass storage as an ordered data chunk and emptying the memory chunk. The method also includes in response to all data records being distributed, writing data chunks that have been sorted in respective memory chunks into the mass storage, and performing a merge sort on all ordered data chunks in the mass storage.

Another aspect of various embodiments disclosed herein provides a data driven parallel sorting system. The system includes: a data distributing device, an in-partition sorting device, a controlled data dumping device; and a merge sorting device. The data distributing device is configured to circularly distribute input data records to n partitions one by one. Each partition corresponds to one of a plurality of parallel sorting processes, and is allocated a memory chunk used to store distributed data records. The memory chunk is sized to store m data records, where n is an integer larger than 1 and m is a positive integer. The in-partition sorting device is configured to sort current data records in respective memory chunks in parallel in respective partitions. The controlled data dumping device is configured to, in response to data records of └m/n┘ rounds being distributed, circularly control one of said n partitions, write data records that have been sorted in the memory chunk of the partition into a mass storage as an ordered data chunk and empty the memory chunk, wherein └m/n┘ indicates that the quotient of m/n is rounded down to the closest integer. The merge sorting device is configured to, in response to distributing of all data records being completed, write data chunks that have been sorted in respective memory chunks into the mass storage, and apply the merge sorting to all ordered data chunks in the mass storage.

Yet another aspect of various embodiments disclosed herein provides a computer program product for parallel sorting. The computer program product comprises a non-transitory computer readable storage medium having program code embodied therewith. The program code is executable by a processor to perform a method. The method includes distributing input data records to n partitions one by one in a circular manner. Each partition corresponds to one of a plurality of parallel sorting processes and has an allocated memory chunk. The memory chunk is sized to store m data records. The method also includes sorting, in parallel, current data records in respective memory chunks in respective partitions. The method also includes in response to data records of └m/n┘ rounds being distributed, circularly controlling one of said n partitions, and writing data records that have been sorted in the memory chunk of the partition into a mass storage as an ordered data chunk and emptying the memory chunk. The method also includes in response to all data records being distributed, writing data chunks that have been sorted in respective memory chunks into the mass storage, and performing a merge sort on all ordered data chunks in the mass storage.

DETAILED DESCRIPTION

Referring now toFIG. 1, shown is an example computer system/server12which is applicable to implement the embodiments disclosed herein. Computer system/server12shown inFIG. 1is only illustrative and is not intended to suggest any limitation as to the scope of use or functionality of embodiments of the invention described herein.

FIG. 2is a flowchart illustrating a parallel sorting method with a large volume of data. In data distributing step210, data from a continuous input stream is evenly distributed among a plurality of partitions, each of which is allocated a memory chunk having a particular size. This memory chunk is used to store distributed data for sorting. The distribution of data is performed continuously. Data is distributed as received, unless the process is blocked. The data distributing process is independent of the sorting processes that correspond to respective partitions.

At in-partition sorting step220, data in each partition's own memory chunk is sorted via the sorting process corresponding to the partition. The sorting processes in respective partitions are performed in parallel. In data dumping step230, when the memory chunk in a partition reaches full and data in the memory chunk has been sorted, the current ordered data chunk in the memory chunk is temporarily written in a mass storage (e.g., a hard disk), and the memory chunk is emptied. That is, within a particular partition, the same memory chunk (empty at this time) is always used to process subsequent input data, and when sorting is complete, the ordered data chunk is written in the hard disk. For each partition, sorting and dumping are performed in a circular manner, until all data is sorted into ordered data chunks and is written in the hard disk.

In merge sorting step240, in response to completing the distribution of all data records, ordered data chunks in respective memory chunks are written in the hard disk, and the merge sorting is applied to all ordered data chunks in the hard disk. Through use of a simple merge sorting algorithm, merge sorting is performed on all such ordered data chunks (on the hard disk) of all partitions. In this manner, ordered data chunks are merged, and data therein is kept ordered. Thus, a final ordered sequence is obtained. This is the parallel sorting method widely used for a large volume of data, with respective partitions performing steps220and230in parallel. However, this technique leads to CPU utilization fluctuating wildly and lower throughput, since sorting processes in respective partitions compete for CPU resources almost at the same time.

FIG. 3is a schematic diagram illustrating CPU utilization when such a contemporaneous parallel sorting method is used. It can be seen fromFIG. 3that, the fluctuation of the utilization of CPU is large, and the utilization of CPU is close to, or even reaches 100% at peaks, which leads to reduced processing efficiency. However, the utilization of CPU is less than 20% at valleys, which leads to waste of processing power.

The root cause of this phenomenon is that a data distributer distributes data to respective partitions evenly using a round robin method. In a round of distributing, one data record is distributed to each partition. Each partition receives the input data distributed to it. Since a round of distributing may be completed in a very short time (almost at the same time), sorting processes in respective partitions process newly input data records almost simultaneously, and respective partitions also need to write an ordered data chunk in the hard disk almost simultaneously. That is, when respective partitions sort all data records in memory chunks based on input of data records newly distributed to them, respective partitions will compete for CPU resources at the same time. This competition leads to occurrences of peaks inFIG. 3.

Additionally, for the above reason, when sorting within respective partitions is completed, respective partitions will also compete for input/output (IO) resources in order to write ordered data chunks in the hard disk. This competition leads to waiting and delay, reducing efficiency of usage of system resources.

Usually, when the size of a memory chunk is small, it is less obvious to reduce efficiency of how the system uses parallel sorting. Reduction of the size of a memory chunk may mitigate the above problem, but this approach has other drawbacks. When the volume of data is very large, small memory chunks are not helpful, because this will cause excessive data chunks to be generated on the hard disk so that merging all these data chunks by the merge sorting process becomes very slow. This in turn causes the whole sorting process to be very slow. Thus, reduction of the size of the memory chunk may not solve the above problem. Various embodiments of data driven parallel sorting systems and methods disclosed herein optimize utilization of system resources, for example, CPU resources and I/O resources. According to one aspect, embodiments disclosed herein control partitions so that the respective partitions write data chunks that have been sorted, in their own memory chunks, into a mass storage at calculated times, even the memory chunks are not full. This creates a time difference between writing data memory chunks of different partitions into the hard disk and between of intense CPU computation. This time difference, which can be large, avoids respective partitions' intensive competition for various system resources. Therefore, system resource utilization can be optimized to improve the performance of parallel sorting.

In the parallel sorting method of the contemporaneous method ofFIG. 3, as soon as a data record is distributed to a partition, the partition re-sorts the data record and other data records (if any) that have been sorted in the memory chunk of the partition. Once the memory chunk of a partition becomes full, data chunk in the memory chunk is written in the hard disk. Thus, the parallel sorting method ofFIG. 3is a data driven method.

Recognized herein are two factors for reducing of system resource utilization. One is the occurrence of peaks, representing the respective partitions' use of CPU resources, occurring at almost the same time. Such a peak appears at the time when the volume of data in the memory chunk exceeds a certain threshold to the memory chunk becomes full. This is the case because the more data in the memory chunk, the more number of comparisons necessary for the sorting process, thus increasing the use of CPU resources. The second factor is that distributing data in round robin method leads memory chunks in respective partitions to become full at almost the same time. The method operates to write data chunks in memory chunks into the hard disk almost at the same time, which causes intensive competition for I/O resources. Based on these observations, the present disclosure recognizes that it is introducing a time difference between timings of writing data chunks in memory chunks of different partitions into the hard disk solves the technical problems discussed above.

Referring now toFIG. 4, shown is a flowchart illustrating a data driven parallel sorting method according to one embodiment disclosed herein. This method may, for example, be applied to data acquisition in a data warehouse. In such an application, the input data record is streaming data, i.e., a stream of data records. The process in the flowchart inFIG. 4includes the following steps: a data distributing step410, an in-partition sorting step420, a controlled data dumping step430, and a merge sorting step440. Each step in the data driven parallel sorting method of the present invention inFIG. 4will now be described in further detail.

In the data distributing step410, a round robin method is used to distribute input data records to n partitions one by one, in a circular manner. Here, n is an integer larger than 1. Each partition corresponds to one of a plurality of parallel sorting processes, and each partition is allocated a memory chunk used to store distributed data records. The memory chunk is able to store m data records, where m is a positive integer. In some embodiments applied to data acquisition, m may reach an order of magnitude of millions.

Here, the round robin method means circularly distributing incoming data records to n partitions one by one, in turn. For example, the 1st data record to the nth data records are distributed, in order of arrival, to the 1st to the nth partitions respectively. Subsequently, the (n+1)th to the 2 nth data records (in order of arrival) are circularly distributed to the 1st to the nth partitions respectively, and so on.

The sorting process may be implemented, for example, as a procedure or a thread. These sorting processes, the number of which is the same as the number (i.e., n) of partitions, can be performed in parallel. In one embodiment, at least two of sorting processes corresponding to respective partitions compete for the same processor resources. Such a parallel sorting method can reduce competition for CPU resources. In another embodiment, sorting processes corresponding to respective partitions are distributed to different processors, or processor cores, so that there is no competition for CPU. However, in this case, the parallel sorting method disclosed herein can still effectively reduce competition for I/O resources, as described later.

The distribution of data is performed continuously. Data is distributed when it arrives, unless the process is blocked. The data distributing is independent of the sorting processes that correspond to respective partitions.

FIG. 5is a schematic diagram illustrating the principle of the data driven parallel sorting method, according to one embodiment disclosed herein.FIG. 5only gives an example embodiment of the data driven parallel sorting method, and this example is provide for ease of understanding the principle of the present invention. This example should not be construed to limit the scope of the embodiments described herein.

InFIG. 5, n partitions are provided, and each partition is allocated with a memory chunk of a particular size. Each partition also has a respective sorting processor, implemented on a process or a thread. InFIG. 5, only the 1st, 2nd, i-th, and n-th partitions are shown, with the remaining partitions are represented by transverse broken lines between partitions. Of course, the techniques described herein are applicable to cases with other numbers of partitions, such as 2 or 3 partitions.

The distributer inFIG. 5is a separate process or thread that is dedicated to distributing incoming data to the n partitions. The distributer may transmit a signal to the sorting processors and/or the dumping initiator shown inFIG. 5. According to the operation in step410(FIG. 4), the distributer inFIG. 5distributes incoming data records to respective partitions one by one in the round robin method, and stores in corresponding memory chunks.

In the in-partition sorting step420(FIG. 4), current data records in respective memory chunks are sorted in parallel, in respective partitions. The sorting may employ various known sorting algorithms, e.g., bubble sorting, quick sorting, binary sorting, etc. As shown inFIG. 5, sorting processors1-n sort input data records in memory chunks in respective partitions. InFIG. 5, only sorting processors1,2, i, and n are exemplified, and other sorting processors are omitted.

As noted above, since data distributing may be completed in a very short time, respective partitions need much longer time to perform in-partition sorting, as compared with data distributing. Since in-partition sorting of respective partitions is performed almost at the same time, the problem of excessive competition for system resources arises. The techniques disclosed herein improve on the data dumping step of contemporaneous methods, as follows.

In the controlled data dumping step430, in response to data records of └m/n┘ rounds being distributed, one of the n partitions is circularly controlled. That is, ordered data records in the memory chunk of the partition are written into a mass storage as an ordered data chunk, and the memory chunk is emptied. The term └m/n┘ indicates that the quotient of m/n is rounded down to the closest integer. Here, data dumping means writing data chunks (that have been sorted) in the memory chunk into the mass storage and emptying the memory chunk. The mass storage may be implemented, for example, as a magnetic hard disk or a solid state hard disk. In a round of distributing, one data record is distributed to each partition. Since one of the n partitions is controlled to perform data dumping whenever data records of └m/n┘ rounds are distributed, as for the n partitions, sizes of the ordered data chunks that are written into the mass storage for the first time are not equal. Thus, there is a time difference as to when respective partitions compete for system resources.

For example, as can be seen inFIG. 5, data chunks1,2, . . . , j, . . . are shown in each partition. These data chunks are ordered data chunks dumped into (for example) a hard disk from the memory chunk, after in-partition sorting. Because of control mechanism described herein, sizes of the first dumped data chunks in respective partitions are not equal, but data chunks starting from the second one in respective partitions are equal in size (m data records). Additionally, it is noted that, the last data chunks (not shown) in respective partitions might be not equal in size either, because a scenario where all memory chunks are filled in the last loop usually does not occur. It also holds true for the contemporaneous parallel sorting process inFIG. 2.

In one embodiment, suppose that i is the number of a partition, 1≤i≤n. As for the 1st to the (n−1)th partitions, sizes of the ordered data chunks that are written into the mass storage for the first time are less than m data records, for example, as shown by data chunks1in the 1st, 2nd, i-th partitions inFIG. 5. (AlthoughFIG. 5only shows the details of four partitions (1,2, i, n), sizes of data chunks1in the 1st to the (n−1)th partitions are all less than m). Additionally, as for the n-th partition, the size of the ordered data chunk that is written into the mass storage for the first time is less than or equal to m data records. That is, when m/n is divisible, the size of the data chunk1in the n-th partition is m data records; and when m/n is not divisible, the size of the data chunk1in the nth partition is less than m data records.

In one embodiment, suppose that i is the number of a partition, 1≤i≤n, and in response to data records of └m/n┘ rounds being distributed, the circular control of one of the n partitions includes: in response to data records of └m/n┘*kth rounds being distributed, controlling the ith (i=(k mod n)) partition to write ordered data records in the memory chunk of the partition into the mass storage as an ordered data chunk, wherein k is a positive integer, and (k mod n) indicates the remainder after k modulo n. Here, k may be regarded as a counter, which is initialized to zero (it is noted that the initialized value is meaningless). Whenever data records of └m/n┘ rounds are distributed, the value of the counter is increased by 1. The remainder obtained after the value of the counter modulo n is the number of the partition to be controlled.

In one embodiment, the above counter may be implemented by the dumping initiator shown inFIG. 5. In this case, whenever data records of └m/n┘ rounds are distributed, the distributer transmits a signal to the dumping initiator inFIG. 5. In response to the signal, the dumping initiator causes the counter to be increased by 1, and initiates data dumping in the corresponding partition i according to i=(k mod n) calculated in accordance with the value of the counter (see transverse double arrows between the dumping initiator and respective partitions inFIG. 5). Specifically, in one embodiment, the dumping initiator may start a write process or thread with respect to the partition, write a snapshot of data chunk that has been sorted in the memory chunk of the partition (into a hard disk, for example), and empty the memory chunk. In another embodiment, the dumping initiator does not necessarily start a special write process or thread, but may notify a corresponding sorting processor, so that the sorting processor, in response to the notification, itself invokes a write instruction to finish data dumping.

In one embodiment, the above counter may be implemented in the distributer shown inFIG. 5. In this case, whenever data records of └m/n┘ rounds are distributed, the distributer causes the counter to be increased by 1, and transmits a signal to the corresponding sorting processor i according to i=(k mod n) calculated in accordance with the value of the counter. In response to receiving the signal directly from the distributer, the corresponding sorting processor starts a special write process or thread or invokes a write instruction to finish data dumping.

In the case of introducing the above value k, when k is less than or equal to n, sizes of the ordered data chunks that are written into the mass storage are └m/n┘*k data records. On the other hand, when k is larger than n and input data records are enough (i.e., neither the first data chunk nor the last data chunk), sizes of the ordered data chunks that are written into the mass storage are m data records.

As described above, various methods may be employed to implement the inventive concept of embodiments disclosed herein, and such embodiments are not limited to the particular structure shown inFIG. 5.

In the following, a simple example is given to illustrate the parallel sorting of the present invention in detail. Suppose that n=4 (i.e., there are 4 partitions) and m=16 (i.e., the memory chunk in each partition can store 16 data records). It is noted that this is only a simple example given for ease of understanding. In reality, the number of partitions may be more than 64, and a memory chunk may be large enough to store millions of data records. In the case of n=4 and m=16, └m/n┘=4. That is, whenever data records of 4 rounds (16 data records) are distributed, one of the 4 partitions is controlled in a circular manner, data records that have been sorted in the memory chunk of the partition are written into the mass storage as an ordered data chunk, and the memory chunk is emptied.

Referring to the example inFIG. 5, when k=1 (i.e., data records of 4 rounds are distributed), data dumping is performed on the partition1((k mod 4)=1). At this time, there are only 4 data records that have been sorted in the memory chunk of the partition1(i.e., ¼ full). In this way, the data chunk1of a size of m*¼ in the partition1is written into storage (a hard disk, for example) and the memory chunk of the partition1is emptied.

When k=2 (i.e., data records of 8 rounds are distributed), data dumping is performed on the partition2((k mod 4)=2). At this time, there are only 8 data records that have been sorted in the memory chunk of the partition2(i.e., half full). In this way, the data chunk1of a size of m*½ in the partition2is written into storage (the hard disk, for example) and the memory chunk of the partition2is emptied.

When k=3 (i.e., data records of 12 rounds are distributed), data dumping is performed on the partition3((k mod 4)=3). At this time, there are only 12 data records that have been sorted in the memory chunk of the partition3(i.e., ¾ full). In this way, the data chunk1of a size of m*¾ in the partition3is written into storage (the hard disk, for example) and the memory chunk of the partition3is emptied.

When k=4 (i.e., data records of 16 rounds are distributed), data dumping is performed on the partition4((k mod 4)=4). At this time, there are 16 data records that have been sorted in the memory chunk of the partition4(i.e., full). In this way, the data chunk1of a size of m in the partition4is written into the storage (the hard disk, for example) and the memory chunk of the partition4is emptied.

When k=5 (i.e., data records of 20 rounds are distributed), data dumping is again performed on the partition1((k mod 4)=1). At this time, there are 16 data records that have been sorted in the memory chunk of the partition1(at this time, 16 rounds have passed after the memory chunk of the partition1is emptied after data distributing of the 4th round). In this way, the data chunk1of a size of m in the partition1is written into the storage (the hard disk, for example) and the memory chunk of the partition1is emptied.

The controlled data dumping step430is performed as described above, and the subsequent steps are performed in a similar way. It is noted that longitudinal arrows inFIG. 5represent a sequential relationship between data chunks, the solid line arrows represent being adjacent, and broken line arrows represent there are other omitted data chunks between data chunks.

Referring back toFIG. 4, the merge sorting step440is similar to the merge sorting step240inFIG. 2. In response to distribution of all data records being completed, data records that have been sorted in respective memory chunks are written into the mass storage, and the merge sorting is applied to all ordered data chunks in the mass storage. Using a merge sorting algorithm, merge sorting is performed on all such ordered data chunks (on the hard disk) of all partitions, thus merging these ordered data chunks and keeping data therein ordered. A final ordered sequence is therefore obtained. (See the lower part inFIG. 5.)

In one embodiment, in response to receiving a signal indicating completion of data distribution from the distributer, the dumping initiator starts a write process or thread to write data chunks (that have been sorted) in respective memory chunks into storage (a hard disk, for example). In another embodiment, the distributer directly notifies respective sorting processors of completion of data distributing, so that respective sorting processors respectively start a write process or thread or invoke a write instruction to write data chunks into storage (a hard disk, for example).

In another embodiment, upon receiving a signal indicating completion of data distributing, dumping is not performed on current data chunks (i.e., the last data chunks) in memory chunks of respective partitions. Instead, merge sorting of all ordered data chunks (including data chunks in the hard disk and data chunks in memory chunks) is directly started. By doing so, it is possible to avoid the redundant I/O operation, i.e., a requirement to read back the last data chunks after they are written to the hard disk.

By controlling respective partitions to cause them to write data chunks that have been sorted in their own memory chunks into a mass storage at calculated times (even the memory chunks are not full), embodiments described herein produce a difference between the time that data in memory chunks of different partitions are written to the hard disk, and times when CPU computation intensity is large. This difference avoids intense competition for various system resources between respective partitions. Therefore, utilization of system resources can be optimized to improve the performance of parallel sorting.

FIG. 6is a block diagram illustrating a data driven parallel sorting system according to an embodiment disclosed herein. The parallel sorting system600inFIG. 6includes a data distributing means610, an in-partition sorting means620, a controlled data dumping means630, and a merge sorting means640. The data distributing means610is configured to circularly distribute input data records to n partitions one by one. Each partition corresponds to one of a plurality of parallel sorting processes, and each partition is allocated a memory chunk used to store distributed data records. The memory chunk is able to store m data records, where n is an integer larger than 1 and m is a positive integer.

The in-partition sorting means620is configured to sort current data records in respective memory chunks in parallel in respective partitions. The controlled data dumping means630is configured to, in response to data records of └m/n┘ rounds being distributed, circularly control one of said n partitions, write data records that have been sorted in the memory chunk of the partition into a mass storage as an ordered data chunk and empty the memory chunk. The term └m/n┘ represents the quotient of m/n rounded down to the closest integer. The merge sorting means640is configured to, in response to distributing of all data records being completed, write data chunks that have been sorted in respective memory chunks into the mass storage, and to apply the merge sorting to all ordered data chunks in the mass storage.

FIG. 7is a diagram illustrating CPU utilization during a contemporaneous parallel sorting method.FIG. 8is a diagram illustrating a reduced CPU competition during a parallel sorting method according to an embodiment disclosed herein. The upper part inFIG. 7shows CPU utilization by a partition sorting process. In the contemporaneous method, when there are two partitions, CPU utilizations by sorting processes in the two partitions are similar, as shown in the upper part inFIG. 7. Thus, CPU utilizations by sorting processes in the two partitions lead to the overlap shown in the upper part inFIG. 8, i.e., peaks overlap with peaks, and valleys overlap with valleys. In contrast, in various parallel sorting methods disclosed herein, when there are two partitions, a difference is generated between time periods in which CPU utilization by the two partitions are high. For example, CPU utilization by the partition1sorting process is shown in the upper part inFIG. 7, while CPU utilization the partition2sorting process is shown in the lower part inFIG. 7.

FIG. 8shows overlapping CPU utilizations by sorting processes in the two partitions during parallel sorting according to the inventive techniques disclosed herein. As seen in the drawing, in comparison with the upper part inFIG. 8, there is no case where utilization is close to 100%, thereby achieving the effect of flattening. Therefore, the response speed of CPU is improved and CPU utilization is optimized.

Competition for I/O resources is handled in a manner similar to that discussed forFIGS. 7 and 8. When the writing processes of ordered data chunks from respective partitions compete for the same I/O resource, intensive competition for the I/O resource is also avoided because of the time difference produced by the techniques disclosed herein, thereby optimizing utilization of the I/O resources. In addition, even in the case of multiple processors (e.g., 4 processors), if the number of partitions exceeds the number of processors, a case where sorting processes in multiple partitions compete for the same processor resource still exists. In this case, the techniques disclosed herein may still be applicable to avoid intensive competition for the processor. In addition, even if the number of partitions is less than the number of processors, CPU resources are nonetheless occupied (for example, other programs are running in the system), so it is still possible for the system to schedule sorting processes in multiple partitions to compete for the same processor resource. In this case, the techniques disclosed herein may still be applicable to reduce intensive competition for the processor.