I am looking to store a sorted list inside a database. I want to perform the following operations efficiently.

  1. Insert(x) - Insert record x into the table
  2. Delete(x) - Delete record x from the table
  3. Before(x,n) - Return the 'n' records preceding the record x in the sorted list.
  4. After(x,n) - Return the 'n' records succeeding the record x in the sorted list.
  5. First(n) - Return the first 'n' records from the sorted list.
  6. Last(n) - Return the last 'n' records from the sorted list.
  7. Compare(x,y) - Given two records x and y from the table, find if x > y.

The simple method I could think of is to store some kind of a 'rank' attribute in the table and query by sorting on that attribute. But in this method inserting/modifying a record with a rank becomes a costly operation. Is there a better method?

Specifically, I am looking to implement the table using Amazon's SimpleDB. But a general answer for a relational database should also be helpful.

Update on load profile:

Since I am planning this for a web application, it depends on the number of users that use the app.

If there are 100k active users (super optimism :P), then my very approximate estimate per day would be

500k selects, 100k inserts and deletes, 500k updates

I would expect the table to grow up to 500k in total.

I am looking to optimize on the updates, insert and the Compare operations. The rank of the items will be constantly changing and I need to keep the table updated.

  • Elaborate a bit on your expected load profile. How many selects/inserts/updates per day? What operations do you want most to optimize for? How big do you expect the table to grow per day or get in total? Commented Sep 13, 2011 at 3:46
  • Is this for a player rankings board? Anyways, I've updated my answer below with feedback based on your projected load profile. Commented Sep 13, 2011 at 13:50
  • no it's not a player rankings board.
    – chitti
    Commented Sep 14, 2011 at 7:40
  • What approach did you end up using? Commented Oct 11, 2011 at 21:22
  • I'm not even sure at what's being asked here or what you don't need to do from the laundry list of things you need to do. Commented Mar 21, 2018 at 19:08

5 Answers 5


If rank isn't completely arbitrary but is instead derivable from some other property (e.g. name, player score, etc.) then take a good look at Joel's answer.

If it is an arbitrary property of your data, then that should be stored as a column in your table of records. Assuming Amazon's SimpleDB is similar to the typical RDBMS, you can then index this column and quickly satisfy all your above queries with the appropriate indexing strategy. This is normal for an RDBMS.

