MYSQL Batch insert but assign unique personalized label

user_4599824 0
Viewed 118

I have a rather unique requirement that I have been trying to solve for weeks now. I have a solution but I don't think it's robust enough.

Problem

I need to generate unique personalized unique labels for items that I upload with a CSV file. These items can grow to billions over time and they expire usually after 60/90 days. So the more records I add over the time I will be erasing them too. Deleting is important because I want to make sure that I give a label with minimum length.

eg. Let's say I need to assign labels to following items.

department = 'A'
items = [ 1 => foo, 2 => bar, 3 => nik, 4 => mik, 5 => baz, 6 => nik, 7 => baz, 8 => baz, 9 => baz, 10 => naz]

department = 'B'
items = [ 1 => foo, 2 => bar, 3 => nik, 4 => mik, 5 => baz, 6 => nik, 7 => baz, 8 => baz, 9 => baz, 10 => naz]

After inserting these records I need the output to be as following.

departments

id name
1 A
2 B

items

id name label segment_value department_id
1 foo foo 0 1
2 bar bar 0 1
3 nik nik 0 1
4 mik mik 0 1
5 baz baz 0 1
6 nik nik1 1 1
7 baz baz1 1 1
8 baz baz2 2 1
9 baz baz3 3 1
11 foo foo 0 2
12 bar bar 0 2
13 nik nik 0 2
14 mik mik 0 2
15 baz baz 0 2
16 nik nik1 1 2
17 baz baz1 1 2
18 baz baz2 2 2
19 baz baz3 3 2
20 naz naz 0 2

The reason why I want the behaviour is because I need a way to reverse lookup an item with a param like this. A/baz3 should be able to map item 9 on the items table.

Current Solution

Right now I have a trigger which updates the label after inserting the record. I maintain an external counter and for each insert the trigger will use that information to update the label.

Limitations/Current Issues

I am inserting these items 100,000 records or 200,000 records per batch. So I want an efficient insert. Also I want the labels to have a minimum numeric values (It's better if I can reuse baz1 after it's erased in 60 days). Also my current trigger doesn't use a new segment_value for each department_id

CREATE TRIGGER insert_items
            BEFORE INSERT ON items
                FOR EACH ROW BEGIN
                   SET NEW.segment_value = ((SELECT IFNULL(MAX(segment_value), 0) from purl_links where segment_key = NEW.segment_key) + 1);
                   SET NEW.label = CONCAT(NEW.label,NEW.segment_value);

                END

I am looking for a decent solution which should help me avoid collision and be able to insert in batch and produce a label with minimum amount of numerics possible (by using available old slots if possible).

PS : I tried to abstract out my problem in the best way possible and I am looking for any help that I can get.

mysql-8.0 mysql algorithm
3 Answers

Instead of trying to do the numbering task as you load a batch, I suggest something like this:

  1. Load the batch into a temporary table.
  2. Have an extra column for the resulting string, plus perhaps some indexes.
  3. Run a query to UPDATE that table with some of the strings -- this might involve a LEFT JOIN between the temp table and the real table to see what is available and what is not.
  4. Run another query to update some more.

Somewhere around step 3, you might create another table that discovers if all the 1-digit suffixes are used up; store the results in another temp table. This tells you which prefixes need a 2-digit suffix.

There may be a dozen passes like this to get it all done, but it will be just a dozen queries, no triggers, no looping (hopefully), etc.

But, there is a problem... Updating 100K rows is terribly slow due to saving stuff for undo in case of a crash. So it might be better to loop through the 100K rows 1K at a time.

Are you expecting to have "billions" or rows in the table even after purging? If so, then the purge will be a significant problem. For that, I recommend PARTITION BY RANGE(TO_DAYS(...)); DROP PARTITION is a lot faster and less invasive than a huge DELETE. The partitions would be weekly or daily. Hopefully, the timing of the purge is not too strict, since some of the strings will linger past the deadline by hours, thereby block their reuse. More: http://mysql.rjweb.org/doc.php/partitionmaint

If you don't need to be too strict on "minimal length", but are willing to use "best effort". With this, you could, for example, see that a prefix is currently using 2-digit suffixes, the try a random number or something. If the random number fails once, try again in the next pass.

user_17668310

Another approach is to keep track of the numbers. After all, they seem to be quite regular. For example:

Suppose the prefix 'baz' has currently used 1 through 3. You have another table with

prefix start end num_digits
'naz'  1     3   1

Tomorrow you add 4 and 5. 1,5,1

Eventually you hit 9, 10, 11 and must expand to 2 digits: 1,11,2

Let's say you get to 1,76,2 and it is time to purge. so it becomes 4,76,2

Not it gets a little tricky: Should you reuse 1,2,3? or continue with 77, 78, etc? Well, you need to continue with 77...99 before going back to the start. It gets messy here. (I see a couple of choices.) Let digress into another part of the algorithm.

Since there are 100K+ items to work with, start by sorting the list to find out how many numbers are needed for each prefix. (Think COUNT(*) and GROUP BY)

Then iterate through the batch, one prefix at a time. This part of the algorithm might best be done with application code, not SQL. This lets you figure out which numbers to use, and makes each UPDATE a manageable size.

user_17668310

I would recommend that you simply keep adding random digits until you get something unique. After all doesn't matter whether baz9 shows up before baz1. And even if the name baz showed up hundreds of times, you'll on average only have to try 4 things before finding a new label that you can use. So it is fast in practice.

Sure, you sometimes wind up with an extra digit. But it is very rare that you'll need 2. And you avoid any complex (and therefore slow) logic that a perfect solution would have required.

(I've used this exact technique in the past on a similar problem where a lot of repeated names happened, and saw massive speed increases.)

user_5854110
Related