Comparing whether two very large text contents are different or not efficiently

Question

I have a MySQL database with a column Body MEDIUMTEXT. Until now I used to only store the contents into it. There was no update option for the users of the application. Now, I wanted to add an update option to the content(To make it easy, just think it like a stack exchange editing a post scenario).

I know about not optimizing something until it's needed but at the same time I don't want to design a system now and later realise it was a stupid thing to do in the first place.

So, I got some ideas:

Retrieving the whole Body from the database and comparing both character by character.

The problem in this idea is: Database overhead(even though it is for inserts, I guess the connecting, sending, parsing and closing is same for every query) of sending a query(2 units), parsing(2 units), retrieving the huge data over the network (even though it's on the same datacenter but still there will be some latency... right?) and the load on application server to actually hold the data in the variables and comparing both the strings(both Memory and CPU load)

In MySQL, MEDIUMTEXT is 16MB max. So, in the worst case, I need to transfer that over network and hold that data(old and new) in a variable in the application server. So, even if I'm handing 32 requests at a time, it will occupy 1GB of RAM (32MB * 32 req = 1024MB) and additional CPU load while checking that content.

It might be in very rare cases that 16MB will be sent every time and the more inefficient thing here is actually comparing that 16MB content character by character. But is it too much to always estimate the worst case while designing a system?

---

Storing a hashed value of Body in a column and comparing the hashes.

I store an additional column in the table with hashedBody value of the Body. Whenever an update comes to the server, I just retrieve that hashedBody value from the database. Here I can save on network transfer by transferring only hashBody value. Now, I hash the new content came from the User and compare the smaller hashes and update if the hashes are different.

But if the hashing algorithm is fast, chances are they might encounter a collision and the new content which is different will not be updated and if the hashing algorithm is secure and slow, there are less chances for collision but I might use more CPU than in the first naive method above.

---

And for the questions I have:

1. Is it too much to always estimate the worst case while designing a system?

2. Is the first method good?

3. Is the second method good? Are there any hash algorithms other than md5? Like less collisions and fast?

4. Is there any other new approach or idea to tackle this?

P.S. Yeah I know that I'm clearly overthinking about this but I'm afraid not considering these small mistakes/design can cause problems which I can't foresee. I just want to make a decision based on all the information and know all the problems that I can or will encounter in the future rather than make a decision based on ignorance and come across problems out of the blue and panic.

---

Edit: 1 I forgot to mention but I'm maintaining a History table to update that with old values(like maintaining a versioning system). So, I can't just update. I need old values to insert it into History table and new values into Post table.

Answer 1

Hashing is the quick way to check if something is different than what's already inside the database. This applies whether it's md5 (which I think is just fine for this purpose) or another algorithm.

However, it does not tell you whether the hashed content A is really the same as the hashed content B. As you said, there is still the possibility that two different content produce the same hash (collision). Whether it's md5 or another, whether you compare a single hash or a set of 42 different ones. This would just reduce the odds.

...so, in the end, even if the hashes are the same, you'll have to send everything over the wire anyway to compare them. ...so in the end, the hashes will be useless and the plain approach of updating the value is the only possibility ...and you know what, you don't even have to care about comparing them. Just update it. ;)

Answer 2

It depends how sure you want to be that two texts are not equal. If you use a good hashing algorithm, and a 256 bit hash, then in practice equal hash means equal strings.

Since you are talking about a real server, you might calculate the probability that a meteor hits your server and destroys it, and another meteor destroys your backup, and you can’t compare the strings at all. If the chances of equal hashes are lower then you’re fine.

Answer 3

Some databases will perform the diff on all to-be-updated columns on their own and use it to decide whether the column needs to be physically updated or it can be ignored because no change is implied. MySQL/MariaDB is one such and so you can use it to your advantage. After update query is executed you can check number of affected rows to see if any changes were actually made. And so there is no need for you to duplicate the diff check on the db client side.

Now let me recap your current db structure and make some analysis of it.

I hope the pseudo syntax for table definition is clear enough; I've also included id_user column just to show that column that cannot change in any version of the same post belong to the parent table, and ofc there should be some timestamps but i ommitted it here.

This is about what you have:

Posts(pk(id_post), fk(id_user), body)
PostHistory(pk(id_post_history), fk(id_post), version, body)

and example data

Posts: id_post, id_user, body
#0           1,       1, "post 1 version 3"
#1           2,       1, "post 2 original"

PostHistory: id_post_history, id_post, version, body
#0                         1,       1,       1, "post 1 original"
#1                         2,       1,       2, "post 1 version 2"

