Как эффективно извлечь количество каждого элемента из огромного набора данных?

Question

Проблема заключается в следующем:

• Входные данные: все статьи из Википедии (33 ГБ текста)
  
• Вывод: Количество скипграмм каждого слова (n-грамм с максимальным пропуском k) из Википедии в файле SQLite.

Схема таблицы вывода:

CREATE TABLE [tokens] ([token] TEXT UNIQUE NOT NULL PRIMARY KEY, [count] INTEGER  NOT NULL

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

INSERT OR REPLACE INTO [tokens] VALUES (@token, COALESCE((SELECT count FROM [tokens] WHERE token=@token), 0) + 1)

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

Проблема в том, что оператор выбора SELECT count FROM [tokens] WHERE token=@token, который должен сканировать таблицу, значительно снижает производительность.

Лучший метод, который я нашел, заключается в следующем (я использую C #):

1. Создайте Dictionary<string,int> для подсчета токенов.

2. Добавляйте токены в этот словарь, пока он не станет слишком большим, чтобы поместиться в ОЗУ.

3. Вставить (не обновлять) токены из словаря во временную таблицу без индекса. Таблица имеет следующую схему:

   CREATE TABLE [temp] ([token] TEXT, [count] INTEGER)
   

4. Если есть еще токены, очистите словарь и перейдите к шагу 2.

5. Копирование токенов из временной таблицы в таблицу токенов:

   INSERT INTO [tokens] SELECT [token], SUM([count]) AS [count] FROM [temp] GROUP BY [token]
   

Этот метод занимает "всего лишь" 24 часа для обработки набора данных, но я считаю, что это не лучший подход, потому что шаг 5 занимает 22 из 24 часов.

Знаете ли вы альтернативный подход, который может решить эту проблему?

P.S. Мое приложение однопоточное, и я делаю вышеупомянутые вставки в пакетах (100000 на пакет) в рамках транзакции.

Answer 1

Я бы предложил создать другую таблицу с таким же определением, заполнить таблицу до определенного состояния, объединить результаты с основным, очистить таблицу и начать обработку следующего набора элементов.

Answer 2

Это звучит как хорошее место, чтобы использовать для меня «фильтр подсчета цветения».

Требуется два прохода над вашими данными, и это немного эвристично, но это должно быть быстро. Фильтры Блума позволяют устанавливать тесты на наличие и присутствие в постоянное время. Фильтр подсчета Блума подсчитывает, сколько из определенного значения было найдено, в отличие от обычного фильтра Блума, который отслеживает только наличие / отсутствие.

Answer 3

Если у вас есть много свободных концертов ....

Я предлагаю вам не считать токены по ходу, а просто добавить все токены в одну таблицу и создать индекс, который организует токены.

CREATE TABLE tokens (token TEXT);
CREATE INDEX tokens_token ON tokens (token ASC);

затем добавьте все токены по одному ...

INSERT INTO tokens VALUES ('Global Warming');
INSERT INTO tokens VALUES ('Global Cooling');

наконец выполнить SELECT ... GROUP BY

SELECT token, COUNT(0) token_count FROM tokens GROUP BY token

Answer 4

Я бы предложил добавить SET TRANSACTION ISOLATION READ UNCOMMITTED.Это означает, что, возможно, счетчик может быть немного не соответствующим, особенно в многопоточной среде, где несколько пытаются одновременно вставить / обновить.