1

Typically the solution for comparing if 2 relational db tables (I am using AWS Athena) are equal is to do full outer join on all the columns but adding an extra column to each dataset that acts as a marker.

select *
from 
(
    (select *, 't1' as t1 from table1 where ...) t1
    full outer join
    (select *, 't2' as t2 from table2 where ...) t2
    on t1.col1 = t2.col1 and t1.col2 = t2.col2 and ...
)
where t1 is null or t2 is null

This gives you the differing rows. But I want to go a step further and find on which columns the row differ.

The problem I'm having is that I'm not sure how to model this, even in a script. If a join failed, that means that the rows where t2 is null (i.e rows in t1 not in t2) and rows where t1 is null (i.e rows in t2 not in t1) could differ on any of the columns or even just not be present in the other table at all. How would I know what 2 rows to compare to find the differences?

I'd appreciate some help modeling the algorithm here. The above query will give me what rows do not have a full match in the other table. But for each row where there's a mismatch, how do I find where the mismatch occurred?

1 way I can think of doing this is once I have the result set of differing rows, I will join the t1 diffs with the t2 diffs on each column (i.e "join on col a", then "join on col a and col b", then "join on col a and col b and col c"), and that will tell me the differences, but I'm sure there are edge cases + that is a lot of queries to do for wide tables.

Another way I can think of is grouping. I would group on all the columns, which gives me a list of groups, and then I order by all the columns. Similar columns would thus show up next to each other, but I don't know if this is fool-proof because what if the columns match on col a, b, d but not col c, and I order by a, b, c, d?

Reminder that this is in AWS Athena, so certain SQL statements are not available.

10
  • 1
    For the general case, this is going to be a factorially hard combinatorics problem. What do you think are the "differences" between the two sets {(1, 2, 3), (4, 5, 6), (7, 8, 9)} and {(1, 5, 9), (4, 8, 3), (7, 2, 6)}? Commented Mar 26 at 21:32
  • @PhilipKendall yeah I agree, to me it seems like a tuple similarity problem, or I define subsets of dimensions and join on each of those subsets making this is a 2^n problem. For your example, I guess I would say they differ on col 2 and col 3 (because col 1 of 1,4,7 is the same). Commented Mar 26 at 22:08
  • But column 2 is also {2, 5, 8} and column 3 is {3, 6, 9} (yes, this was obviously deliberate). What makes you say column 1 is more important than column 2 or 3? Ordering? Commented Mar 26 at 22:12
  • The set of values in each column is the same, but when you take a subset of the columns, the sets differ. Like if we know that column 1 matches completely, then we would join on column 1, and we would see differing values for col 2 and col 3 coming from the different sets, 2 vs 5 and 3 vs 9 for for col 1 = 1 for example. However I recognize we don't know in advance that col 1 is the same. Commented Mar 26 at 22:18
  • 1
    So what would you say are the differences between {(1, 2, 3), (4, 5, 6), (7, 8, 9)} and {(7, 2, 6), (1, 5, 9), (4, 8, 3)}? Unless you have a well defined sort key, you can't assume the ordering of very much at all in SQL. Commented Mar 26 at 22:21

3 Answers 3

3

Tables we care about have a Primary Key. Always.

Assume both tables have similar PK. JOIN on that, with filtering WHERE conjunction to pick out mismatched rows. Store them in a temp table and solve that as a separate problem.


Compute MD5 or SHA3 hash of all rows during the JOIN on PK. Use that instead of a multi column conjunct. Cache such hashes if you frequently re-compare tables.


Add an “updated” timestamp column, indexed, to tables you frequently re-compare. Then an index scan of the < 1% of rows that recently changed will quickly reveal the diffs, while ignoring the vast number of boring rows that will prove uninformative.


Database tables without PK are the moral equivalent of text files. So export to .CSV format, perhaps with first column being the row-wise hash, run it through /usr/bin/sort, and use diff -u to review the wreckage.

