My problem is, that I have no idea how I could cleanly make an index (not a real Table index, just an indicator) for each table row representing the entries position while each position must be unique but inserting a new entry may not cause everything to change its positions.

Here is an example:

Let's assume we have a table products, where each product has clearly its product-id as primary key. Now I am making a catalog of all products and another categorized by anything. Now I certainly could take the product-id or the product name to sort the lists but I want some of them to appear earlier and some not so I am going to give them indexes.

My first solution would be:

Each product gets its own position index like product p-2151 => position 1, p-553 => position 2 etc. No problem so far until I insert a new product between p-2151 and p-553. Now I had to reposition all following products what is no good idea, because I would have to refresh the complete product-cache of my application to recognize it.
So this is definitely not the way to go.

Normally I have no problems with such almost trivial things but somehow I just don't get it here.

What would be the cleanest way to go here?

  • The first issue I take with this is "product-id as primary key" because that isn't really related ... I should write a full answer on this... – jcolebrand Jun 20 '12 at 21:12
  • @jcolebrand You are right, it is not related, feel free to edit if it annoys you. – Matmarbon Jun 20 '12 at 21:19
  • Oh it's not that it annoys me, it's that I see your entire premise as flawed, because you didn't actually state the business rules, like why you need re-indexable fields. Etc. – jcolebrand Jun 20 '12 at 22:19

No matter what solution you choose, you're going to have to "refresh your product cache" anyway, since cached information won't reflect your new product either. You should let the DBMS do its job and just query against the base table.

In terms of managing arbitrary (manually imposed) sequences, one solution to consider which allows for easy inserts with only periodic recalculation of the whole sequence is to use double instead of int for your sequence number.

When you insert a record between two existing records, set the sequence number of the new record to half way between the existing records. This can go on for a very long time before you have to break down and recalculate the whole sequence.

You could have a nightly/weekly/monthly process that recalculates all of your sequence numbers so that they use natural numbers again.

| improve this answer | |
  • Your second and third passages are good (although it is a sad, that sorting by double and storage of double values are both pretty much inefficient, what is why I avoid them where I can) but I don't understand the first. Normally I simply compare md5s of cache and database to avoid data transfer. That would cause very much traffic with my "solution" but not with yours, or am I wrong with that? – Matmarbon Jun 20 '12 at 21:05
  • @Matmarbon - It is true that refreshing a cache will increase workload, as will avoiding caching altogether. The point is that if you change your base data you will have to change your cache, whether the change is a little one (only a few rows changed) or a big one (every row changed). So whether you go the cached route or not depends on how frequently it needs to be refreshed vs. how often you read from it. – Joel Brown Jun 21 '12 at 10:58
  • Now I know what you mean but I compare the hashes of every row (completely->in chunks->each row) with the database, only changes are updated. This is because of a very very thin bottle-neck between my database and client. Anyway as you see your statement is not ever entirely true, it depends on the caching method. – Matmarbon Jun 21 '12 at 11:46

I found have another solution: Based on the idea of ArrayLists and corresponding LinkedLists in Java I am storing the front entry id as foreign key!

In some cases - as mine - this completely suffices but in others it could cause problems when loading a range of items. In this cases I would recommend either Joel Browns solution or multiplying the position ids by some value (e.g. 1000) to make space for inserting other entries in between.

| improve this answer | |
  • 1
    How does a linked list solve the sorting issue unless you are sorting after retrieving the data from the database or using some kind of recursive procedure to return the rows? It's a valid data model, but I think you should give some details as to how you solved the sorting problem using it. – Cade Roux Jun 20 '12 at 21:08
  • @Cade Roux Well, to answer your question: Not at all. I never said it should be sorted on the database, only for the output. – Matmarbon Jun 20 '12 at 21:27
  • OK. If it meets your requirements, that's good. Typically when I need ordering for entities stored in the DB I go ahead and let the DB sort them before I get them, because it simply saves a bunch of extra code to do the sorting. And for this, the linked list representation is not the best in the database. Maintenance of linked list is just as difficult in the database than an integer or float positioning system (assuming procs handle all the shifting or re-ordering to move things around). And you get sorting for minimal cost with no client overhead with most indexing strategies. – Cade Roux Jun 20 '12 at 22:02
  • @Cade Roux Yes and no, yes to normally I would recommend the float solution, no to integer and the maintenance statement. The maintenance could not be less than with this method. For example you only have to change the front-id of two elements (which means only their cache must be updated), to switch thousand products from the beginning of the list to the end or vice versa. As for the performance point, that is not my problem, the database bottle-neck is it, because each user has one keep-alive connection to it. – Matmarbon Jun 21 '12 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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