7

I have two text files. One is a text file with name, email address and other fields. Some lines from file1:

John:myemail@gmail.com:johnson123:22hey
Erik:thatwhatsup@gmail.com:johnson133:22hey
Robert:whatsup@gmail.com:johnson123:21hey
Johnnny:bro@gmail.com:johnson123:22hey

The other contains only email addresses. Examples from file2:

1@gmail.com
rsdoge@gmail.com
mynameiscurt@hotmail.com
myemail@gmail.com

I want the output to be each full line of file1 that has an email address in file2. For example, myemail@gmail.com is in file2, so I'd like to see the following line from file1:

John:myemail@gmail.com:johnson123:22hey

Is there an easy way to search file1 and output the lines that match with the "list of email addresses" file2?

I have been searching for HOURS, but my Google searches (and StackOverflow searches) along with efforts on the command line have not been effective thus far.

Commands I have tried and think would work:

fgrep -f file2.txt file1.txt > matched.txt
grep -F -f ....
grep -F -x -f file1 file2 > common 

etc., but they all got grep memory exhausted - the files I'm matching are 4.8GB (file1) and 3.2GB (file2, containing just the email addresses). I assume the memory gets exhausted with these commands. I found a method using find to execute the commands smoother I guess, but didn't get it to work.

tldr; need to match file2 with file1 and if there's a line from file2 that matches a line in file1, output it. The files are large and I need a safe way to not use up all the memory.

Thank you, searched whole day for this and experimented, didn't want to give up (5hours+).

  • 8
    This data is a candidate for putting into a database. – Kusalananda Aug 1 '16 at 19:24
  • what do you mean? – Axel Tobieson Aug 1 '16 at 19:27
  • 4
    I mean that since the data sets are so large, it may be more efficient to let a database engine perform the query rather than using Unix command-line tools to do it. I was just now looking into a way of reading the data into SQLite or MySQL to see if I could query it efficiently, but it's getting late over here so I don't know if I have time to do something real. Others may step in with other solutions. – Kusalananda Aug 1 '16 at 19:29
  • alright man, it is in .txt format though. – Axel Tobieson Aug 1 '16 at 19:32
  • 1
    Yes. I think I got some great answers but I applied costas answer and got it to work.! :) – Axel Tobieson Aug 3 '16 at 8:14
7

It's rather difficult to operate a big files but you can do it in 3 steps:

  1. Sort file1 by second field

    sort -k2,2 -t: file1 >file1.sorted
    
  2. Sort file2

    sort file2 >file2.sorted
    
  3. Join 2 files by email field

    join -t: -2 2 file2.sorted file1.sorted -o 2.1,0,2.3,2.4 >matched.txt
    
  • You completely fail to take into account that : can occur in the local part of an email address. – Anthon Aug 2 '16 at 11:26
  • @Anthon That''s a weakness of the format used to store the data, surely – Score_Under Aug 2 '16 at 12:13
5

I'm submitting a second answer to this question (this is an interesting problem). This one is totally different from my SQLite solution, and from the quite promising-looking sort+join solutions that starts to appear:

Using your initial approach with grep -f, but literally cutting down the problem a bit. Let's split the "query file", file2 into manageable chunks using split.

The split utility is able to split a file into a number of smaller files based on a line count.