2
  • This is a good solution but unfortunately my datasets do not have primary keys, rather each row differs on the values for all the columns combined. In essence the primary key is a composite key of all the columns Commented Apr 3 at 19:31
  • Your datasets are badly, badly broken. Where many folks have well organized tables that show a PK -> attributes mapping, yours are just jumbled shoe boxes of sales receipts in random order. It would be worth your while to improve your data hygiene. // For shoebox tables A, B, compute these columns, perhaps in a pair of new temp tables: hash_a, hash_b, where we hash across all columns. Now compute common rows, the intersection of hashes. Whatever leftover hashes are not in that common set are of interest. Report on them as you see fit. Perhaps there's some helpful reporting sort order for them.
    – J_H
    Commented Apr 3 at 19:38
3

That way madness lies

Spoiler alert: you're going to want to back out of this quest you're on.

These kinds of question and answers are difficult, because if I just tell you it's a bad idea, you're going to ignore my answer as needlessly dismissive. So instead, let me be your tour guide on this road to madness. We'll skip the concrete details and just figure out approximately how monumental this task actually is.

Your question makes grammatical sense, but not logical sense in the way that you're thinking it does. The inversion you're making here (instead of looking for matches, you're looking for differences) is semantically easy to describe, but deviously hard to write out.

Let's start with some back of the napkin math.

With a being rows in table A, and b rows in table B, you will get a result set approximately a*(b-1) in size, assuming you've filtered out any equal combinations. For the purpose of the example, let's work with the assumption that you have 1000 rows per table.

Based on the question, you're thinking of writing clever filters to only display close comparisons that only differ minimally. First of all, designing this will take even more effort; but more importantly this is another combinatorial problem op top of the previous data squaring problem.

It's the choose amount_of_columns_allowed_to_be_different from total_amount_of_columns function, which I'll call p). We'll use a specific example: let's say that there's 10 columns total, and you allow up to 3 columns to be different. So how many group of columns are there that could be wrong but still within the maximum of 3?

  • Well, there's 10 (10 choose 1) ways for there to be 1 column that's wrong, it's either col1, or col2, or ...
  • There's 45 (10 choose 2) ways for there to be 2 columns that are wrong: col1 plus one of nine others, col2 plus one of eight others, ...
  • There's 120 (10 choose 3) ways for there to be 3 columns that are wrong: col1+col2 plus one of eight more, col1+col3 plus one of seven more, ...
  • Bringing the grand total to 175 inequality comparisons.

Each individual comparison needs to be expressed as a series of == vs != across these 10 columns, so that's 1750 comparisons you'll be writing.

Remember how I said that your logic cannot invert from equality to inequality? Here's the part where I point out that there's 1 way for things to be equal (every column is a == check), and 175 ways for them to be not equal but still >=70% equal. It gets combinatorically worse the more you loosen the constraints on how equal the data is allowed to be.

For the purpose of not going completely off the rails, I'm going to assume that your value comparisons are exact equality and there's no funky "A.col1 contains B.col1 or vice versa" kinds of logic.

But let's say that you're not afraid of typing out this query, and you're still on board with your plan. So, 175 ways to express inequality leading to 1750 checks. These checks need to be performed for every combination. With 1,000 rows per table, that's 1,000,000 combinations, each performing every individual check, so we're looking at about 1,750,000,000 or close to 2 billion evaluations.

And that's a data set of 1,000 rows. You're using AWS Athena so I'm inferring that we're talking about machine-learning-levels of data. Considering this, even at a conservative million rows per table, we're talking 1,750,000,000,000,000 evaluations or close to 2 quadrillion evaluations.

And that's not even getting into the processing of that result set. One row is going to be different-within-limitations from multiple rows, so you're not going to get a neat mapping from one row to the next.

Assuming that equality/inequality is 50/50 for each individual column, this means that there's 1,024 (210) ways rows can be (in)equal to each other, and we're allowing 175 of them (176 if you include full equality), so that's about 17%. This means that for every row in table A, about 1 in 5 rows in table B is going to match. To put it formulaically, your expected result set size is going to be a * b * 0.17. For 1,000 rows, that's 170,000 results. For 1,000,000 rows, that's going to be 170,000,000,000 (billion!) results.

