3

Имеется две группы одноколоночных таблиц. Пример таблицы (по структуре все они одинаковы):

CREATE TABLE IF NOT EXISTS `member_lst_%1` (
    `user_id` BIGINT UNSIGNED NOT NULL
    , PRIMARY KEY(`user_id`)
)

В наименовании каждой таблицы содержится числовой идентификатор. В примере он указан как %1. Это просто число, например, "666", но уникальное для каждой таблицы.

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

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

Важное замечание: одинаковые user_id должны быть найдены не между таблицами одной группы, а именно между двумя группами. То есть, если некий user_id присутствует хотя бы в одной таблице группы, то считается, что он присутствует во всей группе. Этот момент исключает возможность последовательного перебора таблиц через INNER JOIN. Получается, необходимо сначала создать список всех user_id одной группы, потом второй группы и лишь за тем уже сравнивать эти два огромных списка.

Возможно ли как-то иначе решить эту задачу?

Update

select min(user_id),max(user_id),count(1) from member_lst_100475993

min(user_id)  max(user_id)  count(1)
4784          361583895     31746

select count(1) from ( select min(user_id) start,max(user_id) stop from( select user_id,@i:=@i+1,@grp:=if(@i=user_id,@grp,@grp+1) grp from member_lst_100475993,(select @i:=0,@grp:=0) A order by user_id ) G group by grp ) T

count(1)
31746
17
  • 1
    Реляционные БД один из самых неподходящих инструментов для решения подобных задач. да еще с такой структурой. Я не представляю сколько времени у mysql уйдет что бы смержить 100 таблиц по миллиону записей. При том, что грамотно представленные данные в виде интервалов и/или использующие битовые массивы отработают в тысячи раз быстрее
    – Mike
    22 апр 2016 в 17:14
  • Мыши плакали, кололись... :)) Может быть как-то интервально заносить идентификаторы в отдельную таблицу... Что-то вроде, что с такого-то по такой-то номера идентификаторы принадлежат таким-то группам таблиц. Либо действительно отказываться от хранения в БД и переходить на иное.
    – user177227
    22 апр 2016 в 17:36
  • @Mike , подскажите, пожалуйста, может, название алгоритма, по которому можно было бы реализовать эту задачу. Просто, чувствую, что с БД мне так вот интервально не сделать.
    – user177227
    22 апр 2016 в 17:42
  • 1
    Я названий не знаю, я обычно сам придумываю алгоритмы. Но пока ничего конкретного сказать не могу. Тут надо понимать не одну задачу, а все задачи стоящие перед такой системой. интервалы вещь неплохая, особенно если они крупные. Но работать с ними тяжело, особенно обновлять данные, склеивая или разбивая интервалы при добавлении/удалении. Может было бы проще оставить ID по одному, но рядом хранить битовое поле, в котором отмечено в какие группы оно входит. bigint умещает 64 группы. Но такое поле позволяет решить задачу "каким группам принадлежит ID", но не позволяет "Какие ID входят в группу"
    – Mike
    22 апр 2016 в 18:20
  • Ну вернее "Какие ID входят" можно и по битовой маске узнать, но индексы работать не будут, только полным перебором таблицы
    – Mike
    22 апр 2016 в 18:21

1 ответ 1

1

Решил пойти путём, идею которого @Mike озвучил в своём последнем комментарии к данному вопросу (за что ему большое спасибо).

Выяснение того, какие и сколько строк являются одинаковыми между двумя таблицами производится за весьма короткое время (от силы несколько секунд даже в самых тяжёлых случаях, когда обе таблицы имеют огромный размер по нескольку миллионов позиций каждая). Однако самих таблиц много и объединение одинаковых строк для подсчёта в одну таблицу в памяти приводит к недопустимому расходованию ресурсов. Да и запрос такой выполняется час и более.

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

INSERT IGNORE INTO `member_tmp` (`user_id`)
    SELECT `user_id` FROM `member_lst_%1`
    INNER JOIN `member_lst_%2` USING(`user_id`)

Атрибут IGNORE в запросе позволил отсеять одинаковые строки уже между сравнениями каждой пары таблиц и оставить лишь уникальные значения. Это решение снизило время ожидания результата до десятка минут. Ну и конечно отсутствие излишнего потребления памяти машины (окромя дискового пространства, но его в расчёт не принимаю в виду отсутствия особых ограничений).

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

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

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

Дело за малым:

CREATE TABLE IF NOT EXISTS `member_unite` (
    `group1_id` BIGINT UNSIGNED NOT NULL
    , `group2_id` BIGINT UNSIGNED NOT NULL
    , `user_id` BIGINT UNSIGNED NOT NULL
    , PRIMARY KEY(`group1_id`, `group2_id`, `user_id`)
)

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

Осталось реальные данные занести в эту таблицу и своевременно, раз в сутки обновлять. Этим у меня занялся тот же паук, что производит, собственно, обновление данных исходных таблиц.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.