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

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

  

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

  

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

  

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

  

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

2. Строки из базы, которые обновили свои значения в колонках из файла, обновить;  

3. Новые строки из файла, которых нет в базе добавить в базу.  

  

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

  

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

  

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

  

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

  

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

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

  

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. 

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

```
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;

```
  

Пишет 

 1. Загрузить данные в массив и отсортировать массив (если нужна сортировка?). Будет и быстрее, и меньше памяти  

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

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

  

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

  

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

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

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

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

  

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

```
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... | ... |

  

  

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