Карманный 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 записей представляли собой справочник продуктов, остальные изображали операции купли/продажи. Табличка с результатами тестирования на нетбуке и телефоне (время в секундах), а также подробности реализации и выводы — под катом.

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

Поскольку наша база является 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 мне не родной.

Автор: epishman

Источник