Карманный OLAP на Javascript и производительность IndexedDB

Здравствуй, Хабр!

Недавно я решил протестировать производительность Javascript на примере создания несложного WEB-приложения, умеющего строить сводные таблицы на основе слабо-структурированных данных. Повторить весь функционал Excel или взрослых OLAP-систем не предполагалось, но хотелось протестировать производительность Javascript вообще и IndexedDB в частности на различных десктопных и мобильных браузерах. Забегая вперед, скажу, что выполнив первый этап работы — построение сводной таблицы однопроходным алготитмом по хранилищу фактов (индексирование часто-используемых разрезов и кэширование вычисленных агрегатов отложено на будущее) — я был разочарован производительностью чтения из IndexedDB, удивлен тем, что мобильные браузеры практически не отстают от десктопных, и озадачен эпическим провалом моего любимого Firefox в одном из тестов. Всего было 2 теста с различными вариациями:

  • формирование сводной таблицы, где основа алгоритма — единственный цикл по курсору IndexedDB, работа с объектами Object, Array, Set, Map (извлечение по ключу, вставка, итерация), конкатенация строк и простая арифметика;
  • расшифровка (drillthrough) строки сводной таблицы с выводом результата в DOM, где основа алгоритма — многократное (в цикле) извлечение одной записи из IndexedDB по ключу, и последующий вывод результатов в таблицу html группами по 100 строк методом insertAdjacentHTML('beforeEnd', html)).

Тестирование проводилось на файле JSON, содержащем 20 тыс. фактов, из которых 9 записей представляли собой справочник продуктов, остальные изображали операции купли/продажи. Табличка с результатами тестирования на нетбуке и телефоне (время в секундах), а также подробности реализации и выводы — под катом.

Firefox_linux 64.0 Chromium_linux 71.0.3578.80 Falkon_linux QtWebEngine 5.9.5
1 Полный расчет 20 тыс. фактов — фильтр, группировка строк, вычисление агрегатов 12.31, 10.21, 10.69 4.76, 4.38, 4.43 5.08, 4.76, 4.73
2 Без фильтра, вычисляемых атрибутов и агрегатов — только группировка строк 8.08, 8.14, 8.15 3.4, 3.5, 3.48 3.39, 3.37, 3.42
3 Без фильтра, группировок и вычислений — «голый» цикл по курсору IndexedDB 7.83, 7.72, 7.71 3.36, 3.38, 3.44 3.23, 3.11, 3.17
4 Расшифровка (drillthrough) с выводом в таблицу html 20 тыс. строк 108 90.5 100
5 Drillthrough без вывода в DOM — «голый» цикл по массиву ключей, и извлечение записей по одной 11.57, 14.71, 11.52 18.62, 18.91, 18.27 18.01, 18.09, 18.11

Firefox_android 63.0.2 Chrome_android 71.0.3578.98 Edge_android 42.0.0.2804
Полный расчет 20 тыс. фактов на телефоне 13.58, 13.15, 13.67 5.89, 5.84, 5.91 6.48, 6.45, 6.51

Исходные данные


Поскольку наша база является NoSQL, cхема данных и связи между сущностями предварительно не описываются. На вход можно подать любой JSON-файл, содержащий массив объектов, где могут быть перемешаны элементы справочников, транзакции, строки документов и т.д. Связи устанавливаются в момент группировки строк (или вычисления формул) на основе совпадающих значений атрибутов, таким образом можно сказать, что используются текстовые человеко-читаемые ключи. Например, сведения о продукте и операции покупки/продажи будут представлены в базе фактов такими записями:

[
	{"product": "milk-2.5", "EAN-code": "4770148229477-3"},
	{"product": "petrol-95", "EAN-code": "74820123490016-3"},
	{"product": "fish-pollock", "EAN-code": "4640014465660-3"},
	{"operation": "purchase", "partner": "nalchik-moloko", "product": "milk-2.5", "price": 15.5, "quantity": 50},
	{"operation": "purchase", "partner": "lukoil", "product": "petrol-95", "price": 35, "quantity": 200},
	{"operation": "purchase", "partner": "china-fish", "product": "fish-pollock", "price": 90, "quantity": 100},
	{"operation": "sale", "partner": "ivanov-petr", "product": "milk-2.5", "price": 20.30, "quantity": 3.5},
	{"operation": "sale", "partner": "smith-john", "product": "petrol-95", "price": 42, "quantity": 30},
	{"operation": "sale", "partner": "ivanov-petr", "product": "fish-pollock", "price": 120, "quantity": 2}
]

