How to pretend ordering records just like line numbers of an editor

Question

This is about storing commands in a database instead of a text file or spreadsheet. I am looking for a solution, which mimics the behavior of line numbers in a text editor.

E.g. Given the table below with the column "Order" as the primary key, when I delete the second row (Order = 2), I would end up with a gap in the order column (1, 3), which needs to be corrected to (1, 2)

| Order | Command      |     | Order | Command      |     | Order | Command      |
|-------|--------------|     |-------|--------------|     |-------|--------------|
|   1   | CAM - ON     | ==> |   1   | CAM - ON     | ==> |   1   | CAM - ON     |
|   2   | Turn left    |     |   3   | Take picture |     |   2   | Take picture |
|   3   | Take picture |                                                              

I have already experimented with triggers. Before the record gets deleted, a trigger updates the relevant order numbers of the other records. I have also triggers to deal with appending or inserting a new record "before" an existing one.

I know the physical order on disk is different and irrelevant. So, I just manipulate the "Order" column to mimic the behaviour of line numbers.

The same works fine with updating records. E.g. if I want to "move" the "Turn left" command to the first position, implementing a trigger before update to reorder the other records does the trick too. E.g. set the order of the "Turn left" command to 1 and the trigger updates the other records first:

| Order | Command      |     | Order | Command      |
|-------|--------------|     |-------|--------------|
|   1   | CAM - ON     | ==> |   2   | CAM - ON     |
|   2   | Turn left    |     |   1   | Turn left    |
|   3   | Take picture |     |   3   | Take picture |

However, this one introduces a problem. Deleting or inserting a record triggers a procedure, which updates records, which now triggers the update procedure. This seems to make things recursive and complicated.

I tried to disable and enable the update trigger from within the other trigger procedures, but (in postgresl) this requires altering the table, which is not allowed during a query..

My question is: Is there a more straight forward solution, which covers all four CRUD Operations? Perhaps involving other data types for the order column instead of integer or completely different techniques?

Answer 1

You don't really need a trigger to achieve this. Just make the primary key deferrable, and you can remove and renumber in a single statement:

create table data (order_no integer not null, command text);

alter table data 
   add constraint pk_data 
   primary key (order_no) 
   deferrable initially immediate;

To delete a row use this:

with removed_row as (
  delete from data
  where ord = 1
  returning ord
)
update data
  set order_no = order_no - 1
where order_no > (select order_no from removed_row);

To insert a new row in the middle you can use this:

with new_row as (
   insert into data values (3, 'Tilt up')
   returning order_no
)
update data
  set order_no = order_no + 1
where order_no >= (select order_no from new_row);

Moving a row can also be done that way:

To move a row down:

with to_move(old_no, new_no) as (
  values (5,2)
), move_row as (   
  update data
    set order_no = new_no
  from to_move
  where order_no = old_no
)  
update data
   set order_no = order_no + 1
from to_move
where order_no >= new_no
  and order_no < old_no
;

And to move a row up:

with to_move(old_no, new_no) as (
  values (2,4)
), move_row as (   
  update data
    set order_no = new_no
  from to_move
  where order_no = old_no
)
update data
   set order_no = order_no - 1
from to_move
where order_no > old_no
  and order_no <= new_no 
;

Answer 2

Don't bother with triggers: what you are looking for is a derived value, that you can compute on the fly when needed, using row_number(). Also, it is generally not a good practice to play around with the primary key of a table (which is what your order column looks to me).

select
    ord original_order,
    row_number() over(order by ord) real_order,
    command
from mytable

You can create a view to save yourself the effort of typing the window function repeatidly:

create view as 
select 
    ord original_order,
    row_number() over(order by ord) real_order
    command
from mytable

Note that order is not a wise choice for a column name, since it clashes with a reserved word. I renamed it to ord it the above queries.

Answer 3

Your data is not really a good match for a relational database - if it was me, and the number of commands is not too large, I'd just store it as a JSON or XML clob.

But if you must use relational storage, I think that having to update on the average half of all rows after each insert is not a good design.

I'd suggest not storing the actual number, but just have the ord column define a relative order. As @GMB already wrote, you can then use row_number to get your consecutive numbers starting with 1.

To insert new rows without having to renumber existing ones, leave "holes" in the numbering:

Let MIN and MAX be the minimum and maximum numbers you want to use in the ord column. Then the very first row you insert should get

ord = (MIN + MAX) / 2

To insert a new row between two existing rows with order numbers o1 and o2, use

ord = (o1 + o2) / 2

Depending on the number of rows and number of inserts/updates you expect, a collision (i.e. no space between o1 and o2) may occur, so you should also have a renumbering procedure for that case. E.g. if you insert already ordered items this will very quickly (after log(max - min) inserts).

Here's pseudocode to get the ord number for insertion after a given row with ord == o1:

