Maintaining Order in GAE

In a previous post I alluded to problems I encountered with using GAE's object model. This is the follow up to that.

In my todo list app, a main feature was to make reordering your todo list a breeze. When I wrote it with mysql, I used the standard relational database pattern to store an ordered list: create a field SEQ in the items table which holds the a sequence number(integer) that represents the order of the item in the list. But this means for every reordering I do, I have to update all active items in the list. I figured since I am only going to have small lists, it shouldn't matter, and it worked fine with mysql. When I did a port of this to GAE, reordering became terribly slow. A friend of mind told me that this is just a characteristic of object databases. My solution was to create a list field in the parent object(list), which remaps the sequence numbers into the correct order for the items. This way, updating the order only took saving the list object. Of course, this approach is more complicated. There are a couple of other possible approaches:

  1. As my friend mentioned: do a link list in the database. Instead of a SEQ field you would have a NEXT field which points to the item that's next to this one. This would make small reorderings(of the type: you take one object and move it to a different place in the list), a constant time operation, in terms of number of updates(3 updates total).
  2. Make the SEQ field a float, which would allow you to insert a item in between 2 other items with only one update. But because of numerical precision issues, sooner or later you would have to relabel the whole list for the SEQ numbers to be not too close together, which would be triggered like a garbage collection operation would be.

My current approach I think is about on par with these 2 in terms of complexity. I like the linked list solution because it's more scalable, you can really reorder/maintain arbitrarily large lists without missing a beat. For my app though, I only need to handle small lists, so I have no reason to switch for now

blog comments powered by Disqus