🐊

SQLite3のテーブルを順序付きにする試行

2024/04/03に公開

sqlite3

tech

動機

ノートアプリなどでメモをユーザの好きな順に並べられるようにしたいから。

参考

並べ替えできるデータをデータベースに保存する方法

いろいろな方法がみられたが、新規挿入や並び替えのたびに影響を受ける行すべてを更新したり、並び替え可能な回数に上限があるのは不安だったので、別の方法を採りたかった。

方法

テーブルの行で連結リストをつくる。

[0] <--- [1] <--- [2] ...

テーブル

連結リストを表現するには、

識別子
前（または後ろ）のアイテムはどれか

が必要。

今回は前のアイテムはどれか（= id）という情報を prev に保存し、これが NULL のものは先頭とすることにした。

CREATE TABLE IF NOT EXISTS list (
    id   INTEGER PRIMARY KEY,
    prev INTEGER
);

実装

今回の連結リストでは、以下のことを行う必要がある。

新規アイテムの挿入は、前に並べたいアイテムの id を指定して行う
- NULL なら先頭への挿入
- 指定された id のアイテムが存在しなければ挿入を失敗させる
アイテムの挿入時、後ろに並ぶアイテムの prev を自身の id に更新しなければならない
アイテムの削除時、後ろに並ぶアイテムの prev を削除前の自身の前のアイテム id へ更新しなければならない

これをデータベース側、アプリケーション側のどちらで実装するかの選択となるが、アプリケーション側のみで実装してしまうとデータベースを直接操作した際に順序の更新がされない事態となるため、データベース側で実装することにした。

これには SQLite3 にある「トリガー」という機能を使った。

トリガー

「トリガー」を使うとアイテムの挿入時、更新時、削除時の前、または後のタイミングで任意の操作を自動で実行させられるようになる。

まずは挿入後に後ろのアイテムの prev を更新するトリガーを作成した。

なお、タイミングが挿入後であるため、新規挿入済みのアイテムもテーブルに存在するので id IS NOT NEW.id の条件で操作対象から外す必要がある。

CREATE TRIGGER IF NOT EXISTS reorder_when_inserting
AFTER INSERT ON list
FOR EACH ROW
WHEN EXISTS (
         SELECT id
         FROM   list
         WHERE  prev IS NEW.prev AND
                id IS NOT NEW.id
         LIMIT  1
     )
BEGIN
    UPDATE list
    SET    prev = NEW.id
    WHERE  id IS (
        SELECT id
        FROM   list
        WHERE  prev IS NEW.prev AND
               id IS NOT NEW.id
        LIMIT  1
    );
END;

次は削除後、後ろのアイテムの prev にじぶんの prev をセットし直すようトリガーを作成した。

CREATE TRIGGER IF NOT EXISTS reorder_when_deleting
AFTER DELETE ON list
FOR EACH ROW
BEGIN
    UPDATE list
    SET    prev = OLD.prev
    WHERE  prev IS OLD.id;
END;

また、挿入時に指定された prev が指す id のアイテムが存在しない場合の失敗もトリガーで実装できた。

CREATE TRIGGER IF NOT EXISTS check_previous_element
BEFORE INSERT ON list
FOR EACH ROW
WHEN NEW.prev IS NOT NULL AND
     NOT EXISTS (
         SELECT id
         FROM   list
         WHERE  id IS NEW.prev
         LIMIT  1
     )
BEGIN
    SELECT RAISE(FAIL, 'Does not exists the previous element');
END;

ビュー

この prev の連鎖をもとに順序を再現するのはアプリケーションにまかせてもよかったが、その条件で抽出できるビューを作成できそうだったのでやってみた。

CREATE VIEW IF NOT EXISTS ordered_list (
    id,
    prev
)
AS WITH RECURSIVE indexing (
    id,
    prev,
    idx
)
AS (
    SELECT id,
           prev,
           0
    FROM   list
    WHERE  prev IS NULL

    UNION ALL

    SELECT list.id,
           list.prev,
           indexing.idx + 1
    FROM   indexing
    JOIN   list
    ON     list.prev IS indexing.id
)
SELECT   id, prev
FROM     indexing
ORDER BY idx
;

SQLite3 の再帰共通テーブルを使う。再帰共通テーブル indexing に prev の連鎖に従って番号 idx を振った行を抽出していき、それを idx でソートするビュー ordered_list を作成した。

流れとしては、

prev IS NULL ならば先頭のアイテムであるのでこれを抽出、残りを再帰処理で並べていく。

再帰処理では、その時点での indexing テーブルと list テーブルを JOIN する。このときテーブル同士のデカルト積が作られるので、ON を使い必要な行のみを抽出する。

例えば、list の内容が以下の場合、

id	prev
1	3
2	NULL
3	2

再帰処理 1 周目の indexing テーブルは次のようになっており、

id	prev	idx
2	NULL	0

このふたつを JOIN したデカルト積のテーブルは次のようになる。

indexing.id	indexing.prev	list.id	list.prev
2	NULL	1	3
2	NULL	2	NULL
2	NULL	3	2

prev を順に辿るため、この中から indexing.id IS list.prev にマッチする 3 行目が抽出され、indexing.idx の値を +1 して並び順を進めたものが indexing テーブルに入る。

再帰処理 2 周目の indexing テーブルは、

id	prev	idx
2	NULL	0
3	2	1

となっており、また再帰処理で list と JOIN されると、次のテーブルが作られる。

indexing.id	indexing.prev	indexing.idx	list.id	list.prev
2	NULL	0	1	3
2	NULL	0	2	NULL
2	NULL	0	3	2
3	2	1	1	3
3	2	1	2	NULL
3	2	1	3	2

この中から再び indexing.id IS list.prev にマッチする 3、4 行目が抽出され、追加済みでない 4 行目が idx を +1 されて indexing テーブルへ入る。

id	prev	idx
2	NULL	0
3	2	1
1	3	2

このテーブルのデータを idx の順に並べたものが ordered_list ビューとなる。

並び替え

アイテムの並び替えは、

対象のアイテムを削除
そのアイテムを目的のアイテムの後ろへ再び挿入

という手順を踏む。これならばトリガーの実行によって順序が自動的に整えられる。

結論

形にはなったが、やはりデータベースで行うことではないと思う。

検索性の問題もあるが、以下のようなテーブルで items にアプリケーション側の言語がもつ順序付きコレクションをそのままシリアル化して格納するのがいいかもしれないと思った。

CREATE TABLE IF NOT EXISTS items (
    id   INTEGER PRIMARY KEY,
    list BLOB
);

動機

参考

方法

テーブル

実装

トリガー

ビュー

並び替え

結論

Discussion