SQLite Forum

How can I maintain a list in an arbitrary order?
Login

How can I maintain a list in an arbitrary order?

(1) By doug (doug9forester) on 2020-03-30 19:36:05 [source]

Given an arbitrarily ordered list of items b,q,t,z,a (obviously not in sort order), how can I insert a new item "p" after item "t", for example, and have a query return the ordered list b,q,t,p,z,a?

If I use a position integer, then all the positions after the inserted row need to be increased by one. Ugh.

The table below seems to capture the information. However, I can't figure out how to query to get it in the right order. My guess is I need a recursive CTE.

Can someone help me out here, please?

--drop table list;
create table list (row_id INTEGER PRIMARY KEY, item TEXT UNIQUE,
     prev INTEGER REFERENCES list(row_id) DEFERRABLE INITIALLY DEFERRED);
insert into list values(null,"b",0);
insert into list values(null,"q",(select last_insert_rowid()));
insert into list values(null,"t",(select last_insert_rowid()));
insert into list values(null,"z",(select last_insert_rowid()));
insert into list values(null,"a",(select last_insert_rowid()));
select * from list order by row_id;
row_id|item|prev
1|b|0
2|q|1
3|t|2
4|z|3
5|a|4
-- want order to be b,q,t,z,a

-- normal insert "p" before "t"
begin transaction;
insert into list values(null,"p",(select prev from list where item="t"));
update list set prev=(select last_insert_rowid()) where item="t";
commit transaction;
select * from list order by row_id;
row_id|item|prev
1|b|0
2|q|1
3|t|6
4|z|3
5|a|4
6|p|2
-- want order to be b,q,p,t,z,a

-- boundary insert row before first row ("b")
begin transaction;
insert into list values(null,"w",(select prev from list where item="b"));
update list set prev=(select last_insert_rowid()) where item="b";
commit transaction;
select * from list order by row_id;
row_id|item|prev
1|b|7
2|q|1
3|t|6
4|z|3
5|a|4
6|p|2
7|w|0
-- want order to be w,b,q,p,t,z,a

-- boundary insert new row at end "h"
insert into list values(null,"h",(select max(row_id) from list));
select * from list order by row_id;
row_id|item|prev
1|b|7
2|q|1
3|t|6
4|z|3
5|a|4
6|p|2
7|w|0
8|h|7-- want order to be w,b,q,p,t,z,a,h

(2) By Clemens Ladisch (cladisch) on 2020-03-30 20:03:18 in reply to 1 [link] [source]

Indeed:

WITH RECURSIVE ordered AS (
  SELECT *
  FROM list
  WHERE prev = 0

  UNION ALL

  SELECT list.*
  FROM list
  JOIN ordered ON list.prev = ordered.row_id
)
SELECT * FROM ordered;

This should have an index on prev.

(3) By Keith Medcalf (kmedcalf) on 2020-03-30 20:54:40 in reply to 1 [link] [source]

So, here are some examples in Python of how to "renumber" tables. This uses the rowid as the indicator of order and allows you to "open up" a row at a specific location by moving an existing row at that location and all following rows "up by one", and how to "renumber" a rowid table so that all the current record numbers are set to start at 1 and increment by 1. All this is done without having to rebalance the b-tree. I suppose you could use any UNIQUE index you liked for the rowid (ie, position) by why have extra indirection that you do not need? Unless, of course, you have "multiple ordered lists" in one table, in which case you would be better off with a without rowid table where the primary key is the (list_id, _rowid_) after which you just need to modify the below to ad a where list_id == :list_id everywhere to constrain the operation to one list_id ...

Getting the output in the "right order" is simply a matter of
select * from <table> order by _rowid_;


def OpenRowid(db, table, id, rowid='_rowid_'):

    # Check if we need to open up the rowid
    sql = 'select %s from %s where %s == ?' % (rowid, table, rowid)
    if db.execute(sql, (id,)).fetchone() is not None:

        db.beginimmediate()

        # Get rowid's to renumber
        sql = 'select %s, %s + 1 from %s where %s >= ? order by %s desc;' % (rowid, rowid, table, rowid, rowid)
        r = [(row[0], row[1]) for row in db.execute(sql, (id,)) if row[0] != row[1]]

        # Renumber all the rowid's that need renumbering
        sql = 'update %s set %s = ? where %s == ?;' % (table, rowid, rowid)
        for old, new in r:
            db.execute(sql, (new, old))

        db.commit()