let next = SELECT MIN(ord) FROM commands WHERE ord > :o1
if next IS NULL then
    if o1 == MAX     then panic_or_renumber
    if o1 == MAX - 1 then MAX
    else (o1 + MAX) / 2
else
    if next == o1 + 1 then panic_or_renumber
    else (o1 + next) / 2

(Note that (a + b) / 2 can overflow when using signed arithmetic. Choose your bounds accordingly or use safer arithmetic if you need huge numbers of rows).

Answer 4

My question was based on the assumption that a trigger cannot be disabled while a trigger procedure is executed.

While this is still true, this SO Question shows that you can actually use the pg_trigger_depth() function to check the trigger depth before a trigger procedure is called. This way, checking against trigger depth = 0 does the trick to prevent a trigger procedure from calling an other. E.g.

CREATE TRIGGER insert_commands_trigger BEFORE INSERT ON commands FOR EACH ROW WHEN (pg_trigger_depth() = 0) EXECUTE PROCEDURE insert_commands();

Going back to the idea of using triggers has the important advantage that neither user mistakes, nor application bugs cannot corrupt the database. Therefore, I would like to share my updated solution (using postgresql version 11.6), which successfully prevented all my attempts to create invalid data so far.

I have renamed "Order" to step as advised, but stick to the step number as primary key:

CREATE TABLE commands (
    step integer primary key NOT NULL DEFAULT 1 CONSTRAINT positive_order CHECK (step >= 0),
    command character varying
);
ALTER TABLE commands OWNER TO kagan;

CREATE OR REPLACE FUNCTION update_commands()
RETURNS TRIGGER AS $$
DECLARE max_step integer;
DECLARE rec RECORD;
BEGIN
    select max(step) into max_step from commands;
    if NEW.step is null then RAISE EXCEPTION 'step must have a value'; end if;
    if NEW.step < 1 then RAISE EXCEPTION 'step (%) must be >= 1', NEW.step; end if;
    if NEW.step > max_step then RAISE EXCEPTION 'step (%) must be <= max(step) (%)', NEW.step, max_step; end if;

    -- Temporarily, move the current record at the old position "out of the way"
    -- Don't forget the other columns
    UPDATE commands set step = 0, command = NEW.command where step = OLD.step;

    if NEW.step > OLD.step then
        FOR rec IN
            select step from commands
            where step > OLD.step and step <= NEW.step
            order by step ASC
        LOOP
            UPDATE commands set step =  step - 1 where step = rec.step;
        END LOOP;
    else
        FOR rec IN
            select step from commands
            where step >= NEW.step and step < OLD.step
            order by step DESC
        LOOP
            UPDATE commands set step =  step + 1 where step = rec.step;
        END LOOP;
    end if;

    -- Put the current row back to the new position
    UPDATE commands set step = NEW.step where step = 0;
    RETURN NULL;    -- DO NOT PROCEED 
END;
$$ language 'plpgsql';

CREATE OR REPLACE FUNCTION insert_commands()
RETURNS TRIGGER AS $$
DECLARE max_step integer;
DECLARE rec RECORD;
BEGIN
    if NEW.step < 1 then RAISE EXCEPTION 'step (%) must be >= 1)', NEW.step; end if;

    select max(step) into max_step from commands;
    if max_step is null then
        NEW.step = 1;
    elsif NEW.step > max_step + 1 then
        RAISE EXCEPTION 'step (%) must be <= max(step) + 1 (%)', NEW.step, max_step + 1;
    else
        FOR rec IN select step from commands where step >= NEW.step order by step DESC LOOP
            UPDATE commands set step =  step + 1 where step = rec.step;
        END LOOP;
    end if;
    RETURN NEW;
END;
$$ language 'plpgsql';

CREATE OR REPLACE FUNCTION delete_commands()
RETURNS TRIGGER AS $$
DECLARE rec RECORD;
BEGIN
        FOR rec IN select step from commands where step > OLD.step order by step ASC LOOP
            UPDATE commands set step =  step - 1 where step = rec.step;
        END LOOP;
    RETURN OLD;
END;
$$ language 'plpgsql';

CREATE TRIGGER insert_commands_trigger BEFORE INSERT ON commands FOR EACH ROW WHEN (pg_trigger_depth() = 0) EXECUTE PROCEDURE insert_commands();
CREATE TRIGGER delete_commands_trigger AFTER DELETE ON commands FOR EACH ROW WHEN (pg_trigger_depth() = 0) EXECUTE PROCEDURE delete_commands();
CREATE TRIGGER update_commands_trigger BEFORE UPDATE ON Commands FOR EACH ROW WHEN (pg_trigger_depth() = 0) EXECUTE PROCEDURE update_commands();

COPY commands (step, command) FROM stdin;
1   CAM - ON
2   Turn left
3   Take picture
\.