How to make a postgres function reorder rows representing a linked list?

Question

I have a table like this that represents a linked list. When comes_after column is null it means it's the first record in the linked list.

id      | comes_after
--------+------------
"one"   | null
"two"   | "one"
"three" | "two"
"four"  | "three"

How do I write a function using SQL or PLPGSQL to reorder the rows? The function function move_id_after (id_to_move string, after_id string) has 2 arguments, the id_to_move which is the id to move to a new position, and after_id which is the id to move that row after. If after_id is null it means to move it to the beginning of the list.

This is my attempt but it doesn't work, and it doesn't seem like the ideal way to be doing it. As shown in the example cases, I'd like to also be able to move a row to the very beginning of a list or to the very end, and handle the cases where nothing needs to change.

create function move_id_after (id_to_move string, after_id string) language plpgsql as $$
declare
  AFTER_id_to_move string;
  AFTER_after_id string;
  id_to_move_used_to_follow string;
begin
  select id from mytable where comes_after = id_to_move into AFTER_id_to_move;
  select id from mytable where comes_after = after_id into AFTER_after_id;
  update mytable set comes_after = id_to_move where id = AFTER_after_id;
  update mytable set comes_after = AFTER_after_id where id = id_to_move returning id into id_to_move_used_to_follow;
  update mytable set comes_after = id_to_move_used_to_follow where id = id_to_move_after;
end $$;

Here are examples of some cases of how the result should be.

Move a record to another position

select move_id_after("two", "three") should become:

id      | comes_after
--------+------------
"one"   | null
"three" | "one"
"two"   | "three"
"four"  | "two"

Move a record to a position it's already in

select move_id_after("three", "two") should have no change:

id      | comes_after
--------+------------
"one"   | null
"two"   | "one"
"three" | "two"
"four"  | "three"

Move the first record to last position

select move_id_after("one", "four") should become:

id      | comes_after
--------+------------
"two"   | null
"three" | "two"
"four"  | "three"
"one"   | "four"

Move the last record to first position

select move_id_after("four", null) should become:

id      | comes_after
--------+------------
"four"  | null
"one"   | "four"
"two"   | "one"
"three" | "two"

Answer 1

If you want to specify a order, then you have to use ORDER BY clause. Any other solution should not to work. Your design is not practical with bigger data. With your design, you have to calculate some value for order every time, and this calculation should be based on recursive call - it is good design for graph databases, and bad for relational.

Relation (table) is not matrix, there is not a begin, there is not a end. Example, when you want to search last record, you have to use recursive CTE

 -- searching last record in list
with recursive x as (select 0 l, id 
                       from mytable 
                      where comes_after is null 
                     union all 
                     select l + 1, mytable.id 
                       from x join mytable on x.id = mytable.comes_after) 
  select id 
    from x 
   order by l desc 
    limit 1;

I don't know what is your target, but relation database is bad tool for this.

It's maybe interesting school task, but it can be terrible in real life. It is going against relation databases principles.

More usual solution is using special numeric column that you can use for ORDER BY clause. Some like

CREATE SEQUENCE test_o START WITH 1;

CREATE TABLE test(id SERIAL, v varchar, o numeric DEFAULT nextval('test_o'));

-- insert at end
INSERT INTO test(v) VALUES('ahoj');
INSERT INTO test(v) VALUES('nazdar');
INSERT INTO test(v) VALUES('bazar');

-- sort data by o
SELECT * FROM test ORDER BY o;
INSERT INTO test(v, 

SELECT * FROM test ORDER BY o;
┌────┬────────┬───┐
│ id │   v    │ o │
╞════╪════════╪═══╡
│  1 │ ahoj   │ 1 │
│  2 │ nazdar │ 2 │
│  3 │ bazar  │ 3 │
└────┴────────┴───┘

Insert after id=2:

INSERT INTO test(v, o)
  SELECT 'HELLO', 
         (SELECT (o +  lead(o,1) OVER (ORDER BY o))/2 
            FROM test 
           WHERE o >= (SELECT o 
                         FROM test 
                        WHERE id = 2) 
           ORDER BY o 
           LIMIT 1);

postgres=# SELECT * FROM test ORDER BY o;
┌────┬──────────┬────────────────────┐
│ id │    v     │         o          │
╞════╪══════════╪════════════════════╡
│  1 │ ahoj     │                  1 │
│  2 │ nazdar   │                  2 │
│  6 │ HELLO    │ 2.5000000000000000 │
│  3 │ bazar    │                  3 │
└────┴──────────┴────────────────────┘
(4 rows)