Постановка задачи

Пусть мы пишем систему слежения за НЛО. В SQLite-базе хранятся периоды наблюдения за воздушным пространством и отчёты о наблюдении НЛО. Интересовать нас будет среди прочего статистика по количеству наблюдаемых НЛО в каждый период.

Для этого понадобится выполнять запрос на поиск пересекающихся отрезков, для ускорения которого нужен специальный индекс.

Решение «в лоб»

Для хранения периодов наблюдения заведём таблицы observations и events, дату будем хранить как строку:

create table observations (
    id integer primary key,
    start text not null,
    end text not null
);
create table events (
    id integer primary key,
    start text not null,
    end text not null
);

Следующий очевидный запрос выдаст количество наблюдений НЛО за каждый период. Для удобства сравнения дата конвертируется в юлианский день, т.е. в число с плавающей точкой.

select
    o.id,
    count(e.id)
from
    observations o,
    events e
where
    julianday(o.start) < julianday(e.end)
    and julianday(o.end) > julianday(e.start)

Как видно по плану запроса, запрос проходит по всем записям из observations и по всем из events:

Стоит базе хоть немного подрасти (4000 записей в observations и 65000 записей в events), как этот запрос начинает выполняться очень медленно (по 3 минуты). Очевидно, нас не устраивает подобное положение вещей.

R*Tree-индексы

Создание индекса

В SQLite есть специальный тип индексов R * Tree предназначенный для ускорения запросов вида «попадает ли точка в заданный k-мерный отрезок?». На каждую проиндексированную таблицу создаётся виртуальная таблица с индексом, в которой хранятся записи с первичным ключом, равным rowid записи из основной таблицы и пары чисел, хранящие начальную и конечную координаты соответствующей размерности многомерного отрезка. При этом если 32-битного числа с плавающей точкой не хватает для точного представления координаты, то начальная координата округляется вниз, а конечная - вверх. Таким образом, интервал в индексе полностью включает в себя интервал исходной записи с небольшим запасом.

В нашем случае удобно будет хранить в индексе начало и конец интервала как юлианскую дату. Однако на момент написания этой статьи (17 сентября 2016) эта дата составляет 2457648.91398646, что приведёт к большой погрешности при составлении индекса. Поэтому при сохранении данных в индекс вычтем из даты какую-нибудь константу, близкую к сегодняшнему моменту. Например, 2450000 (9 октября 1995).

Создадим индексы:

create virtual table observations_index using rtree (id, start, end);
create virtual table events_index using rtree (id, start, end);

Обновление индекса

SQLite не обновляет RTree-индекс автоматически. Можно, конечно, заполнять таблицу вручную, но тут легко допустить ошибку и получить индекс, не синхронный с состоянием основной таблицы. Поэтому будем обновлять его по триггеру.

create trigger observations_insert_trigger
after insert on observations
begin
    insert into observations_index
        (id, start, end)
    values
        (new.id, julianday(new.start) - 2450000, julianday(new.end) - 2450000)
    ;
end;

create trigger observations_update_trigger
after update on observations
begin
    update observations_index
    set
        start = julianday(new.start) - 2450000,
        end = julianday(new.end) - 2450000
    where
        id = new.id
    ;
end;

create trigger observations_delete_trigger
after delete on observations
begin
    delete from observations_index
    where id = old.id
    ;
end;

Аналогичным образом создадим индексы для таблицы events.

Использование индекса

В запросе сначала будем фильтровать пересекающиеся интервалы по RTree-индексам, а затем уже уточнять по значениям из основных таблиц.

select
    o.id,
    (
        select
            count(e.id)
        from
            events e
            join events_index ei on (e.id = ei.id)
        where
            oi.start < ei.end
            and oi.end > ei.start
            and julianday(o.start) < julianday(e.end)
            and julianday(o.end) > julianday(e.start)
    )
from
    observations o
    join observations_index oi on (o.id = oi.id)

По плану запроса видно, что используется созданный нами индекс:

Выполняется такой запрос за 388 мс, что в пятьсот раз быстрее, чем запрос без индекса.