1

I have multiple databases (MySQL, all identical except data, can delete arbitrarily from any) across multiple machines which contain large quantities of sentences (~ 1e+11 per database, ~ 4e+12 in the whole system). What I want to do is delete all duplicates across these databases.

The first idea that came to mind was to hash every row and if a collision occurs compare the sentences and delete all but one of them if they are equal. This would be all nice and easy if it wasn't for the amount of data.

To come to my question: is there a way of doing this within a maximum of one week (although faster would be better), and do you have any tipps of how to implement this?

  • "~ 1e+11 per database, ~ 4e+12" - so there are approximately 40 databases? And are they all interchangable / can you delete from any of them arbitrarily? – Doc Brown Nov 18 '19 at 6:33
  • Have you considered resharding the data? That way you can rely on the database engine to deduplicate the data. – Kain0_0 Nov 18 '19 at 8:06
  • ERR_UNDEFINED: a reasonable amount of time – Dan Wilson Nov 18 '19 at 16:51
  • If I replace the word databases with the word files in the question it almost begs for the answer first external merge sort then deduplicate. – High Performance Mark Nov 18 '19 at 17:03
  • added: time contraints + info about deletion – Ingrim4 Nov 18 '19 at 21:06
1

(1) On every database in parallel: Calculate a hash (e.g. the md5-sum) of all sentences and store them in a new column with an index on it. As MySQL provides an SQL-Function, this can be done with an SQL-statement.

(2) While step (1) is running, write and test a program that roughly does the following:

  • For each database have an input buffer. Whenever empty, refill it from that database, reading the hashes in ascending order.

  • In every step peek the next hash from each buffer and take the lowest, thus traversing all hashes from all databases in consecutive order.

  • Have an output buffer for every database and write duplicates to it. Whenever full, delete the corresponding rows from that database

(3) Run the program.

0

The specific time that this is going to take is going to depend a lot on the database hardware, networking constraints, and the design of the database tables involved. I do think this is something that is feasible in the time frame you give though, with those caveats.

Hashing the sentences is a good start. Presumably you have some sort of primary key that allows you to retrieve the sentence. One thing here is to pick a hashing function that is very fast. A lot of the hash functions we encounter are designed for security use cases. You should use something else e.g. MD4 that is more appropriate for this kind of problem.

The other technique that can help you here is Bloom filters. If you size the filter appropriately, you should be able to narrow down to possible matches much more efficiently (both in time and space) than if you tried to build a gigantic hashtable or tree. One approach might be to build a bloom filter per database. I'm not sure if this would be any faster but you would know immediately which DBs the potential matches are.

One thing that may or may not be an issue: it's optimal to always keep the value in the earliest processed DB when a match is found because you cannot remove items from a Bloom filter. This first DB will not have any records deleted and may end up larger than the second. The same would be true then for the second and the third and so on and so forth. If you don't expect a large percentage of the records to be duplicated, this can probably be ignored.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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