Как синхронизировать большие таблицы?

Question

[Василий Жуков]

Есть таблица в базе, либо почти пустая, либо из с примерно 2000000 строк.

Есть файл с «новой версией» этой таблицы с примерно 2000000 строк (размер примерно 100Mb). Т.е. первичный ключ там есть и по нему будет синхронизация.

Структуры таблиц одинаковые, первичный ключ всегда число, в остальных колонках числа и строки ограниченной длины (до 20 символов). Строки в файле не отсортированы по первичному ключу.

Синхронизация идет из файла в базу, т.е. стандартно нужно:

1. Строки из базы, которых нет в файле пометить как удаленные (есть колонка deleted);
2. Строки из базы, которые обновили свои значения в колонках из файла, обновить;
3. Новые строки из файла, которых нет в базе добавить в базу.

Нужно синхронизацию сделать как можно быстрее с наименьшим использованием памяти на Java.

Сейчас есть быстрое решение с использованием хеш-таблиц, но оно ест непомерно много памяти: HashMap, trovе и другие реализации смотрел. Т.е файл загружается в HashMap и дальше все просто.

Есть еще решение, которое ест мало памяти с использование FileHashMap, когда значения map сохраняются на диск, но оно очень долгое.

Нужно, чтобы было и быстро, и памяти ело не много, т.е. максимум около 150Mb (фактически, весь файл в память можно загрузить в массив байтов).

Какие еще есть варианты?

Comments

[Василий Жуков]

решение должно работать на базах: postgresql, mssql, oracle

Answer 1

[Василий Жуков]

Придумал такое решение:

1. загружаем файл в память в виде массива байт, где каждые K-байт — это строка таблицы.
2. сортируем этот массив алгоритмом сортировки, который не требует доп. памяти, т.е. сортирует на месте или использует logN памяти. На практике выбрал модифицированный (для сортировки строк по K-байт) quicksort из Arrays.sort, он же описан в статье «Engineering a Sort Function». Ест logN памяти, а работает мега быстро (2000000 массив сортирует за 250ms).
3. делаем запрос select id,a,b,c from mytable order by id (грузим не сразу все, а пачками, используя fetchSize).
4. сейчас будем бежать по первому отсортированную массиву из файла, это будет индекс i, и по строкам из запроса, это будет индекс j. Для простоты объяснения проще представить, что есть два отсортированных массива.
5. i = 0, j = 0
5.1 если A[i].id == B[j].id, то (если A[i] != B[j], добавляем B[j] в temp_update); i++, j++;
5.2 если A[i].id > B[j].id, то B[j] добавляем в temp_insert; j++;
5.3 если A[i].id < B[j].id, то A[i] добавляем в temp_delete; i++;
6. выполняем 3 запроса к этим временным таблицам. таблица в базе синхронизирована

Итого: память O(1), а работать будет так же быстро, как и с map.
Если файл насколько большой, например, миллиард записей, то вначале сортируем таблицу в файле используя mergesort, а дальше переходим к пункту п3.

Comments

[Василий Жуков]

поправка: память O(1) будет если не грузить таблицу из файла в память, а отсортировать ее на диске с помощью mergesort. Получается, можно хоть миллиардные таблицы так синхронизировать.

[vajadhava]

Да, пожалуй ваше решение то что нужно. Закрываю вопрос. :-D

[denver]

Пойдет :)

[ztxn]

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

Ваш алгоритм, по сути — классический merge join. Если бы речь шла только об оракле, я бы скептически отнесся бы к идее самостоятельной реализации собственного велосипеда, платформа, наверняка это сделает эффективнее. Слияние наборов выполнил бы одним запросом:

merge into dest_table t
   using (select coalesce(t.id,s.id)
                 ,decode(s.id,null,t.val1,s.val1) val1
                 ,decode(s.id,null,t.val2,s.val2) val2
                 ....
                 ,decode(s.id,null,t.valN,s.valN) valN
                 ,decode(s.id,null,1,0) deleted 
           from dest_table t
            full join src_tmp_table s on t.id = s.id
         ) s
   on (t.id = s.id)
   when matched then update
     set t.val1 = s.val1
         ,t.val2 = s.val2
         ...
         ,t.valN = s.valN
         ,t.deleted = s.deleted
  when not matched then insert values (
      s.id
      ,s.val1
      ,s.val2
      ...
      ,s.valN
      ,s.deleted
  )