A 3.2 Gb file with an average line length of 20 character has somewhere around 172,000,000 lines (unless I've made an arithmetic error). Splitting into 2000 files of 85000 lines per file is doable.

So,

$ mkdir testing
$ cd testing
$ split -l 85000 -a 4 ../file2

The -a 4 option tells split to use four characters after an initial x to create the filenames for the new files. The files will be called xaaaa, xaaab, etc.

Then run the original grep -f on these:

for f in x????; do
  grep -F -f "$f" ../file1
done

This may make grep able to hold the now much smaller set of query patterns in memory.

UPDATE: With 145,526,885 lines, use split -l 72000 -a 4 to create roughly 2000 files.

Remember to clear out the testing directory each time you try to create a new set of split files.

Note that the split files from this answer are individually usable as input to any of the other answers you may get to this question.

  • highly appreciate the help, i am trying - will let you know if it works. also the 3.2 Gb file is at 145.526.885 lines (145.5m) – Axel Tobieson Aug 1 '16 at 21:15
  • @AxelTobieson There, I think I got it right now. Sorry for my confusion. No guarantees it will work though. The sort+join solutions are probably good too. – Kusalananda Aug 1 '16 at 21:32
  • @AxelTobieson I got some feedback and have a better version of the answer now. – Kusalananda Aug 1 '16 at 22:04
4

Costas answer is probably the best given your exact problem because you have a field that has a 100% match.

But if your problem really was grepping for millions of regexps in billions of lines, then GNU Parallel has a description of how to do that: https://www.gnu.org/software/parallel/man.html#EXAMPLE:-Grepping-n-lines-for-m-regular-expressions

The simplest solution to grep a big file for a lot of regexps is:

grep -f regexps.txt bigfile

Or if the regexps are fixed strings:

grep -F -f regexps.txt bigfile

There are 3 limiting factors: CPU, RAM, and disk I/O.

RAM is easy to measure: If the grep process takes up most of your free memory (e.g. when running top), then RAM is a limiting factor.

CPU is also easy to measure: If the grep takes >90% CPU in top, then the CPU is a limiting factor, and parallelization will speed this up.

It is harder to see if disk I/O is the limiting factor, and depending on the disk system it may be faster or slower to parallelize. The only way to know for certain is to test and measure.

Limiting factor: RAM

The normal grep -f regexs.txt bigfile works no matter the size of bigfile, but if regexps.txt is so big it cannot fit into memory, then you need to split this.

grep -F takes around 100 bytes of RAM and grep takes about 500 bytes of RAM per 1 byte of regexp. So if regexps.txt is 1% of your RAM, then it may be too big.

If you can convert your regexps into fixed strings do that. E.g. if the lines you are looking for in bigfile all looks like:

ID1 foo bar baz Identifier1 quux
fubar ID2 foo bar baz Identifier2

then your regexps.txt can be converted from:

ID1.*Identifier1
ID2.*Identifier2

into:

ID1 foo bar baz Identifier1
ID2 foo bar baz Identifier2

This way you can use grep -F which takes around 80% less memory and is much faster.

If it still does not fit in memory you can do this:

parallel --pipepart -a regexps.txt --block 1M grep -F -f - -n bigfile |
sort -un | perl -pe 's/^\d+://'

The 1M should be your free memory divided by the number of cores and divided by 200 for grep -F and by 1000 for normal grep. On GNU/Linux you can do:

free=$(awk '/^((Swap)?Cached|MemFree|Buffers):/ { sum += $2 }
          END { print sum }' /proc/meminfo)
percpu=$((free / 200 / $(parallel --number-of-cores)))k

parallel --pipepart -a regexps.txt --block $percpu --compress grep -F -f - -n bigfile |
sort -un | perl -pe 's/^\d+://'

If you can live with duplicated lines and wrong order, it is faster to do:

parallel --pipepart -a regexps.txt --block $percpu --compress grep -F -f - bigfile

Limiting factor: CPU

If the CPU is the limiting factor parallelization should be done on the regexps:

cat regexp.txt | parallel --pipe -L1000 --round-robin --compress grep -f - -n bigfile |
sort -un | perl -pe 's/^\d+://'

The command will start one grep per CPU and read bigfile one time per CPU, but as that is done in parallel, all reads except the first will be cached in RAM. Depending on the size of regexp.txt it may be faster to use --block 10m instead of -L1000.

Some storage systems perform better when reading multiple chunks in parallel. This is true for some RAID systems and for some network file systems. To parallelize the reading of bigfile:

parallel --pipepart --block 100M -a bigfile -k --compress grep -f regexp.txt

This will split bigfile into 100MB chunks and run grep on each of these chunks. To parallelize both reading of bigfile and regexp.txt combine the two using --fifo:

parallel --pipepart --block 100M -a bigfile --fifo cat regexp.txt \
\| parallel --pipe -L1000 --round-robin grep -f - {}

If a line matches multiple regexps, the line may be duplicated.

Bigger problem

If the problem is too big to be solved by this, you are probably ready for Lucene.

2

Important disclaimer: I have tested this on the data provided in the question. The loading of several gigabytes of data into a SQLite database may take a lot of time. The querying by using two text fields may be inefficient. Disk performance may factor in. Etc. etc.

The following sh script will create the SQLlite database database.db (this file will be deleted if it already exists), create the tables qadr and data, and load the data into the two tables (file1 into data and file2 into qadr). It will then create an index on data.adr.

#!/bin/sh

address_file="file2"
data_file="file1"

database="database.db"

rm -f "$database"

sqlite3 "$database" <<END_SQL
CREATE TABLE qadr ( adr TEXT );
CREATE TABLE data ( name TEXT, adr TEXT, tag1 TEXT, tag2 TEXT );
.separator :
.import "$data_file" data
.import "$address_file" qadr
VACUUM;
CREATE UNIQUE INDEX adri ON data(adr);
VACUUM;
END_SQL

The creation of the index assumes that the addresses in file1 are unique (that is, that the second :-delimited field is unique). If they are not, then remove UNIQUE from the CREATE INDEX statement (ideally, they are unique, and ideally, the lines in file2 are also unique).

I've never worked with SQLite and these amounts of data, but I know that multi-gigabyte imports into MongoDB and MySQL can be painfully slow, and that index creation likewise can be time consuming. So what I'm basically saying is that I'm just throwing this out there for someone with a lot of data to test.

Then, it's a matter of one simple query:

$ sqlite3 database.db 'SELECT data.* FROM data JOIN qadr ON (data.adr = qadr.adr)'
John|myemail@gmail.com|johnson123|22hey

or possibly even just

$ sqlite3 database.db 'SELECT * FROM data NATURAL JOIN qadr'
John|myemail@gmail.com|johnson123|22hey

Someone with more SQLite knowledge will surely give a constructive comment on this.

  • 1
    Just using : as a seperator is a overly simlistic. A : can be in the local part of a valid email address. – Anthon Aug 2 '16 at 11:29
  • 1
    @Anthon Didn't know that. This will require submitting the data to some formatting pre-import, which may require parsing and validating email addresses. I will consider that outside the scope of what I'm willing to do for this particular question. The other answers may be more fruitful if this is the case (or even regardless of whether there are exotic addresses in the list). – Kusalananda Aug 2 '16 at 11:34
  • 1
    the : separator can be fixed easily with awk or perl. split into an array using : as separator. if the array has 4 fields, use it as is. if it has 5 fields, join fields 2&3 with a :, delete field 3, and then use. "use" could be as simple as output with TAB delimiters and pipe into sqlite for import. or correctly quoted and CSV. or json, or XML. BTW, with files of this size, I'd be inclined to use postgresql or mysql instead of sqlite. – cas Aug 3 '16 at 12:31
2

If you need to avoid a DB solution (not sure why, it seems the best idea to me), you could do it by sorting the two files on the email addresses and then using the join command, which approximates what a DB would do.

Here's what I did:

sort -t: +1 file1 -o file1
sort file2 -o file2
join -t: -o 1.1,1.2,1.3,1.4 -1 2 file1 file2

That seems to do the right thing with your sample data. It sorts the files in place. If you don't want that, change the -o option on the sorts to temp file names and then use those in the join. Also, if you actually have other than 4 fields in the first file you have to account for that in the -o option to join.

For more details, consult man pages.

  • You completely fail to take into account that : can occur in the local part of an email address. – Anthon Aug 2 '16 at 11:27
1

Something like this would work, but I'm not sure it's a good idea depending on your use-case (untested):

while read f2line
do
  f1=$(grep $line file1)

  [[ ! -z $f1 ]] && echo $f1line 
done < file2

Another possible solution if you want more of a one-liner method (quickly tested below):

grep . file2 | xargs -i^ grep ^ file1

Which yielded:

root@7Z233W1 (/tmp)# cat f1
John:myemail@gmail.com:johnson123:22hey
Erik:thatwhatsup@gmail.com:johnson133:22hey
Robert:whatsup@gmail.com:johnson123:21hey
Johnnny:bro@gmail.com:johnson123:22hey

root@7Z233W1 (/tmp)# cat f2
1@gmail.com
rsdoge@gmail.com
mynameiscurt@hotmail.com
myemail@gmail.com

root@7Z233W1 (/tmp)# grep . f2 | xargs -i^ grep ^ f1
John:myemail@gmail.com:johnson123:22hey
  • 1
    The second solution look more plausible as the first one does one grep per line in a 3.2 Gb file. – Kusalananda Aug 1 '16 at 20:01
0

Here's a version of Kusalananda's script that uses perl to transform file1 from : separated to TAB separated before feeding it into sqlite3.

The embedded perl script checks to see if there are 5 fields rather than 4. If there are, it appends field 3 to field 2 (restoring the : that was removed by the autosplit), then deletes field 3.

#!/bin/sh

address_file="file2"
data_file="file1"

database="database.db"

rm -f "$database"

sqlite3 "$database" <<END_SQL
CREATE TABLE qadr ( adr TEXT );
CREATE TABLE data ( name TEXT, adr TEXT, tag1 TEXT, tag2 TEXT );
.mode line
.import "$address_file" qadr
END_SQL

perl -F: -lane 'if (@F == 5) {
    $F[1] .= ":" . $F[2];  # perl arrays are zero-based
    delete $F[2];
  };
  print join("\t",@F);' $data_file | 
    sqlite3 "$database" -separator $'\t' '.import /dev/stdin data'


sqlite3 "$database" <<END_SQL
VACUUM;
CREATE UNIQUE INDEX adri ON data(adr);
VACUUM;
END_SQL

IMO, sqlite isn't suitable for a database this large. I'd recommend using mysql or postgresql instead. For this kind of task, mysql's raw speed probably makes it a better choice - it's faster for simple things like this but postgresql is much faster for more complex tasks - in my experience, pg is "smart fast" (i.e. it can achieve massive speed improvements in complex tasks by working smart rather than working hard), mysql is "dumb fast" (i.e. it works hard, without much capability to work smart).

The script above can easily be adapted to work with the psql or mysql command line clients instead of sqlite3, but i'd modify the CREATE TABLE commands to use fixed-size CHARACTER(size) instead of TEXT, where size is a reasonable guess at what the maximum size for each field is - e.g. maybe 255 characters for the adr field, and 10-50 characters for the others.

one possible optimisation is to careful choose the field sizes so that each record is an even divisor of your drive's block size (taking into account mysql/postgresql's per-record overhead). 512 bytes should be good for all common block sizes. make the fields whatever size you need, and add an extra, unused, CHARACTER(size) field to make up the difference. The point of doing this is so that records never cross a block boundary, so the db engine only ever has to read in one disk block to get all of the data for a given record (actually, it will read multiple records in one block with most current block sizes, but that only helps performance, can't hurt it).

https://dba.stackexchange.com/ is probably the best site to search or ask for info about optimising record sizes.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.