def RenumberRowids(db, table, rowid='_rowid_'):
    db.beginimmediate()

    # Generate the SQL to get all the rowid > 0 rows that need renumberid
    sql = 'select %s, row_number() over (order by %s) from %s where %s > 0 order by %s;' % (rowid, rowid, table, rowid, rowid)
    r = [(row[0], row[1]) for row in db.execute(sql) if row[0] != row[1]]

    # Renumber all the rowid's that need renumbering which will compact the rowids > 0
    sql = 'update %s set %s = ? where %s == ?;' % (table, rowid, rowid)
    for old, new in r:
        db.execute(sql, (new, old))

    # Find out if there are any rowid's < 1 that we need to renumber
    sql = 'select coalesce(count(*), 0) from %s where %s < 1;' % (table, rowid)
    offset = db.execute(sql).fetchone()[0]
    if offset:

        # Get the rowid's that need to move to make way for the rows with rowid's < 1
        sql = 'select %s, %s + ? from %s where %s > 0 order by %s desc;' % (rowid, rowid, table, rowid, rowid)
        r = [(row[0], row[1]) for row in db.execute(sql, (offset,)) if row[0] != row[1]]

        # Renumber all the rowid's that need renumbering
        sql = 'update %s set %s = ? where %s = ?;' % (table, rowid, rowid)
        for old, new in r:
            db.execute(sql, (new, old))

        # Get the new rowid for all the rows with rowids < 1
        sql = 'select %s, row_number() over (order by %s) from %s where %s < 1 order by %s desc;' % (rowid, rowid, table, rowid, rowid)
        r = [(row[0], row[1]) for row in db.execute(sql) if row[0] != row[1]]

        # Renumber all the rowid's that need renumbering
        sql = 'update %s set %s = ? where %s = ?;' % (table, rowid, rowid)
        for old, new in r:
            db.execute(sql, (new, old))

    db.commit()

if __name__ == '__main__':
    import apsw
    db = apsw.Connection()
    db.execute('create table x(id integer primary key, v integer not null);')
    db.execute('insert into x select value*10, value from generate_series where start=1 and stop=10;')
    db.execute('insert into x select -(value-1)*10, -value from generate_series where start=1 and stop=10;')
    db.execute('delete from x where id=50;')
    db.execute('delete from x where id=-30;')
    for row in db.execute('select * from x;'):
        print(row)
    print()
    RenumberRowids(db, 'x', 'id')
    for row in db.execute('select * from x;'):
        print(row)
    print()
    OpenRowid(db, 'x', 3, 'id')
    OpenRowid(db, 'x', -4, 'id')
    for row in db.execute('select * from x;'):
        print(row)
    print()
    db.execute('insert into x values (3, 103);')
    db.execute('insert into x values (-4, -104);')
    for row in db.execute('select * from x;'):
        print(row)
    print()
    RenumberRowids(db, 'x', 'id')
    for row in db.execute('select * from x;'):
        print(row)
    print()

