Django ORM how to maintain non-automatic counter integrity on a large table?

Question

Lets assume I have the following table 'book' (with tens of millions of rows):

  id     shelf   position (on shelf)
   1        2        3
   2        1        1
   3        1        2
   4        2        2
   5        2        1
 ...      ...      ...

40000000 1 2543355

And I need to move book 2 to another shelf or totally remove it. Is there a good way to close the gap in positions that will open because of it? I know there is this way to do it, but it will be really bad for performance, won't it?

Book.objects.filter(shelf=self.shelf, position__gt=self.position).update(position=F('position')-1)

I am thinking about changing maximum position on the shelf to moving/deleting position. Is there a good way to do it with Django ORM?

Answer 1

A good way (performance-wise) to close the gap (book2 moved from shelf=1, position=1) will be this (move the last book on shelf to the opened position):

Book.objects.filter(shelf=1).order_by('-position')[0].update(position=1)

An index on (shelf, position) is also needed to maintain performance.

(Found this answer in a related question)

Answer 2

What you want to do is very similar to a leaderboard implementation in rdbms. This is a really good read for doing that.

Essentially, what you want to do (in sql) is:

UPDATE book SET position = position - 1 WHERE shelf = X and position > Y

Where X is the shelf you moved the book from, and Y is its former position on that shelf. SQL syntax may vary.

In that article there are also examples of doing an insert of position into an existing shelf where positions must increase to make room for the newly inserted book. The article goes on to explain how to best do these in batches as moving one at a time, and then updating N records per move can be quite costly especially if you are repositioning the same books in the same shelf repeatedly.

For example, if you have 100 books on shelf 1, and you move two of them in positions [22, 56], then the optimal solution would move each book from 23-55 by one position, and each book from position 56-100 by two positions. The naive approach would move everything from 23-100 by one position. Then move everything from 56-100 by one position again.