1. Read product name (pn.o) and price (p.o) from the old file. Read product name (pn.n) and price (p.n) from the new file.
2. If pn.o eq pn.n, goto 5.
3. If pn.o lt pn.n, then pn.o was deleted. If the old file is exhausted, goto 8, else read the next line of the old file into pn.o and p.o and goto 2.
4. (pn.o gt pn.n) This means pn.n is a new product. If the new file is exhausted, goto 9, else read the next line of the new file into pn.n and p.n and goto 2.
5. If p.o != p.n, the price was modified. Else there was no change in the product.
6. If the old file is exhausted, goto 8, else read the next line of the old file into pn.o and p.o.
7. If the new file is exhausted, goto 9, else read the next line of the new file into pn.n and p.n and goto 2.
8. pn.n is a new product, and so are all other unread entries in the new file. Read them, adjust your database, and end the program.
9. pn.o is a deleted product, and all other unread entries in the old file were deleted as well. Read them, adjust your database, and end the program.

Abigail

I second Abigail's suggestion. To reiterate -- first sort, then do the comparison.

A while back I was twiddling around during some "downtime" and I cooked up the following little Perl exercise. Remove duplicate email addresses from a file where each line was an address. So, I applied the usual, build an array, sort, take out the unique addresses, write them to a new file. Took just under 2 mins on my fast Windows box at work, and about 3.5 mins on my relatively pokey iBook at home. Both machines had half Gb ram.

The file was 300+ Mb in size and had about 145 million rows in it.

;-)

I applied the usual, build an array, sort, take out the unique addresses, write them to a new file.

For me, "the usual" would be:

    $ sort -u file > file.$$ && mv file.$$ file
[download]

Would even work without much ram.

Abigail

It does depend on the files being in the same order each time, so you might have to sort them first.

Fortunately there is a Unix command called "sort" which can probably do that for you.

How about an array of MD5 signatures for each line? If you've got two files with 1.2 million rows each and an MD5 signature is 16 bytes long then you should be able to index them both in around 400MB of memory. If Perl adds too much overhead to the arrays (and it might) then use Tie::IntegerArray or just program it in C (heresy!).

If the rows have a primary key you might be able to use Bit::Vector to setup bitmaps to test for insertions and deletions. That would likely use less memory than an array of 16bit MD5s, depending on how sparse your key-space is.

-sam

So what do I do? How can you compare two files for changes when both files are so large that you either run out of memory or it takes so long to process them that the information in the file is out of date.

I would consider other options. Here's one that might work for you: Use separate logical databases for each customer, and use UNION queries that span the separate logical databases. (MySQL 4.0 supports UNION queries). This looks like:

    SELECT stuff FROM db1.t WHERE stuff like 'foo%'
    UNION
    SELECT stuff FROM db2.t WHERE stuff like 'foo%'
    UNION
    SELECT stuff FROM db3.t WHERE stuff like 'foo%'
[download]

In such a scheme, you would build (and possibly cache) the query at runtime based on the current "complete" databases. When new data for a vendor arrived, you would create a new database, bulk load the new data into that database (without having to worry about deleting expired product records), then switch that database to be current. Then, arrange for new queries to use the new database. Since there may be queries active at the time of the switch, you may need to introduce some delay before recycling (deleting) the old database for that vendor.

The beauty of this scheme is that

• it saves you from having to compute deltas,
• it allows you to bulk load data without having to worry about transactions (bulk loading can be a lot faster), and
• you don't incur transaction overhead when you're inserting while querying.

The (small) downside is that you can't embed a static query (or set of queries) in your applications. Instead, you have to either construct new queries dynamically, or read the cached ones.

Probably true. In my paying job I'm only dealing with data sets on the order of 10**3 or 10**4. I simply don't have sets on the order of 10**6 or larger to test against. I would welcome a suggestion for a publicly available data set of that magnitude against which I could test List::Compare and try to refine it.

Jim Keenan (author of List::Compare)