Verknüpfen von Textdateien mit 600M + Zeilen

IMO the best way to do this would be to use the programming/scripting language you know best and:

1. load small.txt into an in-memory hash/map/associative array keyed on the words
2. Process huge.txt line by line, adding the column looked up from the hash and writing the result into an output file
3. Buffer input and output so that it happens in chunks of at least 4K

To build on Michael Borgwardt's answer: as long as both files are sorted, you can put them together by basically performing one step of a mergesort. It'll be a little different than standard mergesort because you only want to keep one of the files. This will, of course, have to be implemented in your favorite programming language.

Here's a sketch of the algorithm:

line1 = read a line from file 1 line2 = read a line from file 2 start of loop: if (first word of line1 == first word of line2) { write all fields of line1 and second field of line2 to output line1 = read a line from file 1 go to start of loop } else if (first word of line1 < first word of line2) { write line1 to output line1 = read a line from file 1 go to start of loop } else (first word of line1 > first word of line2) { line2 = read a line from file 2 go to start of loop } 

Here's a Python version (since Python is just what I happen to know best, not necessarily the best language for the job):

file1 = open('file1', 'r') file2 = open('file2', 'r') w2, n2 = file2.readline().split() for line1 in file1: w11, w12, w13, w14, n15 = line1.split() if w11 == w2: print w11, w12, w13, w14, n15, n2 continue elif w11 < w2: print w11, w12, w13, w14, n15 continue else: while w11 > w2: w2, n2 = file2.readline().split() if w11 == w2: print w11, w12, w13, w14, n15, n2 elif w11 < w2: print w11, w12, w13, w14, n15 

and for completeness, after some digging here's what I came up with for Awk:

BEGIN { getline line2 <"file2"; split(line2, a); } { if (a[1] == $1) print $0,a[2]; else if (a[1] < $1) print $0; else { getline line2 <"file2"; split(line2, a); } } 

Invoke as awk -f program.awk <file1.

My answer is similar to Michael Borgwardt's, but you don't have to load all of either file into memory. If the files are both sorted, then you walk through first file one line at a time, and you do binary search on the second file to find the target line in question. That's a lot of HD access, but it's low memory consumption.

OK, this approach uses http://cr.yp.to/cdb.html as a quicker way to look up the content of 'small.txt':

• Go and install cdbmake (part of 'freecdb' package in Ubuntu, but there are a lot of implementations available.

• Use awk to pipe small.txt to cdbmake.

  % awk ' { printf "+%d,%d:%s->%s\n", \ length($1),length($2),$1,$2 } \ END { print "" }' | cdbmake small.cdb small.cdbtmp 

(This transforms a line of 'small.txt' from something like "key value" into "+ks,vs:key->value".)

• Now you go line by line over 'huge.txt' and print it out, looking up the first word in 'small.cdb':

  #!/bin/python import cdb import fileinput c = cdb.init("small.cdb") for l in fileinput.input(['huge.txt']): print l.strip(), v = c.get(l.split()[0]) print "" if v == None else v 

You would have to install python-cdb of course to make this tiny snippet work (and it works only for Python 2.5 because of the 'conditional expression'. Anyway, there are a lot of bindings for whatever language you like. You could also use cdbget(a command line tool) and invoke it over and over again but spawning a new process for millions of lines is a bit ineffective.

Anyway, keep this in mind:

• Each .cdb file can not be bigger than 4 GB. So if you have to process 'small.txt' with a size of 10 GB you obviously have to split up that into multiple files and create 'small1.cdb', 'small2.cdb', 'small3.cbd' and so on. It should be an easy task.
• You do not need to sort 'small.txt', a lookup in a cdb file is pretty fast anyway.
• I have not timed my little test case here, it is based on what you provided. :)

I know it's embarrassingly simple but it works.
Based on the assumption that my original files contain only lowercase characters, I simply replaced the problematic apostrophes and dashes with two uppercase letters, re-sorted than joined the files, finally changed back the letters back to the signs. That's it.

Thanks again for everyone contributing an answer or insightful comment.

The sorting took like 2 hours for huge.txt (14Gig), the joining less than an hour.

cat small.txt | tr "\'-" "AD" | sort -k1 > small.AD cat huge.txt | tr "\'-" "AD" | sort -k1 | cat huge.txt | join -o 1.1 1.2 1.3 1.4 2.2 - small.AD | tr "AD" "\'-" > output.txt 

Instead of MySQL, you might try PostgreSQL which likely can handle this task more gracefully. See their guide on efficiently populating a database.