To put it differently, this means that for every row in table A, you're going to get 170,000 suggestions for its partner in table B. While it might be reasonable to filter this down based on the amount of matching columns, how are you going to choose between suggestions that have an equal amount of non-matching columns?
It should be clear that this can't be done manually. If you're thinking of doing a proximity match based on how different the column values are, you can increase all the above numbers by several orders of magnitude. If you want to assign weights to each columns, that's another calculation and mapping to design and execute.

I sincerely hope that we don't need to travel this road to madness any further. If you're not running for the hills now, then I don't know how to further explain why your quest is an impossible one.

The eventual retrospective

The real lesson here is that it's easy to turn an organized structure into a pile of stuff, and it can be nigh impossible to turn that pile of stuff back into an organized structure. I suggest you abandon ship now, and the next time you're thinking of cutting corners by not modeling your data storage properly, remember the ship you had to abandon.

A more fruitful avenue would be to instead clean up the data before trying to figure out how to compare it. It'll still be inefficient doing it after the fact (compared to keeping it clean from the get go), but if you are stuck with this task then this is the bullet you're going to have to bite.

6
  • Thanks for the thorough analysis! Commented Apr 4 at 0:07
  • But does it really require that many comparisons? Let's say I have n rows in dataset 1 and m rows in dataset 2. Then I would compare each row in d1 (n) to each row in d2 (m) which is n * m comparisons. Assume there are 10 columns, I would be doing n * m * 10. For each 2 rows I compare, couldn't I just see which columns they do not match on, and use that as a key? then I could group all rows together by the key, i.e which cols they match on. Commented Apr 4 at 0:23
  • I think that would be way less comparisons then saying "let me calculate all possible column groups of size k where k = 1...10 and then find the rows that match on that". Basically, using your example, I would have 175 possible keys, and each key maps to a list of rows that all match on that combination of columns for that key. n*m*10 total evaluations are done. Commented Apr 4 at 0:24
  • 1
    @JeremyFisher "I would be doing n * m * 10" You would be doing that for equality, not inequality. Things can be equal in one way, but they can be inequal in many different ways. For example, my car and your car can either be the exact same (a red 2011 Porsche 911 DX), but if they're not, there's many possible reasons why they can be different (different color, different brand, different make, different trim level, different year), including combinations of all of these possible differences.
    – Flater
    Commented Apr 4 at 0:34
  • @JeremyFisher [..] "then I could group all rows together by the key, i.e which cols they match on" You need to understand that inequality cannot be expressed in a single way, which means you can't group by "is inequal" in a logically cohesive manner without expressing which kinds of inequality you're interested in - I'm focusing on cases of "somewhat equal but not exactly", not just all of !equal. At best, you could count the amount of inequal columns and pick the ones with the lowest count, but this doesn't help you decide between options that have the same amount of different columns.
    – Flater
    Commented Apr 4 at 0:36
0

This gives you the differing rows. But I want to go a step further and find on which columns the row differ.

As you point out this is really giving you rows from t1 which have no match in t2 and vice versa. Subtly different from "differing rows"

When you take it a step further and want to know on which cols they differ, well row 1 in t1 is obviously going to be different from all but one row in t2. Presumably you don't actually want all the data squared?

If you are using Athena I assume you have a machine learning problem? It would seem to me what you really want to do is group similar rows to find categories.

This can be done by turning each columns value into an integer and plotting the rows as a vector in n dimensional space. You can then group by proximity. You will be able to see clusters of rows which are extremely different from other clusters, groups where everything is the same except a couple of fields etc etc. Various models can be used to extract the categories.

Once you have categories of rows you can start asking meaningful questions about differences, by comparing individual rows against the set as a whole and categories within the set.

  • Which column has the most variation?
  • Is this row "normal"?
  • How many rows fall outside the main groups?
2
  • I don't have a ML problem, but I do see this is as a vector problem where as you said I'd be resolving each row to an int and then grouping or sorting. Commented Apr 3 at 19:32
  • thats an ML problem. there are libraries to help you
    – Ewan
    Commented Apr 3 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.