Синтаксис формул


Используется синтаксис Javascript, и 3 дополнительных функции:

  • fact(columnname) — возвращает значение атрибута (в т.ч. вычисляемого) текущего факта;
  • row (columnname) — возвращает текущее (промежуточное) значение строки сводной таблицы, в которую попадает данный факт;
  • selectlast(columnname, where) — возвращает значение атрибута последнего факта из набора фактов, удовлетворяющих условию where.

Пример формулы для фильтра:

['purchase', 'sale'].includes(fact('operation'))

Пример вычисляемого атрибута факта:

"amount": "round(fact('price') * fact('quantity'), 2)"

Примеры формул для колонок сводной таблицы (агрегаты, пост-агрегатные вычисления, запросы к справочникам):

{
	"quantity-sum": "row('quantity-sum') + fact('quantity')",
	"amount-sum": "round(row('amount-sum') + fact('amount'), 2)",
	"quantity-avg": "round(row('quantity-sum') / row('count'), 2)",
	"price-max": "fact('price') > row('price-max') ? fact('price') : row('price-max')",
	"price-min": "row('price-min') == null || fact('price') < row('price-min') ? fact('price') : row('price-min')",
	"price-sum": "row('price-sum') + fact('price')",
	"price-avg": "round(row('price-sum') / row('count'), 2)",
	"price-avg-weight": "round(row('amount-sum') / row('quantity-sum'), 2)",
	"EAN-code": "selectlast('EAN-code', 'fact(\"product\") == row(\"product\")')"
}

Особенности алгоритма


Поскольку алгоритм у нас однопроходный — в каждый момент времени мы имеем один текущий факт и одну строку сводной таблицы, в которую данный факт попадает. Таким образом, используя функции fact() и row() можно вычислять простейшие агрегаты типа суммы, мин/макса, среднего, и т.д. Более сложные статистические функции, требующие сохранения в памяти всего массива значений, пока не готовы.

Сложнее было реализовать left join (функция selectlast()) для целей извлечени дополнительных атритутов из справочников (по сути из других фактов) в рамках единственного цикла по хранилищу фактов. Я сделал допущение, что количество записей справочников всегда будет на порядки меньше количества оперативных данных, и решил задачу следующим образом — одновременно с группировкой строк и вычислением агрегатов — в отдельную песочницу выбираются все справочники (то есть факты, у которых задан искомый атрибут). После окончания формирования строк сводной таблицы — вторым проходом по песочнице подтягиваем недостающие атрибуты в соответствующие колонки сводной таблицы. Таким образом тяжелый цикл у нас остается лишь один.

Последней оптимизацией было преобразование всех формул в функции JS на старте, чтобы избежать использование eval() в цикле.

Тестирование производительности


К моему удивлению, вставка 20 тыс. фактов в неиндексированную ObjectStore занимало около секунды, однако с извлечением даных наблюдаются существенные проблемы.

Низкая производительность в строке 4 понятна — вывод в DOM, да еще и в таблицу — прогнозируемо тяжелая операция, к тому же довольно бессмысленная на проде, так как нормально работать с такой таблицей все равно не получится.

Интерес вызывают строки 3 и 5, представляющие «голую» производительность выборки из IndexedDB. В данных тестах я закомментил весь алгоритм, оставив только операции с базой — в строке 3 использовался один большой курсор и итерация по нему, в строке 5 наоборот — итерация по массиву ключей (предварительно подготовленному), и извлечение записей по одной. Ключ целочисленный, автоинкрементный.

Вот фрагменты кода для тестов 3 и 5 соответственно:

// single cycle on facts
db.transaction('facts', 'readonly').objectStore('facts').openCursor(undefined, 'prev').onsuccess = (ev) => {
	let cur = ev.target.result;
	if (cur) {
		cfact = cur.value;
		;
		// next fact
		cur.continue();
	}
}

rowout(0);

function rowout(i) {
	if (i < ids.length) {
		db.transaction('facts', 'readonly').objectStore('facts').get(ids[i]).onsuccess = (ev) => {
			cfact = ev.target.result;
			;
			rowout(i+1);
		}
	}
}

Поскольку интерфейс IndexedDB асинхронный — в обоих случаях мы наблюдаем хвостовую рекурсию, которая обязана оптимизироваться движком (иначе бы давно упали от переполнения стека), однако причина столь эпических тормозов мне непонятна. Причем Firefox, проигравший во всех тестах, существенно выиграл в тесте на одиночные запросы, что вселяет надежду, что уж с запросами по индексу он точно справится.

