Bert's Blog

Sequential SQL

Recently I wrote an interesting piece of sql using a cartesian product. The goal was to insert an item into the top-most position in a list given that some of the item positions are fixed. The table “list” is as follows:

|item|rank|fixed|
| a  | 1  |  1  |
| b  | 2  |  0  |
| c  | 3  |  0  |
| d  | 4  |  0  |

The idea is to insert the new item in the 0th position, and move every non-fixed item down. We can get part of the way there with a cartesian product of list and itself, filtering by rank and grouping by item:

select a.rank as oldrank, min(b.rank) as newrank
from list a, list b
where a.rank < b.rank 
group by a.item;

This gives the mapping oldrank/newrank, however we are missing a mapping for the last item in the list. This is fixed by extend “list b” using a union:

select a.rank as oldrank, min(b.rank) as newrank
from list a,
( select rank from list
  union 
  select max(rank) + 1 from list
) b
where a.rank < b.rank 
group by a.item;

Lastly, we can filter the lists by “fixed” which gives our update statement:

update list set rank = 
( select newrank from 
  ( select a.rank as oldrank, min(b.rank) as newrank
    from list a,
    ( select rank from list where fixed = 0
      union 
      select max(rank)+1 from list
    ) b
    where a.rank < b.rank
    and a.fixed = 0
    group by a.item
  ) c
  where oldrank = rank
) where fixed = 0;

N.B These examples were tested using MySQL. I originally tested the scripts using sqlite only to discover that they didn’t work! It appears that sqlite evaluates “list b” each time it updates an item, making our sequence non-sequential.