Quick way to validate two tables against each other
Here's what I've done before:

(SELECT 'TableA', * FROM TableA
EXCEPT
SELECT 'TableA', * FROM TableB)
UNION ALL
(SELECT 'TableB', * FROM TableB
EXCEPT
SELECT 'TableB', * FROM TableA)


It's worked well enough on tables that are about 1,000,000 rows, but I'm not sure how well that would work on extremely large tables.

Added:

I've run the query against my system which compares two tables with 21 fields of regular types in two different databases attached to the same server running SQL Server 2005.  The table has about 3 million rows, and there's about 25000 rows different.  The primary key on the table is weird, however, as it's a composite key of 10 fields (it's an audit table).

The execution plans for the queries has a total cost of 184.25879 for UNION and 184.22983 for UNION ALL.  The tree cost only differs on the last step before returning rows, the concatenation.

Actually executing either query takes about 42s plus about 3s to actually transmit the rows. The time between the two queries is identical.

Second Addition:

This is actually extremely fast, each one running against 3 million rows in about 2.5s:

SELECT CHECKSUM_AGG(BINARY_CHECKSUM(*)) FROM TableA

SELECT CHECKSUM_AGG(BINARY_CHECKSUM(*)) FROM TableB


If the results of those don't match, you know the tables are different.  However, if the results do match, you're not guaranteed that the tables are identical because of the [highly unlikely] chance of checksum collisions.

I'm not sure how datatype changes between tables would affect this calculation.  I would run the query against the system views or information_schema views.

I tried the query against another table with 5 million rows and that one ran in about 5s, so it appears to be largely O(n).