GUID-подобные первичные ключи в SQLite на Android

Интро

Каждая таблица в SQLite по умолчанию содержит приватный ключ на основе автоматически генерируемого 64-битного целого. Это эффективно и удобно в большинстве ситуаций. Неудобства начинаются, пожалуй, только в двух случаях:

• когда диапазона 64 бит не хватает (тогда стоит задуматься о целесообразности SQLite задаче)
• когда хранилище становится "распределенным"

Может показаться, что и второй задачи в комбинации с SQLite не должно возникать, но распределенность не всегда означает что-нибудь вроде BigData. Типичный пример (из-за чего лично мне и понадобилось исследование на эту тему) это приложение с возможностью синхронизации данных между устройствами. Это может быть как что-то небольшое, как записная книжка, так и более нагруженное, как история браузера. Проблемой тут становится не столько объем данных, сколько слияние нескольких баз. Очевидно, что целочисленные счетчики записей, начинающие отсчет с 1, неизбежно будут выдавать конфликтующие последовательности, а значит использовать их в качестве уникального идентификатора записи на нескольких устройствах уже нельзя. Можно заморочиться с разделением на поддиапазоны или "сдвиганием" айдишников записей перед их передачей, но это все кривые и хрупкие костыли. Никто так не делает, конечно же. Вместо этого каждое устройство присваивает своим записям что-нибудь вроде GUID-а – просто и надежно.

GUID в качестве первичного ключа

GUID это случайное "число", длиной в 128 бит. То есть в БД это будет 16 байт в виде BLOB-а, либо минимум 32 байта в виде строки. Определенный оверхед (особенно, если остальные столбцы небольшие) по сравнению с дефолтным ключом, который хранится очень эффективно: обычно там не 8 байт, а столько, сколько требует для представления значение ключа. Этот оверхед ради решения задачи мы готовы платить, но не хотим усугублять – поэтому конечно же предпочитаем хранение в бинарном виде, а не текстовой строкой.

Что ж, объявить столбец с блобом несложно, сделаем примитивную табличку:

CREATE TABLE records (id BLOB PRIMARY KEY, data CHARACTER);

Можно еще добавить WITHOUT ROWID в качестве спецификатора таблицы для оптимизации – чтобы SQLite не добавляла и не поддерживала неявный ключевой столбец.

Тему можно было бы закрывать, если бы не желание заставить БД самостоятельно генерировать айдишники, так же, как в случае с дефолтным целочисленным ключом. Что ж, если нет принципиального требования иметь настоящие GUID (которые не совсем просто рандомное число, а имеют несколько предопределенных бит), то это тоже легко:

CREATE TABLE records (id BLOB PRIMARY KEY DEFAULT (randomblob(16)), data CHARACTER);

На этом можно было бы вновь остановиться, если бы не перфекционизм. Забегая вперед, скажу, что даже с перфекционизмом тяжелой формы на этом и стоит остановиться, если вы не собираетесь вставлять в БД миллионы записей. А вот если может быть так, что собираетесь, то стоит обратить внимание, что длинное случайное число не очень хорошо подходит в качестве ключа по той причине, что его дороже индексировать: просто складывать записи одну за другой и надеяться на быстрый поиск уже не выйдет.

Проблема эта к счастью давно и успешно решена и решение адаптировано на многие БД. Вкратце там все просто: первые 6 байт идентификатора заменяются на timestamp. В результате записи создаются сразу (частично) упорядоченными, что сильно облегчает их индексацию. Вероятность коллизий при этом увеличивается, но незначительно. И снова история закончилась бы ровно на этом месте, если бы в Android-ном API SQLiteDatabase позволяла определять внешние функции, чтобы сгенерировать гуидоподобный BLOB. Можно конечно генерить их и в Java-коде и биндить ко всем запросам на вставку, но это неспортивно. Кроме того, могут быть другие причины не делать этого. Например необходимость держать "глобальные" идентификаторы отдельно от "локальных", генерируя их по мере необходимости при помощи триггера.

Ну хорошо, взять 6 байт от unix timestamp с грехом пополам можно так:

SELECT round((julianday('now') - 2440587.5) * 86400000) & 0xFFFFFFFFFFFF AS ts;

Результатом будет число. Например, такое: 1489877740453 – на момент написания статьи. Хорошие новости в том, что оно обычно будет неубывающим, и его можно считать средствами самой БД. Но дальше начинаются некоторые сложности. Дело в том, что в SQLite очень ограниченный набор функций для работы с BLOB: только обрезать (substr()) и склеить (||). И как заставить интерпретировать число в качестве строки байтов, непонятно. То есть можно конечно сделать CAST(... AS BLOB), но это не то: оно переведет число в строку, а потом возьмет байты полученной строки – то есть превратит 6 байт в 13. Даже если предварительно отформатировать в шестнадцатиричное представление, будет много – 12. Не катит.