Now if you wanna create history entry only for updates that do actual change. If you update Posts first, you cannot make history from the old data because you have just overwritten it. So you have to

• pull the old data to memory first (old body going db->app; both old and new body in app memory).
• Then you perform update (new body going app->db).
• If db sais "no affected rows" you are done, but you also discard old body that you loaded and now didnt use
• if 1 affected row, you send old body to history table (old body going app->db)

In summary:

• you had two bodies (old and new) in app memory at the same time
• in best case you transfered old body db->app
• in worst case you transfered new body app->db and old body there and back

So thats 2 bodies in memory and 3 body transfer within 3 queries in case of body changes. Or 2 bodies in memory, and 1 body transfer within 1 query if no changes to body.

Although this can be simplified a bit:

• insert to history table using insert select (transferring new body app->db)

INSERT INTO PostsHistory (id_post, body)
SELECT p.id_post, p.body
FROM Posts p
WHERE id_post = ?postId
AND body != ?newBody

• if affected 0 rows, you are done
• if affected 1 row execute update on the Posts table (passign new body app->db again)

This would give you 1 body in memory, 2 body transfer within 2 queries if body changes. Or 1 body in memory, 1 body transfer within 1 query if no body changes.

Since you passed new body twice to db, you can wrap the two queries in a stored procedure, pulling it down to 1 body in memory and 1 body transfer within 1 query regardless of body changing.

Either way, if new and old body is different, db compared them twice (once in the insert select, secondly in the main table update).

Anyway, if you change your db structure a bit you can do something like this:

You might consider having history that contains all versions including the first one while the main table does not replicate the data/body column, so you would instead have something like this

Posts(pk(id_post), fk(id_user))
PostVersions(pk(id_post_version), unq(fk(id_post), version), body)

with example data:

Posts: id_post, id_user
#0           1,       1
#1           2,       1

PostVersions: id_post_version, id_post, version, body
#0                          1,       1,       1, "post 1 original"
#1                          2,       1,       2, "post 1 version2"
#2                          3,       1,       3, "post 1 version3"
#3                          4,       2,       1, "post 2 original"

insert new post operation becomes 2 insert queries:

INSERT INTO Posts (id_user) VALUES (?)
INSERT INTO PostVersions (id_post, version, body) VALUES (?lastInsertId, 1, ?body)

update post:

INSERT INTO PostVersions (id_post, version, body)
SELECT tmp.id_post, tmp.version + 1, ?newBody
FROM (
  SELECT id_post, version, body
  FROM PostVersions
  WHERE id_post = ?postId
  ORDER BY version DESC
  LIMIT 1
) as tmp
WHERE tmp.body != ?newBody

---

EDIT2: I have changed the above query because it had a flaw that would match an older version if new changes make the post contain the same body as it already had somewhere in the past.

---

Thats 1 body in app memory, 1 body transfer within 1 query regardless of body changing. But db compared bodies only once and you didnt need a stored procedure.

---

EDIT: sry the new body Is twice in the query, So it Is actually 2 body transfer within 1 query, but a SP can reduce it to 1 in 1. But still a single diff either way.

---

and "get the last version" query:

SELECT p.id_post, p.id_user, pv.version, pv.body
FROM Posts p
JOIN PostVersion pv
  ON pv.id_post = p.id_post
WHERE p.id_post = ?postId
ORDER BY version DESC
LIMIT 1

The unique index ensures (except for uniqueness) that both update and get operations are fast.

But now operation "get many posts' latest versions" gets a bit complicated, but we can easily solve this by adding latestVersion column to the Posts table and adding an after insert trigger on the versions table. Since we only insert version and never modify and when we insert it becomes the latestVersion, we can simply update Posts.latestVersion with NEW.version of the insert to PostsVersions. Get many last versions operation could then look like this:

SELECT p.id_post, p.id_user, pv.version, pv.body
FROM Posts p
JOIN PostVersion pv
  ON pv.id_post = p.id_post
  AND pv.version = p.latestVersion
WHERE p.id_post IN (?postIds)

Again the unique compound index helps a lot here. And of course the same simplification applies to the "get latest version of a single post" operation, but there it is not that much important.

A downside is that if you decide to use the PostVersions approach, you will have to migrate current data.

So after all it seems there are both pros and cons for both PostHistory table approach and PostVersions table approach and it will be up to you to decide what fits you best.

Lastly, one point I'd like to emphasize. INSERT SELECT is a powerful and (possibly) underestimated feature that allows conditional insertion (but one has to be smart about what to select for the insert:)).

PS: As for the hashing I think others have already mentioned enough about this and so I wasn't targeting that part here....