Правда, памятуя о проблемах с фулл джойном в ранних версиях оракла, использовать full join поостерегся бы, использовал вместо него группировку объединения двух наборов.

[Василий Жуков]

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

[ztxn]

Понял, я пропустил, что вы сравниваете не только идентификаторы, но и сами данные. Возможно в этом действительно что-то есть.

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

[ztxn]

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

[Василий Жуков]

По регламенту раз в месяц, но на многих инсталляциях. Пользователи сильно жалуются, что операция выполняется слишком долго и им приходится постоянно ждать по 30 минут (в реале задача немного сложнее описанной). Сейчас все будет проиходить за 8 минут максимум при первом импорте и за 2-3 минуты при всех последующих обновлениях.

Answer 2

[denver]

Отчего не просто:

START TRANSACTION;
UPDATE mytable SET is_deleted=1;
INSERT INTO mytable (field1, field2, ...) VALUES
('field1', 'field2', ...), ('field1', 'field2', ...), ('field1', 'field2', ...), ...
ON DUPLICATE KEY UPDATE
is_deleted=0,
field1=VALUES(field1),
field2=VALUES(field2),
...
;
COMMIT;

Пишет

Comments

[Василий Жуков]

Надо будет запомнить такой способ, не знал.

Проблема в том, что весь запрос в память не поместится.

[denver]

А нет проблем разбить его на несколько.
Хотя я бы писал на диск и mysql mydatabase < updates.sql его, так дебажить будет быстрее.

[Василий Жуков]

Согласен, можно разбить, на MySql заработает, но нужно, чтобы работало в postgresql, mssql, oracle. В любом случае замерю время, спасибо за идею.

mysql mydatabase < updates.sql, а это съест, по скромным замерам, 400Mb запрос?

[denver]

А Точно, правильный вопрос :) В MySQL максимальный запрос ограничивается настройкой max_allowed_packet. Увеличить через клиент можно mysql --max_allowed_packet=32M или в конфиге сервера.
Да, INSERT… ON DUPLICATE KEY только в MySQL, в оракле MERGE, в постгре тоже можно что-то придумать. Но, конечно не универсально. Пишите уточнение ;)

Answer 3

[Arktos]

1. Загрузить данные в массив и отсортировать массив (если нужна сортировка?). Будет и быстрее, и меньше памяти
2. А зачем вообще грузить весь файл, а потом вести синхронизацию? Загрузили одну строчку, провели синхронизацию, загрузили вторую, снова провели. Если вам кажется, что это будет дольше работать, объясните тогда, как вы быстро синхронизируете таблицу БД с хеш-таблицей в памяти?

Comments

[Василий Жуков]

Загрузили одну строчку, провели синхронизацию. Как? Запрос в базу для каждой загруженной из файла строки? Получится 2000000 запросов. Долго.

С хеш-таблицами сейчас так: грузим весь файл в map. Потом просматриваем таблицу из базы по K элементов (один селект, который грузит в память не всю таблицу, а по K строк). Для каждой строки смотрим в map по id, удаляя из него просмотренный элемент. Если нету, то во временную таблицу temp_delete сбрасываем id строки, если есть и значения в колонках не равны, то строку из map сбрасываем во временную таблицу temp_update. Оставшиеся в map строки — новые, добавляем из во временную таблицу temp_insert. Потом выполняем три запроса:
1. update mytable set deleted=1 from temp_delete t on t.id=mytable.id
2. update mytable set a=t.a, b=t.b, c=t.c from temp_update t on t.id=mytable.id
3. insert into mytable (a,b,c) values (select a,b,c from temp_insert)

итого: 1 sql запрос к таблице + куча запросов к временным таблицам (но они все типа insert batch, и во временных таблицах нет никаких индексов, кроме pk, поэтому достигается 10000запросов/сек) + 3 последних запроса, которые тоже быстрые, так как индексы в mytable обновляются только 1 раз, по времени уходит где-то 5 минут.