Преобразование числа в BLOB

… в SQLite невозможно – ответит вам google и stackoverflow. Так-то оно, конечно, правда, но если очень хочется, то вообще-то можно. В Интернете мне ничего найти не удалось, и пришлось изобрести самому. Сразу скажу: это будет грязно :)

Итак, у нас есть склейка (||), значит, имея две байтовые строки – timestamp и случайную часть – мы могли бы получить COMB Джимми Нельсона:

SELECT ts_bytes || randomblob(10);

Искомые ts_bytes это всего лишь строка из 6 байт, представляющая целое число. Давайте еще раз взглянем на него: 1489877740453. Или 0x 01 5A E3 A2 2B A5. Если бы могли взять по отдельности каждый байт в виде BLOB-а, и склеить их вместе – даже в ручном режиме это всего (и всегда) 6 склеек. Что ж, попробуем разделить число на байты. Их числовые значения можно получить при помощи небольшой арифметики:

• первый: ts >> 40 == 1 (0x01)
• второй: (ts >> 32) % 256 == 90 (0x5A)
• третий: (ts >> 24) % 256 == 227 (0xE3)
• ...

Но, опять же, это пока не байты. Интерпретатор SQLite будет считать это просто числами:

SELECT typeof( (1489877740453 >> 24) % 256 );
integer

А нам нужен BLOB. BLOB из одного байта, представляющего полученное число. Явно мы это сделать не можем, но если бы у нас было что-то вроде таблицы – значений байта-то всего 256 штук. Тут мы вспоминаем о второй операции, доступной в SQLite и возвращающей байты – substr, которая по индексу возвращает подстроку букв или байт. Бинго! Захардкодим все значения байта в строку, где индексом само значение этого байт и будет. К счатью, можно записывать бинарный литерал при помощи синтаксиса вида x'DEADBEEF':

SELECT X'
000102030405060708090A0B0C0D0E0F
101112131415161718191A1B1C1D1E1F
202122232425262728292A2B2C2D2E2F
303132333435363738393A3B3C3D3E3F
404142434445464748494A4B4C4D4E4F
505152535455565758595A5B5C5D5E5F
606162636465666768696A6B6C6D6E6F
707172737475767778797A7B7C7D7E7F
808182838485868788898A8B8C8D8E8F
909192939495969798999A9B9C9D9E9F
A0A1A2A3A4A5A6A7A8A9AAABACADAEAF
B0B1B2B3B4B5B6B7B8B9BABBBCBDBEBF
C0C1C2C3C4C5C6C7C8C9CACBCCCDCECF
D0D1D2D3D4D5D6D7D8D9DADBDCDDDEDF
E0E1E2E3E4E5E6E7E8E9EAEBECEDEEEF
F0F1F2F3F4F5F6F7F8F9FAFBFCFDFEFF' as b;

Это слегка псевдокод, потому что переносить строки так нельзя, но так нагляднее, а в коде можно и в одну строку отформатировать. Зато теперь все, что осталось сделать, это "вырезать" нужный байт из таблицы и склеить с другими. Шесть раз:

SELECT
  substr(b, (ts >> 40)       + 1, 1) ||
  substr(b, (ts >> 32) % 256 + 1, 1) ||
  substr(b, (ts >> 24) % 256 + 1, 1) ||
  substr(b, (ts >> 16) % 256 + 1, 1) ||
  substr(b, (ts >>  8) % 256 + 1, 1) ||
  substr(b,  ts        % 256 + 1, 1) ||
  randomblob(10);

Псевдо-GUID в бинарной форме готов! На самом деле SQLite пока что будет считать получаенную строку байт "текстом", но CAST(... AS BLOB) сделает все, как надо. Вообще-то это даже обязательно, потому что иначе чтение из этого столбца будет возвращать не 16 байт, как ожидается, а 17 – с нулевым терминатором строки. Осталось подставить выражение в качестве значения столбца по умолчанию.

Автовставка идентификаторов

Просто запихнуть весь этот "поезд" внутрь DEFAULT(...) в определении столбца таблицы нельзя, потому что там должны быть только "простые" выражения, а нам нужны вложенные SELECT-ы, чтобы избежать копипасты и множественных вычислений одного и того же.

К счастью, в SQLite есть триггеры, с помощью которых можно модифицировать строки на лету при вставке. К сожалению, ни фаза BEFORE INSERT, ни AFTER INSERT не подходят для обслуживания PRIMARY KEY, т.к. для удовлетворения неявного условия NOT NULL значение столбца нужно обязательно указывать в изначальном запросе. К тому же, для таких триггеров UPDATE-выражение снова позволяет только примитивные выражения. Зато доступен тип триггеров INSTEAD OF INSERT, который как раз может создать новую запись на основе переданных значений с добавлением сгенерированного блоба. Есть с ним только одна особенность, не указанная в документации: триггер INSTEAD OF INSERT нельзя создать на таблицу. Можно только на VIEW.

