Optimal k-way merge pattern

user_10550964 0
Viewed 561

I need to merge n sorted fixed record files of different sizes using k simultaneous consumers, where k<n. Because k is (possibly a lot) smaller than n, the merge will be done in a number of iterations/steps. The challenge is to pick at each step the right files to merge.

Because the files can differ wildly in size, a simple greedy approach of using all k consumers at each step can be very suboptimal.

An simple example makes this clear. Consider the case of 4 files with 1, 1, 10 and 10 records respectively and 3 consumers. We need two merge steps to merge all files. Start with 3 consumers in the first step. The merge sequence ((1,1,10),10) leads to 12 read/write operations in (inner) step 1 and 22 operations in (outer) step 2, making a total of 34 ops. The sequence (1,(1,10,10)) is even worse with 21+22=43 ops. By contrast, if we use only 2 consumers in the first step and 3 in the second step, the merge pattern ((1,1),10,10) takes only 2+22=24 ops. Here our restraint pays off handsomely.

My solution for picking the right number of consumers at each step is the following. All possible merge states can be ordered into a directed graph (which is a lattice I suppose) with the number of ops to move from one state to another attached to each edge as the cost. I can then use a shortest path algorithm to determine the optimal sequence.

The problem with this solution is that the amount of nodes explodes, even with a modest number of files (say hundreds) and even after applying some sensible constraints (like sorting the files on size and allowing only merges of the top 2..k of this list). Moreover, I cannot shake the feeling that there might be an "analytical" solution to this problem, or at least a simple heuristic that comes very close to optimality.

Any thoughts would be appreciated.

mergesort algorithm
2 Answers

May I present it another way:

The traditionnal merge sort complexity is o( n.ln(n)) but in my case with different sublist size, in the worst case if one file is big and all the other are small (that's the example you give) the complexity may be o( n.n ) : which is a bad performance complexity.

The question is "how to schedule the subsort in an optimal way"?

Precompute the graph of all executions is really too big, in the worst case it can be as big as the data you sort.

My proposition is to compute it "on the fly" and let it be not optimal but at least avoid the worse case.

  1. My first naive impression was simply sort the files by sizes and begin with the smaller ones: this way you will privilege the elimination of small files during iterations.

I have K=2: in your example 1 1 10 10 -> 2 20 -> 22 : It is still (20 + 2) + 22 CC so 42 CC*

CC: Comparison or copy: this is the ops I count for a complexity of 1.

If I have K=1 and reinject the result in my sorted file Array I get: (1 1 10 10) -> 2 10 10 -> 12 10 -> (22) : 2 CC + 12 + 22 = 46 For different value of K the complexity vary slightly

Compute the complexity of this algorithm in the mean case with probability would be very interresting, but if you can accept some N² execution for bad cases.

PS:

The fact that k<n is another problem: it will be simply resolved by adding a worker per couple of files to a queue (n/2 workers at the beginning), and making the queue read by the k Threads.

user_21733920

Firstly an alternative algorithm 

read all record keys (N reads) with a fileid
sort them
read all files and place the records in the final position according to the sorted key (N R/W)

might be a problem if your filesystem can't handle N+1 open files or if your random file access is slow for either read or write. i.e. either the random read or random write will be faster.

Advantage is only N*2 reads and N writes.

Back to your algorithm

Does it pay to merge the large files with small files at a random point in the merging? No

  • E.g. (1,1,10,10) -> ((1,10),(1,10)) [2*11 ops] -> (11,11) [22 ops] sum 44. ((1,1),10,10) is only 24.
  • Merging large and small files cause the content of the large files to be R/W an extra time.

Does it pay to merge the large files first? no

  • E.g (1,10,10,10) -> (1,10,(10,10)) 20+31 ops vs. ((1,10),10,10) 11+31 ops
  • again we get a penalty for doing the ops on the large file multiple times.

Does it ever pay to merge less than K files at the last merge? yes

  • e.g. (1,2,3,4,5,6) -> (((1,2),3,4),5,6) 3+10+21 vs ((1,2,3),(4,5,6)) 6+15+21
  • again merging the largest files more time is a bad idea

Does it pay to merge less than K files, except at the first merge? yes

  • e.g. !1 (1,2,3,4,5,6) -> (((1,2),3,4),5,6) 3+10+21=34 vs (((1,2,3),4),5,6)) 6+10+21=37
  • the size 3 file gets copied an extra time
  • e.g. #2 (((1,1),10),100,100). Here we use k=2 in the first two steps, taking 2+12+212=226 ops. The alternative ((1,1),10,100),100) that uses k=3 in the second step is 2+112+212=326 ops

New heuristic

while #files is larger than 1
  sum size of smallest files until K or next larger file is greater than the sum.
  K-merge these

ToDo make proof that the sum of additions in this case will be smaller than all other methods.

user_40132580
Related