How to apply efficiently multiple position changes of a huge list in the database?

Question

I have a huge java list of simple objects, stored in the database, maintaining the position of the elements by a index column. I use hibernate but manage the list by myself since it's too big to be stored as a collection.

After some changes to the list are made (add, remove, move) I want to persist the changes in the database by manually updating the index columns and inserting new respectively removing elements by hibernate.

Now, (1) is there an efficient algorithm how to combine the list delta to as few as possible sql statements - or (2) do I have to record every change and apply it step by step?

Answer 1

You could try maintaining index changes for segments of the huge list. For instance, in a list of 1000 items, if you:

• insert new items at positions 99 and 199,
• move item 2 to position 6,
• and remove item 277,

you can do the following with HQL:

• delete item 277
• update item set index = 6 where index = 2
• update item set index = index-1 where index between 3 and 6 (and it's not previous item - watch for overlaps)
• update item set index = index+1 where index between 278 and 1000
• update item set index = index+2 where index between 199 and 276
• update item set index = index+1 where index between 99 and 198
• insert items 99 and 200

I'm not ready to work on details of the algorithm, will just say that you need to maintain a list of collection segments and offset for each segment.