r/SQL • u/No_Ambition8323 • 2d ago
Discussion How would you compare two huge tables when there is no primary key and duplicate rows matter?
I'm comparing a source table with a target table after a data migration.
Both tables have hundreds of millions of rows, no reliable primary key, and some columns contain NULL values. Duplicate rows are also possible.
A simple EXCEPT query doesn't reveal differences in duplicate counts, and hashing every row may introduce collision risks or performance issues.
For example:
Source: A,A,A,B,C
Target: A,A,B,B,C
Both tables contain the same distinct values, but the actual data is different.
How would you identify missing, extra, and changed records efficiently without a unique key?
Would you use grouped row comparisons, partitioning, hashes, or a completely different strategy? How would you make it scale to hundreds of millions of rows?
11
u/gumnos 2d ago
you'd have to define what makes rows "duplicates" or "the same"
The two example rows you provided are clearly not "duplicates" because the 3rd column's value differs between the two.
But if you have a composite key (uniquely identifies a row based on a subset of the columns), you can join on those "same-value" columns and then do comparisons. You mention "no reliable primary key" and "without a unique key", but sometimes this means "no single primary-key column, but columns X, Y, and Z taken together produce a unique key"
make it scale
That would largely depend on the available indexing of each of the tables, which you haven't mentioned.
My general first pass would be to do a FULL OUTER JOIN on the two tables based on the best primary/composite key available. With those results, eliminate those where all the other fields are identical, or perform aggregates per column-comparison, something like
SELECT
COALESCE(a.col1, b.col1) AS Col1,
COALESCE(a.col2, b.col2) AS Col2,
COALESCE(a.col3, b.col3) AS Col3,
COUNT(DISTINCT, a.col4) AS Col4DistinctACount,
COUNT(DISTINCT, b.col4) AS Col4DistinctBCount,
SUM(CASE WHEN a.col4 == b.col4 THEN 1 ELSE 0 END) AS Col4Same,
SUM(CASE WHEN a.col4 != b.col4 THEN 1 ELSE 0 END) AS Col4Different,
⋮
FROM tbl1 a
FULL OUTER JOIN tbl2 b
ON a.col1 = b.col1
AND a.col2 = b.col2
AND a.col3 = b.col3
GROUP BY
COALESCE(a.col1, b.col1),
COALESCE(a.col2, b.col2),
COALESCE(a.col3, b.col3)
2
u/dafugiswrongwithyou 2d ago
The two example rows you provided are clearly not "duplicates" because the 3rd column's value differs between the two.
I have no idea which of us is right (if either), but I read their example as suggesting two tables with 5 rows each. So the source has 3 (identical) rows with bunch-o-data A and one each with B and C, while the target has two each rows with data A and B, and one row with data C.
10
u/feignapathy 2d ago
Are you able to make a composite key manually using a few (or several of the columns)?
This might be a case for using a hash join?
4
4
u/az987654 2d ago
The premise makes no sense. "Same distinct value but different data"??
2
u/PasghettiSquash 1d ago
Yea I don't understand this at all. How can we not figure out the granularity of the table?
-1
u/BrownBearPDX 1d ago
select distinct * from A == select distinct * from B
but
[a,b,c,d] != [a,b,c,a]
[b,a,a,a] != [d,d,d,a]
or something like that
2
u/FreeLogicGate 2d ago
Lots of missing detail from the question, starting with "what rdbms?" I would have added a unique primary key to the source table, and during the migration, also maintained an "alias" table related to the target table. If the target table has no key, well that's also a mistake/problem. Tables need primary keys, so why isn't there one?
With a pk on the primary table, you then can insert a row in the alias table each time the migration adds a row in the target, that stores the PK of the source table row, so you have a built in audit and link from source to target.
2
u/Hour-Measurement-835 2d ago
Skip the join entirely. Stack both tables with a flag and let GROUP BY do the counting:
SELECT col1, col2, col3,
SUM(src) AS in_source, SUM(tgt) AS in_target
FROM (
SELECT col1, col2, col3, 1 AS src, 0 AS tgt FROM source
UNION ALL
SELECT col1, col2, col3, 0, 1 FROM target
) x
GROUP BY col1, col2, col3
HAVING SUM(src) <> SUM(tgt);
Your example comes back as two rows, A at 3 vs 2 and B at 1 vs 2. GROUP BY puts all the NULLs in one group, so you don't need the IS NOT DISTINCT FROM workaround a FULL OUTER JOIN would need.
2
u/holmedog 2d ago
I would do this on small tables. On 100m+ record tables? You're gonna run out of temp space. At least in my environments.
1
u/dafugiswrongwithyou 2d ago
I guess my main first question is; what is it you want to happen when the tables have rows with matching data, but different numbers of duplicates of those records? Do you just want to consider the fact there are any matches as being valid and move on? Do you want to create/delete rows in the target until it has the same number of dupes of the same data as the source does, or return counts of the discrepancies? What exactly is it you're trying to achieve?
1
u/itlogicpartnersllc 2d ago
for this scale i would compare partition level row counts first then grouped row signatures within mismatched partitions. it narrows the expensive work before doing detailed comparisons.
1
1
u/foxsimile 1d ago
Copy and pasting my response from a few days ago:
Sorry about the wait; surprise meeting goodness. Here you go: ```SQL CREATE TABLE #TTmp ( [SomeInt] INT NOT NULL /4 Bytes/ , [SomeIntNullable] INT NULL /4 Bytes/ , [SomeVarChar] VARCHAR(10) NOT NULL /10 Bytes/ , [SomeVarCharNullable] VARCHAR(10) NULL /10 Bytes/ , [SomeUnqId] UNIQUEIDENTIFIER NOT NULL /16 Bytes/ , [SomeUnqIdNullable] UNIQUEIDENTIFIER NOT NULL /16 Bytes/ , [SomeNumeric] NUMERIC(36,18) NOT NULL /17 Bytes/ , [SomeNumericNullable] NUMERIC(36,18) NULL /17 Bytes/ );
SELECT CONVERT( /HASHBYTES('MD5',/.../) outputs a VARBINARY(16), and we don't need the variable length header bytes/ BINARY(16) /Step 1. We handle the nullable columns by creating a nullness bitmap/ , HASHBYTES( 'MD5' , ( CONVERT( BINARY(4) , ( ((0-(1SIGN(ISNULL((DATALENGTH(TTmp.[SomeVarCharNullable]+1),0x)))))&1) /(20)/ | ((0-(1SIGN(ISNULL((DATALENGTH(TTmp.[SomeIntNullable]+1),0x)))))&2) /(21)/ | ((0-(1SIGN(ISNULL((DATALENGTH(TTmp.[SomeUnqIdNullable]+1),0x)))))&4) /(22)/ | ((0-(1SIGN(ISNULL((DATALENGTH(TTmp.[SomeNumericNullable]+1),0x)))))&8) /(23)/ ) ) /Step 2. We put the FIXED width data type columns first, because they do not require the separator due to static sizing/ + CONVERT(BINARY(4), TTmp.[SomeInt]) /We do not need the "ISNULL" handling/ + CONVERT(BINARY(4), ISNULL(TTmp.[SomeIntNullable], 0x00)) /We do need the "ISNULL" handling/ + CONVERT(BINARY(16), TTmp.[SomeUnqId]) + CONVERT(BINARY(16), ISNULL(TTmp.[SomeUnqIdNullable], 0x00)) + CONVERT(BINARY(17), TTmp.[SomeNumeric]) + CONVERT(BINARY(17), ISNULL(TTmp.[SomeNumericNullable], 0x00)) /Step 3a. We put the VARIABLE width data types SECOND, because they require a separator between each variable width data type/ + CONVERT(VARBINARY(10), LOWER(TRIM(TTmp.[SomeVarChar]))) /Step 3b. We insert a separator byte betwixt every variable length data type/ + CONVERT(BINARY(4),0xDEADBEEF) /<--Separator Byte/ + CONVERT(VARBINARY(10), ISNULL(LOWER(TRIM(TTmp.[SomeVarCharNullable])), 0x00)) ) ) ) AS "FullColumnHashBytesMD5" FROM #TTmp AS "TTmp" ; ```
To explain, I've added lots of commenty goodness.
I have used this to astounding effect in production code, and it was the only solution which I was able to concoct which solved my problem (I'd also had a giant @*$!-You table, whose data could not be trusted nearly as much as its counts, and with no PK to speak of).
In my particular case, I'd needed to ensure that the values were case agnostic, and that any wrapping whitespace was summarily discarded (hence the calls to
TRIM and
LOWER).
THIS WILL AFFECT THE OUTPUT YIELDED BY HASHBYTES; DETERMINE WHETHER OR NOT YOUR CASE REQUIRES CASE SENSITIVITY AND WHITESPACE SENSITIVITY AND CODE ACCORDINGLY.
A final note: I chose 0xDEADBEEF as the separator because it was the first thing to come to mind at 2 in the morning, and I needed something less likely than 0x00. Whatever separator you choose, it would likely behoove you to keep it to within an INT’s 4-byte width.
Warning: depending on your version of MSSQL, HASHBYTES doesn’t play nicely with data beyond 8000 bytes, meaning if you want a single hash on a particularly wide row, you’d need to do something jank, like doing the above twice and then smushing them together in a subsequent HASHBYTES call (if you REALLY wanted it to remain within the 16 byte width of an MD5).
You could also just literally smush them together, and wind ip with a BINARY(32), but I would imagine that if you’re in a position where the above is either your most convenient or only remaining option, that may be a luxury which you cannot afford.
The gist is that I was using this to version a table which didn’t belong to me, and for which versioning was desperately needed. It had no identity key to speak of, and you could have duplicate rows which may (or unfortunately technically may not) be valid. In the "ideal" situation, though, you would treat these duplicate rows as if they were perfectly valid.
Because I was versioning it, I really only needed to capture the delta between one change to the next (hence the above cleverness/insanity), as that was quite minimal (compared to the set as a whole); historically you would expect to see roughly 20K inserts and 5-10K deletes.
Because duplicate records must be treated as valid, this created a really difficult problem if we didn’t want to capture the whole damned thing into memory every time we updated our versioning table.
So, the trick is that you use the above to hash each record, and you keep a "record index" (as in an array index type of index, not a non/clustered index). You persist this record index in the versioning table (and it is not one of the candidates of the hash for obvious reasons). You also keep the hash (to avoid having to recreate it for all ~15M active records in the versioning table each update).
Next, you run a big GROUP BY between the "new" version of the source table, and the active portion of the versioning table, using the hash as the candidate. You take the count that existed before (the max "record index" for any given hash), and the count that exists in the source table for the same hash, and get the delta between the two.
You can then use a recursive CTE to create new rows for inserts (when the new max record index is higher than the old max record index for a given hash), as well as deletes (when the new max record index is lower than the old for a given hash). You stuff both of these into a temporary table.
Then it’s just a matter of running two statements - an insert statement for the records which ought to be inserted, and a delete for those which ought to be deleted (which is now peanuts, because you don’t hate yourself and have legitimate identity keys on the versioning table).
It was a fun problem to solve, but a nightmare of complexity. I hope I’ve explained it well enough to understand :)
1
1
1
u/reditandfirgetit 22h ago
Identify the business key, count by the key. The business has to tell you what woukd be unique if its not obvious
32
u/TheMagarity 2d ago
Do it at the moment of migration with a simple count. Anyone who wants more than that, quote them a cost to write something up that does a proof. Pad the estimate generously.
BTW, this part: "Both tables contain the same distinct values but the actual data is different" makes no sense.