and here is another example that does the same thing using more direct SQL (ie, it is not programmatic but does place some more constraints against the validity of the table being renumbered.

def OpenRowid(db, table, rowid):
    if not db.execute('select _rowid_ from %s where _rowid_ == ?;' % (table,), (rowid,)).fetchone():
        db.execute(OpenRowid.sql % (table,table), (rowid,))

OpenRowid.sql =
'''
insert into %s (_rowid_)
     select _rowid_
       from %s
      where _rowid_ >= ?
   order by _rowid_ desc
on conflict (_rowid_) do update
        set _rowid_ = excluded._rowid_ + 1;
'''


def RenumberTable(db, table):
    db.execute(RenumberTable.sql % (table,table,table,table,table,table,table))

RenumberTable.sql =
'''
begin immediate;
drop table if exists temp.r;
create table temp.r
(
    old integer not null,
    new not null,
    primary key (old, new)
) without rowid;
-- close up all rowid > 0 gaps, renumber going up
insert into temp.r
     select _rowid_ as old,
            row_number() over (order by _rowid_) as new
       from %s
      where _rowid_ > 0;
insert into %s (_rowid_)
       select old
         from temp.r
        where old != new
     order by old
  on conflict (_rowid_) do update
          set _rowid_ = (select new from temp.r where old == excluded._rowid_);
-- make space for the rowid < 0 rows, renumber going down
delete from temp.r;
insert into temp.r
     select _rowid_ as old,
            row_number() over (order by _rowid_) + (select count(*) from %s where _rowid_ < 1) as new
       from %s
      where _rowid_ > 0;
insert into %s (_rowid_)
       select old
         from temp.r
        where old != new
     order by old desc
  on conflict (_rowid_) do update
          set _rowid_ = (select new from temp.r where old == excluded._rowid_);
-- set final row numbers for rowid < 0 rows, renumber going down
delete from temp.r;
insert into temp.r
     select _rowid_ as old,
            row_number() over (order by _rowid_) as new
       from %s
      where _rowid_ < 1;
insert into %s (_rowid_)
       select old
         from temp.r
     order by old desc
  on conflict (_rowid_) do update
          set _rowid_ = (select new from temp.r where old == excluded._rowid_);
drop table temp.r;
commit;
'''

(4) By Keith Medcalf (kmedcalf) on 2020-03-30 21:41:56 in reply to 3 [link] [source]

Oops, some errors in the second example:

def OpenRowid(db, table, rowid):
    if db.execute('select _rowid_ from %s where _rowid_ == ?;' % (table,), (rowid,)).fetchone() is not None:
        db.execute(OpenRowid.sql % (table,table), (rowid,))

OpenRowid.sql = '''
insert into %s (_rowid_)
     select _rowid_
       from %s
      where _rowid_ >= ?
   order by _rowid_ desc
on conflict (_rowid_) do update
        set _rowid_ = excluded._rowid_ + 1;
'''


def RenumberTable(db, table):
    db.execute(RenumberTable.sql % (table,table,table,table,table,table,table))

RenumberTable.sql = '''
begin immediate;
drop table if exists temp.r;
create table temp.r
(
    old integer not null,
    new not null,
    primary key (old, new)
) without rowid;
-- close up all rowid > 0 gaps, renumber going up
insert into temp.r
     select _rowid_ as old,
            row_number() over (order by _rowid_) as new
       from %s
      where _rowid_ > 0;
insert into %s (_rowid_)
       select old
         from temp.r
        where old != new
     order by old
  on conflict (_rowid_) do update
          set _rowid_ = (select new from temp.r where old == excluded._rowid_);
-- make space for the rowid < 0 rows, renumber going down
delete from temp.r;
insert into temp.r
     select _rowid_ as old,
            row_number() over (order by _rowid_) + (select count(*) from %s where _rowid_ < 1) as new
       from %s
      where _rowid_ > 0;
insert into %s (_rowid_)
       select old
         from temp.r
        where old != new
     order by old desc
  on conflict (_rowid_) do update
          set _rowid_ = (select new from temp.r where old == excluded._rowid_);
-- set final row numbers for rowid < 0 rows, renumber going down
delete from temp.r;
insert into temp.r
     select _rowid_ as old,
            row_number() over (order by _rowid_) as new
       from %s
      where _rowid_ < 1;
insert into %s (_rowid_)
       select old
         from temp.r
     order by old desc
  on conflict (_rowid_) do update
          set _rowid_ = (select new from temp.r where old == excluded._rowid_);
drop table temp.r;
commit;
'''

if __name__ == '__main__':
    import apsw
    db = apsw.Connection()
    db.execute('create table x(id integer primary key, v integer);')
    db.execute('insert into x select value*10, value from generate_series where start=1 and stop=10;')
    db.execute('insert into x select -(value-1)*10, -value from generate_series where start=1 and stop=10;')
    db.execute('delete from x where id=50;')
    db.execute('delete from x where id=-30;')
    for row in db.execute('select * from x;'):
        print(row)
    print()
    RenumberTable(db, 'x')
    for row in db.execute('select * from x;'):
        print(row)
    print()
    OpenRowid(db, 'x', 3)
    OpenRowid(db, 'x', -4)
    for row in db.execute('select * from x;'):
        print(row)
    print()
    db.execute('insert into x values (3, 103);')
    db.execute('insert into x values (-4, -104);')
    for row in db.execute('select * from x;'):
        print(row)
    print()
    RenumberTable(db, 'x')
    for row in db.execute('select * from x;'):
        print(row)
    print()

Now also includes sample test same in both.