Given that you expect high insert and update activity, but also relatively high read activity, I recommend doing the following:

  • Cluster the table on the rank, especially if the vast majority of your queries are against rank. If not, or if choosing a clustering key is not available in SimpleDB, then just create an index with rank as the leading column. This would satisfy queries 3-6.
  • An index on the record first and then rank (or, in the SQL Server world, just record and INCLUDE-ing rank, or just record if you've clustered on rank) would satisfy query 7.
  • Operations 1 and 2 can be optimized by spacing out your data appropriately (i.e. setting the FILLFACTOR in SQL Server). This is especially important if you cluster on rank.
  • As you insert or update ranks, maintain as much of a gap between rank numbers as possible to minimize that possibility that you will need to re-rank an existing record to accommodate a rank insert or update. For example, if you rank your records in steps of 1000 you leave enough room for about half that many changes and inserts with minimal chance you'll need to re-rank a record not directly involved in those changes.
  • Every night re-rank all records to reset the rank gaps between them.
  • You can tune the frequency of the mass re-rankings as well as the rank gap size to accommodate your expected number of inserts or updates relative to the number of existing records. So if you have 100K records and expect your inserts and updates to be 10% of that, leave enough room for 10K new ranks and re-rank nightly.
  • Re-ranking 500K records is an expensive operation, but done once a day or week off-hours should be fine for a database like that. This off-hours mass re-ranking to maintain the rank gaps is what saves you having to re-rank many records for each rank update or insert during your normal and peak hours.

If you expect 100K+ reads on a 100K+ sized table I do not recommend using the linked list approach. It will not scale well to those sizes.

  • Ranks are modifiable. I am expecting the ranks to change constantly and new records being inserted constantly. I am worried about the case when I insert a new element with a rank then the ranks of all records below the new record in sort order need to changed. Isn't that a costly operation when I have thousands of records in my database?
    – chitti
    Commented Sep 13, 2011 at 1:16
  • @chitti - Ah, that is a concern. You could space out your rankings (e.g. 0, 1000, 2000, 3000, ...) and periodically re-rank all records as the rank gaps fill up. This will not scale if you expect much more than a few tens of thousands of records, though. Commented Sep 13, 2011 at 1:21
  • 1
    @chitti - This is kinda funny, actually. This is exactly the problem database engines deal with when indexing data, because they are ordering it and re-ordering it as data is added or changed. If you look up FILLFACTOR you will see it is basically meant to create that extra space for records in an index, just as the rank gaps I described create space for rank changes and insertions. Commented Sep 13, 2011 at 1:28
  • 2
    Thanks for the updated answer. The 'rank' is an arbitrary property of my data. I am almost convinced that a custom index column is what I require. Check out this SO link with a similar question. The top answer provides recommendations on how to handle such a rank column.
    – chitti
    Commented Sep 14, 2011 at 7:45
  • @chitti - The accepted answer to that SO question is great. It suggests the same approach I've detailed here, with the additional suggestion of using decimals instead of integers to greatly expand your flexibility in assigning and changing ranks. Great find. Commented Sep 14, 2011 at 15:20

I generally use the "rank" method you describe. Rather than mess around with updating rows when items needed to be reordered I've often been able to get away with deleting all the records in the list and re-inserting new items in the proper order. This method is clearly optimized for retrieval.

An alternative approach would be to model the records as a linked list by using a "predecessor" reflexive foreign key column on the table:

ID   setID   item       predecessor
---  ------  ------     ------------
1    1       Apple      null
2    1       Orange     1
3    2       Cucumber   null
4    1       Pear       2
5    1       Grape      4
6    2       Carrot     3

You can easily retrieve a list and add and remove items with little overhead, but getting the records out in the proper order will be tricky. Perhaps there's a clever way to do it in a single query, probably with lots of aliased table joins.

I use this latter approach often when I'm modeling a tree-style relationship (categories, folders, sets and subsets). I've generally had a recursive function of some sort to reconstruct the full tree in my application.

  • 2
    The linked list model is neat. To retrieve such a hierarchy in order in SQL Server you would use a recursive CTE. Commented Sep 13, 2011 at 3:32
  • Building that hierarchy would be pretty costly for a tall table, though. The advantage is that rank changes/inserts/etc can be made easily. Depending on chitti's expected load profile, this may actually be the best approach. Commented Sep 13, 2011 at 3:37
  • The linked list option looks like the best idea for all operations except Compare. Any idea how I would implement Compare without having to trace the path between the two elements being compared?
    – chitti
    Commented Sep 13, 2011 at 5:07
  • If you have the IDs of the items I think Compare() would be straightforward, unless I misunderstood what you meant by Compare(). When you said: "find if x > y" did you mean "find if x precedes y"? I can't see that being easy without a custom index or a stored procedure that would walk the list (or that interesting CTE feature mentioned by @Nick).
    – bpanulla
    Commented Sep 13, 2011 at 22:18
  • 5
    This type of solution also approximates a graph data model (en.wikipedia.org/wiki/Graph_theory). A storage system optimized for storing graph nodes and edges might be a better solution than a RDBMS. Triple- and Quad-stores and graph databases like Neo4J are pretty good at this.
    – bpanulla
    Commented Sep 13, 2011 at 22:25

I would think the thing to do is to store the property or properties that are used to calculate the rank and then build an index over them. Rather than trying to force the database to physically store the data in ranked order or using a manually managed linked list, why not let the database engine do what it was designed to do?

  • 3
    What if the 'properties that are used to calculate the rank' are arbitrary? Eg: A set of shopping cart entries that get reordered based on user's arbitrary actions.
    – chitti
    Commented Sep 14, 2011 at 7:48
  • When you say the rank is arbitrary, what do you mean? There has to be an algorithm that you use to calculate what the rank should be. For example: "based on shopping cart entries" - Based how? There must be something stored in the database that is the driver for the rank calculation. It may be a combination of several things, but these things must somehow be stored in the customer table or in tables related to the customer. If it is in the data then you can create a function that calculates it. If you can calculate it you can store it and index over it.
    – Joel Brown
    Commented Sep 14, 2011 at 11:11
  • Let's say that we need to maintain the order of items in a shopping cart and the order can be 'arbitrarily' changed by the user using a web ui. How would you store such a list of items in a database and how would you maintain the sorting order?
    – chitti
    Commented Sep 15, 2011 at 1:55
  • If I understand you correctly, by "arbitrarily changing" the order of items in a shopping cart you mean that the user can drag items up and down in a list and drop them where they want. I guess that strikes me as a little contrived. Why would users do that? If they could do it, would they do it a lot? Is using a simple sequence of items within a cart really that much of performance concern? It seems to me that a sequence number from one to the number of items in the cart + the FK to the order would give you the index you need. Just update the items when one gets dragged around.
    – Joel Brown
    Commented Sep 15, 2011 at 3:22
  • 4
    The shopping cart is just an example I gave to show that there are cases where the 'rank' can be arbitrary. May be that was not a great example. The netflix dvd queue can be a better example. Just for the sake of argument imagine a netflix queue with 100k items that can be arbitrarily reordered by the user and he does it every one minute. How would you design a database to store that ordered list of movies in this hypothetical application?
    – chitti
    Commented Sep 15, 2011 at 3:30

These are the limitations of a non-RDBMS like simpleDB. The features you require cannot be implemented on the DB side in simpleDB, they have to be implemented from the programming side/application.

For a RDBMS like SQL server, the features you require are rudimentary to the clustered index.

  • Insert(x) - Insert record x into the table > Simple insert.
  • Delete(x) - Delete record x from the table > Simple delete.
  • Before(x,n) - Return the 'n' records preceding the record x in the sorted list. > Select top n results where x less than value and order by clause.

  • After(x,n) - Return the 'n' records succeeding the record x in the sorted list. > Select top n results where x greater than value and order by clause.

  • First(n) - Return the first 'n' records from the sorted list. > Select top n results.

  • Last(n) - Return the last 'n' records from the sorted list. > Select top n results after order by desc.

  • Compare(x,y) - Given two records x and y from the table, find if x > y. > TSQL IF statement.
  • SimpleDB does provide automatic indexes, sorting and a basic query language. My problem will remain even if I choose a RDBMS. The problem is because the ranking of the data in my database change arbitrarily and they cannot be captured as a single property (unless I use a custom rank column) that can be indexed.
    – chitti
    Commented Sep 14, 2011 at 8:01

Here's what I used to re-rank my Postgres table after every insert:

CREATE OR REPLACE FUNCTION re_rank_list() RETURNS trigger AS $re_rank_list$
    temprow record;
    row_idx integer := 1;    
    FOR temprow IN
    SELECT * FROM your_schema.your_list WHERE list_id = NEW.list_id ORDER BY rank ASC
        UPDATE your_schema.your_list SET rank = row_idx * 100 WHERE id = temprow.id;
        row_idx := row_idx + 1;
$re_rank_list$ LANGUAGE plpgsql;

CREATE TRIGGER re_rank_list AFTER UPDATE ON your_schema.your_list_value
    WHEN (pg_trigger_depth() = 0)
    EXECUTE PROCEDURE re_rank_list();

For my use-case, performance is not a concern, but confidence that it'll never break or act oddly is important.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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