21

I want to represent the list "hi", "hello", "goodbye", "good day", "howdy" (with that order), in a SQL table:

pk | i | val
------------
1  | 0 | hi
0  | 2 | hello
2  | 3 | goodbye
3  | 4 | good day
5  | 6 | howdy

'pk' is the primary key column. Disregard its values.

'i' is the "index" that defines that order of the values in the 'val' column. It is only used to establish the order and the values are otherwise unimportant.

The problem I'm having is with inserting values into the list while maintaining the order. For example, if I want to insert "hey" and I want it to appear between "hello" and "goodbye", then I have to shift the 'i' values of "goodbye" and "good day" (but preferably not "howdy") to make room for the new entry.

So, is there a standard SQL pattern to do the shift operation, but only shift the elements that are necessary? (Note that a simple "UPDATE table SET i=i+1 WHERE i>=3" doesn't work, because it violates the uniqueness constraint on 'i', and also it updates the "howdy" row unnecessarily.)

Or, is there a better way to represent the ordered list? I suppose you could make 'i' a floating point value and choose values between, but then you have to have a separate rebalancing operation when no such value exists.

Or, is there some standard algorithm for generating string values between arbitrary other strings, if I were to make 'i' a varchar?

Or should I just represent it as a linked list? I was avoiding that because I'd like to also be able to do a SELECT .. ORDER BY to get all the elements in order.

Donal Fellows
  • 133,037
  • 18
  • 149
  • 215
Travis
  • 2,961
  • 4
  • 22
  • 29
  • 1
    possible duplicate of [Update a list of things without hitting every entry](http://stackoverflow.com/questions/2824428/update-a-list-of-things-without-hitting-every-entry) – Michael Mrozek May 30 '10 at 21:50
  • 2
    BTW: Your Comment *"UPDATE table SET i=i+1 WHERE i>=3" doesn't work, because it violates the uniqueness constraint on 'i'* definitely doesn't hold true in SQL Server. The Constraints are checked at the end. What RDBMS are you using? – Martin Smith May 30 '10 at 22:33

4 Answers4

6

As i read your post, I kept thinking 'linked list' and at the end, I still think that's the way to go.

If you are using Oracle, and the linked list is a separate table (or even the same table with a self referencing id - which i would avoid) then you can use a CONNECT BY query and the pseudo-column LEVEL to determine sort order.

Tom H
  • 46,766
  • 14
  • 87
  • 128
Randy
  • 16,480
  • 1
  • 37
  • 55
  • 3
    btw - this reminds me of the good old days when you needed to renumber your BASIC programs... that was usually done as a seperate command/effort whenever you ran out of numbers in between (you would count by 10's basically in the beginning just in case...) – Randy May 30 '10 at 21:55
  • 1
    As long as you can use your application to figure out the sort order, a simple NextNode column that is either NULL or points to the next entry will get you what you want. You won't be able to take advantage of ORDER BY but the data is there. INSERTS are as simple as modifying the NextNode column of the row that used to point to the one you want to be after your new entry. – colithium May 31 '10 at 03:38
3

If you don't use numbers, but Strings, you may have a table: 

pk | i | val
------------
1  | a0 | hi
0  | a2 | hello
2  | a3 | goodbye
3  | b  | good day
5  | b1 | howdy

You may insert a4 between a3 and b, a21 between a2 and a3, a1 between a0 and a2 and so on. You would need a clever function, to generate an i for new value v between p and n, and the index can become longer and longer, or you need a big rebalancing from time to time.

Another approach could be, to implement a (double-)linked-list in the table, where you don't save indexes, but links to previous and next, which would mean, that you normally have to update 1-2 elements: 

pk | prev | val
------------
1  |   0  | hi
0  |   1  | hello
2  |   0  | goodbye
3  |   2  | good day
5  |   3  | howdy

hey between hello & goodbye:

hey get's pk 6, 

pk | prev | val
------------
1  |   0  | hi
0  |   1  | hello 
6  |   0  | hi <- ins
2  |   6  | goodbye <- upd
3  |   2  | good day
5  |   3  | howdy

the previous element would be hello with pk=0, and goodbye, which linked to hello by now has to link to hey in future.

But I don't know, if it is possible to find a 'order by' mechanism for many db-implementations.

ebruchez
  • 7,760
  • 6
  • 29
  • 41
user unknown
  • 35,537
  • 11
  • 75
  • 121
  • Using strings is terrifying (but rather clever). It might even be fast; with an index on your i column, ordered queries should be cheap, and may give advantages over the linked-list approach due to data locality. – David Given Mar 10 '16 at 13:44
3

You can easily achieve this by using a cascading trigger that updates any 'index' entry equal to the new one on the insert/update operation to the index value +1. This will cascade through all rows until the first gap stops the cascade - see the second example in this blog entry for a PostgreSQL implementation.

This approach should work independent of the RDBMS used, provided it offers support for triggers to fire before an update/insert. It basically does what you'd do if you implemented your desired behavior in code (increase all following index values until you encounter a gap), but in a simpler and more effective way.

Alternatively, if you can live with a restriction to SQL Server, check the hierarchyid type. While mainly geared at defining nested hierarchies, you can use it for flat ordering as well. It somewhat resembles your approach using floats, as it allows insertion between two positions by assigning fractional values, thus avoiding the need to update other entries.

Henrik Opel
  • 19,341
  • 1
  • 48
  • 64
  • 1
    I'm using SQLite, which apparently doesn't support cascading/recursive triggers (although it does support 'before' triggers). – Travis May 30 '10 at 23:38
  • 2
    @Travis: It seems like they added support for recursive triggers starting with version 3.6.18, but you have to explicitly turn it on: http://www.sqlite.org/pragma.html#pragma_recursive_triggers - I'm not sure though if the 'cascade' in your case counts as recursive, as it should never affect the inserted/updated row itself, but always a different row, so it might be worth a try anyway. – Henrik Opel May 31 '10 at 09:09
  • 1
    Thanks, didn't see that. However, there's a compiled-in upper limit on the recursion depth (1000 by default), and I don't know whether it can handle very high values, which could be a problem for me. What I finally decided to do was remove the uniqueness constraint on 'i' and for now just use the "i=i+1 WHERE i>=new_i" approach. I'll revisit this if updating the extra i values unnecessarily actually becomes a performance problem. – Travis May 31 '10 at 15:44
0

Since I had a similar problem, here is a very simple solution:

Make your i column floats, but insert integer values for the initial data:

pk | i   | val
------------
1  | 0.0 | hi
0  | 2.0 | hello
2  | 3.0 | goodbye
3  | 4.0 | good day
5  | 6.0 | howdy

Then, if you want to insert something in between, just compute a float value in the middle between the two surrounding values:

pk | i   | val
------------
1  | 0.0 | hi
0  | 2.0 | hello
2  | 3.0 | goodbye
3  | 4.0 | good day
5  | 6.0 | howdy
6  | 2.5 | hey

This way the number of inserts between the same two values is limited to the resolution of float values but for almost all cases that should be more than sufficient.

sonovice
  • 813
  • 2
  • 13
  • 27