Do a select * from table order by some-key from both tables (assuming they have a unique index...), then repeatedly fetch rows from either side, reporting mismatches. Unless your database is cold, the network ought to be the bottle neck here - assuming your client libraries negotiate package size on your behalf. If the database is cold, reading from disk may be the bottleneck (depends a bit on the type of index), but there will be no way around that. If it's got to be read from disk, it's got to be read from disk.