Definitely use a database, as a number of folks have already pointed out. If you go all the way and use a relational DB, you can incrementally load into it as new data becomes available, then use whatever query tools you want (or write) to work on the bits of the database you need to. It's the best way once things get reasonably big, and you're well past 'reasonable' here. :)

If you're curious as to the current size of things, you can always play with the Devel::Size module, which'll figure out how much memory your hash is using right now.