Grepping over a huge file performance

Question

I have FILE_A which has over 300K lines and FILE_B which has over 30M lines. I created a bash script that greps each line in FILE_A over in FILE_B and writes the result of the grep to a new file.

This whole process is taking over 5+ hours.

I'm looking for suggestions on whether you see any way of improving the performance of my script.

I'm using grep -F -m 1 as the grep command. FILE_A looks like this:

123456789 
123455321

and FILE_B is like this:

123456789,123456789,730025400149993,
123455321,123455321,730025400126097,

So with bash I have a while loop that picks the next line in FILE_A and greps it over in FILE_B. When the pattern is found in FILE_B i write it to result.txt.

while read -r line; do
   grep -F -m1 $line 30MFile
done < 300KFile

Thanks a lot in advance for your help.

Answer 1

The key to performance is reading the huge file only once.

You can pass multiple patterns to grep by putting them on separate lines. This is usually done by telling grep to read patterns from a file:

grep -F -f 300KFile 30MFile

This outputs the matches in the order of the large file, and prints lines that match multiple patterns only once. Furthermore, this looks for patterns anywhere in the line; for example, if the pattern file contains 1234, then lines such as 123456,345678,2348962342 and 478912,1211138,1234 will match.

You can restrict to exact column matches by preprocessing the pattern. For example, if the patterns do not contain any special character ()?*+\|[]{}:

<300KFile sed -e 's/^/(^|,)/' -e 's/$/($|,)/' |
grep -E -f - 30MFile

If retaining only the first match for each pattern is important, make a first pass to extract only the relevant lines as above, then do a second pass in awk or perl that tracks patterns that have already been seen.

<300KFile sed -e 's/^/(^|,)/' -e 's/$/($|,)/' |
grep -E -f - 30MFile |
perl -l -F, -ape '
    BEGIN {
        open P, "300KFile" or die;
        %patterns = map {chomp; $_=>1} <P>;
        close P;
    }
    foreach $c (@F) {
        if ($patterns{$c}) {
            print;
            delete $patterns{$c};
        }
    }
'

Answer 2

Can you run the following?

grep -Ff FILE_A FILE_B > FILE_C

Now you can run your script on files A and C only.

Update: Wait... Does it preserve the order?

Another update: Some more processing is needed to keep the order. This gives me the same results as your original script. Tested on 300K lines in FILE_A and only 300K lines in FILE_B, 125 minutes vs. 14 secs.

#! /bin/bash
grep -Ff FILE_A FILE_B > FILE_B_TMP
grep -oFf FILE_A FILE_B_TMP > FILE_A_SHUFF
grep -Ff FILE_A_SHUFF FILE_A > FILE_A_TMP

while read -r line; do
   grep -F -m1 "$line" FILE_B_TMP
done < FILE_A_TMP > result.txt

Answer 3

I believe comm can make better performance:

comm -12 300KFile <(sed 's/,.*//' 30MFile)

ps. I'm not sure if string 123123 fromm 300KFile should match to string gdwyedg,123123,hfsjdkfh in 30M file. As in your script it matches, but in my script it doesn't.

Answer 4

I believe the grep based solutions still need to compare each record in FILE_A with each record in FILE_B. Since at least N-1 records in FILE_A will not match a specific record in FILE_B, there's a lot of redundancy in this approach. If, on the other hand, the files were sorted then it would be possible to discard a large number of the tests for each comparison. Hence, something like....

#!/bin/bash

# NB a faster solution would be to sort the smaller file in a seperate process
# you might also want to set a buffer size for large files
sort $1 > /tmp/$$.a
sort $2 > /tmp/$$.b

join -j1 -t',' /tmp/$$.a /tmp/$$.b

rm -f /tmp/$$.?

(not tested)

But note that the order of entries will be changed, this pre-supposes that you want to match on a specific column of data in FILE_B and also the sorting introduces an overhead - but the result should be faster for these file sizes.