В итоге схема выстраивается следующая:

• основная таблица явно используется только для чтения
• запросы на запись идут во VIEW-пустышку с триггером на вставку
• триггер генерирует BLOB и делает вставку в основную таблицу

CREATE TABLE records (id BLOB PRIMARY KEY, data CHARACTER) WITHOUT ROWID;

CREATE VIEW  fake AS SELECT NULL as ts, NULL as data;

CREATE TRIGGER auto_guids INSTEAD OF INSERT ON fake BEGIN
  INSERT INTO records(id, data) SELECT CAST(new_guid AS BLOB), NEW.data FROM (
    SELECT
      substr(b, (ts >> 40)       + 1, 1) ||
      substr(b, (ts >> 32) % 256 + 1, 1) ||
      substr(b, (ts >> 24) % 256 + 1, 1) ||
      substr(b, (ts >> 16) % 256 + 1, 1) ||
      substr(b, (ts >>  8) % 256 + 1, 1) ||
      substr(b,  ts        % 256 + 1, 1) ||
      randomblob(10) AS new_guid FROM (SELECT
        round((julianday('now') - 2440587.5) * 86400000) & 0xFFFFFFFFFFFF as ts,
        x'000102030405060708090A0B0C0D0E0F...' as b
      )
  );
END;

Читаем как обычно:

SELECT * FROM records;

А записываем так:

INSERT INTO fake (data) VALUES ('Hello COMBs!');

Можно было положить таблицу байт в отдельную VIEW ради удобочитаемости, но это несколько негативно сказывается на производительности. Также можно было оставить первичный ключ на целоцисленном счетчике, сделать столбец guid просто уникальным и написать триггер ON AFTER INSERT, которы бы "передобавлял" строку с новым guid, но, забегая чуть вперед, скажу, что это медленнее примерно на 30%. Кстати, самое время посмотреть на производительность.

Производительность

Очевидно, что склейка байтов вручную медленнее встроенной функции randomblob(). Выигрыш должен появиться на большом количестве вставок. Проведем замеры. Сравнивать будем "обычный" целочисленный ROWID, ключ на основе randomblob(16) и наши частично упорядоченные блобы (COMBs, как их назвали в вышеупомянутой статье).

Тестовый сценарий таков:

• три транзакции вставок по миллиону записей
• случайная выборка всех вставленных записей по id

Время записи замеряется как для каждой серии, так и внутри через каждые 20% записей. Тесты запускались в эмуляторе Android 6.0 (SQLite 3.8.10). Исходники тут.

На графике: время вставки каждой последующей порции из 200 тысяч записей. Эталон производительности, понятное дело, дефолтный целочисленный индекс (синяя линия). Его скорость не зависит от количества последовательных вставок. Желтная линия (COMBs) это наш пациент. Его скорость также практически постоянна, хотя и ниже на 55-59%. А красная линия это таблица с первичным ключом на randomblob(16). Видно, что, начиная всего на 11% медленнее INTEGER PRIMARY KEY, где-то после первого миллиона вставок ее накладные расходы на поддержание индекса превышают частично упорядоченные последовательности и продолжают расти, достигая 75% замедления к концу 3го миллиона.

На самом деле COMB можно сделать еще быстрее. Текущая проблема заключается в том, что с миллисекундной точностью временных отметок соседние строки выстраиваются в кластеры по 18-20 штук, где первые 6 байт (таймстамп) – одинаковые, частично возвращая проблему упорядочивания случайных байт. Если к таймстампу каким-то образом прибавлять порядковый номер добавляемой записи (хотя бы внутри транзакции), это снизит оверхед до 29-34% по сравнению с "INT" и даст выигрыш по сравнению с randomblob(16) уже после 500 тысяч записей.

Недостаток в том, что в простейшем случае порядковый номер нужно передавать из управляющего кода, а этого делать не хочется по условиям задачи. Кроме того, уже и так можно сделать выводы.

Выводы

SQLite сама по себе очень неплохо управляется с индексированием даже чего-то GUID-о-подобного.

Если предполагаемый объем данных не превышает хотя бы 500 тысяч записей, чистый randomblob() обладает вполне приемлемой производительностью. Я в своем текущем проекте поэтому скорее всего его и выберу.

Даже если записей будет много, но вставляются они редко или, тем более, в виде единичных записей, тип первичного ключа не будет играть вообще никакой роли в производительности. Одна только фиксация транзакции (в Android с дефолтными настройками БД) занимает порядка 20-50 миллисекунд. И в разы больше, если система IO поднагружена. Вставка записи внутри массовой транзакции, которая происходит за микросекунды, по сравнению с этим занимает ничтожное время при любом раскладе.

В SQLite можно превращать числа в BLOB – было бы желание :)

Автор: knuckles

Источник