Заключение


Мне стало грустно, и я не уверен, что буду продолжать эксперименты. Конечно, можно построить индексы и отказаться от фулскана, но суммировать агрегаты все-равно придется в цикле, а, как мы видим, выборка из курсора — самая дорогая операция. Возможно, стоит вообще отказаться от IndexedDB, хранить данные на диске в формате JSON (благо, парсинг занимает секунды), а алгоритм переписать на wasm. Или ждать имплементации Rust в браузеры (шутка).

Приложение доступно тут, файл с тестовыми данными тут.

Буду благодарен за советы и просто умные мысли, так как язык Javascript мне не родной.

PS
Старшие товарищи объяснили в чем дело. Все запросы к IndexedDB выполняются в отдельном потоке (воркере), и даже при обходе курсора — для каждой записи происходит межпоточный вызов, а это очень накладно, ведь к расходам на собственно колбек добавляются расходы на создание сообщения и копирование всех данных (сложные объекты передавать по ссылке Javascript не умеет). Таким образом — высокая производительность несовместима с асинхронным межпоточным интерфейсом. Надеюсь, браузеры со временем решат эту проблему.

PPSS
Продолжение 1: Проблема производительности решена путем организации блочного хранения данных.
Продолжение 2: Ускорились за счет многопоточный вычислений.
Поделиться публикацией

Похожие публикации

Комментарии 10

    +2
    в js (кроме сафари) нет оптимизации хвостовой рекурсии. но какой-нибудь промис, или таймаут, обрывают хвост, поэтому нет переполнения стека. попробуй все-таки не использовать рекурсию, возможно будет шустрее.
      0
      Ужас, преобразование рекурсии в цикл это же классика, ладно, попробую юзать синхронный интерфейс IndexedDB
      0
      Очень ожидаемая производительность у Firefox.
      SQLite — медленное хранилище. Точнее оно быстрое, пока у вас в нем совсем немного данных (до 2-3 к строк), а затем оно проседает. Абсолютно не подходит для конкурентных операций чтения/записи. Я в свое время пробовал работать с SQLite и полностью в нем разочаровался.
      Единственное место, где его можно применить, это база хранения настроек и конфигураций, если она читается нечасто и переписывается лишь изредка.
      IndexedDB подходит для «передержки» данных между подключениями к серверу, но не для постоянной работы. Рассматривать его всерьез неоправданно.
        0
        Кончится тем, что я решу хранить всю базу одним мега-объектом где угодно, хоть в единственной записи IndexedDB, при старте забирать в память, и там рассчитывать. И будет быстрее.
        +1
        >Или ждать имплементации Rust в браузеры (шутка).
        Вообще говоря, компиляция в wasm уже не новость, и она есть для очень многих языков. Rust не исключение. Довольно давно.
          0
          Да, я сейчас решу вопрос с хранением базы, и займусь wasm. Хотя конечно странновато писать на Rust, который заточен именно на безопасный нативный код, чтобы потом этот код выполнялся на виртуальной машине. Мне это напомнило идею писать на Java для виртуальной машины .NET.
          0

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


          Обработка данных в классических базах данных многопоточная. И причём задачи обработки массивов данных очень прекрасно распараллеливается.


          Думаю, что с вводом-выводом тоже есть проблемы, и не только у SQLite.

            0
            Я использовал именно IndexedDB, она имеет асинхронный интерфейс, и собственный поток исполнения (предполагаю что по технологии вебворкера), а поскольку у этих воркеров обмен с главным потоком Javascript только через сообщения, и все сообщения сериализуются перед отправкой — на тормоза собственно выборки накладываются еще тормоза сериализации, и на больших данных получаем фигню. Я сейчас перешел от хранения «по записям» к хранению одним большим объектом (тоже в IndexedDB), и уже получил 100-кратное ускорение расчета. Теперь приходится решать проблему аллокации памяти, и разделения большой базы на куски среднего размера. Допишу — отчитаюсь.
            PS
            Это конечно не извиняет разработчиков браузеров, ведь на производительность их встроенных баз жалуются все.
            +1
            Поскольку интерфейс IndexedDB асинхронный — в обоих случаях мы наблюдаем хвостовую рекурсию, которая обязана оптимизироваться движком (иначе бы давно упали от переполнения стека)

            если он (последний пример в статье) действительно асинхронный, т.е. onsuccess вызывается после завершения текущего куска кода js, то откуда возьмется переполнение стека?
              0
              Точно, там же внутри колбэк :)

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое