6 ms·

What's it called when the primary key is also a "foreign" (but not really) key into the same table? Anyway just do that. Each Item has a "PrecededByItemId" valu

What's it called when the primary key is also a "foreign" (but not really) key into the same table? Anyway just do that. Each Item has a "PrecededByItemId" value. To insert X between A & B, just make X preceded by A and B preceded by X. Or probably better, go the other way (FollowedByItemId). It's the SQL version of a linked list. Efficient? Yes they're integers and an insert takes only two changes. Robust? Yes, infinite inserts possible. Elegant? Beats any of that complicated stuff in the article, unless I'm missing something. I suppose you could run out of integers but if your to-do list is that long, well...

grzm 9y ago
Would you elaborate on how to select data in the custom order efficiently? What you're describing can't be easily indexed, if I understand you correctly. The strategy outlined in the submission ensures minimal table rewrites on updates (insertion, reordering, deletion) as well as efficient retrieval.
- rdiddly 9y ago
  Well I think this achieves minimal rewrites, but you do lose a bit on indexing. You can't retrieve by numeric position index for example. But reproducing the order is just a matter of starting from the head (where PrecededById is null) or from any point and then repeatedly selecting the entry whose PrecededById = the current ID.
  - grzm 9y ago
    That's more than a bit on indexing. Following a linked list through repeated selections is not nearly as efficient as an index scan.
    - rdiddly 9y ago
      Yeah that's true. Oh well, fractions it is then!
- dzamo_norton 9y ago
  with recursive todo_list_sorted as ( select * from todo_list tl1 where prev_id is null union all select tl1.* from todo_list tl1 join todo_list_sorted tl2 on tl1.prev_id = tl2.id ) select * from todo_list_sorted
  - grzm 9y ago
    Yes, there are ways to do it. The question is how to do so efficiently. Recursive queries don't benefit from indexes as efficiently as, for example, the solution outlined in the submission.
gluxon 9y ago
There may be other reasons, but here's one. The solution with fractions supports ORDER BY syntax. With the self-referential foreign keys, you would have traverse through from the beginning with multiple queries for that behavior. It's also a lot harder to query results in order while specifying an offset.
- pabl0rg 9y ago
  Couldn't you just order by preceeded_by ? Offsets should work
  - deleted 9y ago
    [deleted]
  - wainstead 9y ago
    I think one of the first design choices you have to make is: can preceded_by be NULL? The first item in the list has to do something with preceded_by. As a general rule making columns NOT NULL is prefereable; here I declared it NOT NULL, and the first row must reference itself as a result: nworks=# create table todo (todo_id int primary key, task text, preceded_by int not null references todo (todo_id)); CREATE TABLE nworks=# insert into todo values(1, 'do homework', 1); INSERT 0 1 nworks=# insert into todo values(2, 'clean bedroom', 1); INSERT 0 1 nworks=# insert into todo values(3, 'walk the dog', 2); INSERT 0 1 nworks=# insert into todo values(4, 'call mom', 3); INSERT 0 1 nworks=# select * from todo; todo_id | task | preceded_by ---------+---------------+------------- 1 | do homework | 1 2 | clean bedroom | 1 3 | walk the dog | 2 4 | call mom | 3 (4 rows) nworks=# update todo set preceded_by = 1 where todo_id = 4; -- call your mother first, it's more important UPDATE 1 nworks=# select * from todo order by preceded_by; todo_id | task | preceded_by ---------+---------------+------------- 2 | clean bedroom | 1 1 | do homework | 1 4 | call mom | 1 3 | walk the dog | 2 (4 rows) I didn't do any operation to fix the sorting order once I updated item #4, so there's more work to do here. I don't think it's a practical solution.
  - 9y ago

grzm 9y ago

Would you elaborate on how to select data in the custom order efficiently? What you're describing can't be easily indexed, if I understand you correctly. The strategy outlined in the submission ensures minimal table rewrites on updates (insertion, reordering, deletion) as well as efficient retrieval.

rdiddly 9y ago
Well I think this achieves minimal rewrites, but you do lose a bit on indexing. You can't retrieve by numeric position index for example. But reproducing the order is just a matter of starting from the head (where PrecededById is null) or from any point and then repeatedly selecting the entry whose PrecededById = the current ID.
- grzm 9y ago
  That's more than a bit on indexing. Following a linked list through repeated selections is not nearly as efficient as an index scan.
  - rdiddly 9y ago
    Yeah that's true. Oh well, fractions it is then!
dzamo_norton 9y ago
with recursive todo_list_sorted as ( select * from todo_list tl1 where prev_id is null union all select tl1.* from todo_list tl1 join todo_list_sorted tl2 on tl1.prev_id = tl2.id ) select * from todo_list_sorted
- grzm 9y ago
  Yes, there are ways to do it. The question is how to do so efficiently. Recursive queries don't benefit from indexes as efficiently as, for example, the solution outlined in the submission.

gluxon 9y ago

There may be other reasons, but here's one. The solution with fractions supports ORDER BY syntax. With the self-referential foreign keys, you would have traverse through from the beginning with multiple queries for that behavior. It's also a lot harder to query results in order while specifying an offset.

pabl0rg 9y ago
Couldn't you just order by preceeded_by ? Offsets should work
- deleted 9y ago
  [deleted]
- wainstead 9y ago
  I think one of the first design choices you have to make is: can preceded_by be NULL? The first item in the list has to do something with preceded_by. As a general rule making columns NOT NULL is prefereable; here I declared it NOT NULL, and the first row must reference itself as a result: nworks=# create table todo (todo_id int primary key, task text, preceded_by int not null references todo (todo_id)); CREATE TABLE nworks=# insert into todo values(1, 'do homework', 1); INSERT 0 1 nworks=# insert into todo values(2, 'clean bedroom', 1); INSERT 0 1 nworks=# insert into todo values(3, 'walk the dog', 2); INSERT 0 1 nworks=# insert into todo values(4, 'call mom', 3); INSERT 0 1 nworks=# select * from todo; todo_id | task | preceded_by ---------+---------------+------------- 1 | do homework | 1 2 | clean bedroom | 1 3 | walk the dog | 2 4 | call mom | 3 (4 rows) nworks=# update todo set preceded_by = 1 where todo_id = 4; -- call your mother first, it's more important UPDATE 1 nworks=# select * from todo order by preceded_by; todo_id | task | preceded_by ---------+---------------+------------- 2 | clean bedroom | 1 1 | do homework | 1 4 | call mom | 1 3 | walk the dog | 2 (4 rows) I didn't do any operation to fix the sorting order once I updated item #4, so there's more work to do here. I don't think it's a practical solution.
- 9y ago