implementing keyValue pair, with key as a Pair<T,U>

Hi,
I'm looking for some help implementing an issue i have.
main purpose is aggregating information from DB

I get data from a DB, and that table has 2 primary keys.
for each pair (primary key) i create an object that holds all the information, and after all the DB is read, i take each object and put its information in a differnet DB table.
I need to clarify that performance is very important, dealing with about 1milion rows every time.

The issue im having is how to hold that info. I tried using a Dictionary, the key being Pair (simple object i created).
however, when using Dictinary.contains() didnt recognize 2 similar Pairs, and created a new 'similar' object instead of returning the one already existing.

I am not sure if I should implement Icomparable,
or maybe there is a different way altogether that might be better.

Thanks for your help