[Arktos]

«Загрузили одну строчку, провели синхронизацию. Как? Запрос в базу для каждой загруженной из файла строки? Получится 2000000 запросов. Долго.»
2000000 быстрых запросов. Асимптотически сложность получается та же самая. Индекс в базе данных представляет собой хэш-таблицу. В вашем случае вы делаете 2000000 запросов к хэш-таблице, в предлагаемом мной случае то же 2000000 запросов к хэш-таблице, только к другой хэш-таблице и без использования ОП
Конечно это только асимптотически, а реально работа с БД медленней, чем с ОП, это задача СУБД устроить это как можно быстрее. Можно не поединично, а K, в результате будет 2000000 / K запросов, и поэкспериментировать с размером K.

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

[Василий Жуков]

1. Если грузить по одной строке из файла (или пачкой по K), то как узнать те строки из бд, которые нужно пометить как удаленные?

2. разброс id очень большой.

[Arktos]

1. Например, пометить deleted=1 для всех строчек, которые встретили в файле, а после прочтения файла инвертировать поле deleted для всех записей

[Василий Жуков]

Если так сделать, то в бд те, строки которые уже помечены как deleted и не присутствуют в файле, будут помечены как не deleted. Косяк.

[denver]

Вроде всё правильно Arktos сказал, только запутанно :) перед апдейтом пометим все в базе как удаленные, а записи из файла вставляем/апдейтим всегда с deleted=0.

[Arktos]

А еще можно создать temp таблицу из файла (insert по K элементов), а затем сделать три запроса на удаление, изменение и вставку, похожие на ваши, только с одной таблицой temp

[Василий Жуков]

1. Да, в Arktos варианте с deleted флагом так же можно сделать, согласен. Чую только проблемы со скоростью будут, ведь запрос на проставление всем строкам флага deleted по сути изменит почти все «хорошие» строки в таблице. В варианте с map «хорошие» строки не трогаются и по факту все последующие обновления происходят очень быстро.

2. С одной temp таблицей тоже отличная идея! Замерю время. Только все последующие обновления будут требовать вставки всех значений из файла во временную таблицу. В варианте с map, вставляются только реально те строки, которые нужно удалить/обновить/добавить.

Answer 4

[ztxn]

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

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

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

Answer 5

[Василий Жуков]

Итого, решения не подходят, косяк в массовом проставлении флага deleted всем записям. На 2000000 таблице, почти все значения не deleted, поэтому выставление флага меняет почти все строки, это занимает около 5 минут, а синхронизация еще даже не началась :) В решение с map, все бы уже закончилось.

Comments

[denver]

Категорично :) Я подозреваю что обновить 2 млн займет единицы секунд. Думаю обновляются еще куча индексов, куда входит deleted. А в таком случае лучше отключать индексирование, включать после последних изменений.

[Василий Жуков]

Взял postgresql. Индексов в таблице на колонке deleted нет. Просмотр 2 млн строк действительно занимает секунды. С update сложнее. Я нашел причину столь долгой работы update-запроса. После каждого update-запроса размер таблицы увеличивается, план запроса сильно ухудшается, время запроса сильно увеличивается. На таблице вначале (после ее оптимизации) update-запрос выполнился за 40сек, потом за 2 минуты, потом за 4.5 минуты, тут еще запускается autovacuum (автоматическая оптимизация таблицы), которая тормозит все запросы к таблице. Все последующие запросы выполнялись за 4.5 минуты, autovacuum работает, видимо.

Answer 6

[voilesik]

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

т.е. например если у вас есть таблица типа:

create table t_mytable (
  id integer,
  field1 type1,
  ....,
  CONSTRAINT pk_mytable PRIMARY KEY (id));

и есть какие-то значения:

1	value1	value...	...
2	value2	value...	...
3	value3	value...	...

вы загружаете в нее же данные из файла инвертируя ключ, например:

-3	valueC	value...	...
-1	valueA	value...	...
1	value1	value...	...
2	value2	value...	...
3	value3	value...	...

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