Уменьшить размер выборки при сравнении по 10 колонкам

Здравствуйте.

Задача есть 2 таблицы с 10 колонками в каждой. В каждой колонке содержатся ID, то есть числовые значения.
Нужно совместить (join) таблицы, используя "нестрогое" соотвествие - 2 записи совмещаются, если значения равны хотя бы в 6-ти колонках.

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

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

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

0

правильное решение - это не иметь 6 колонок и вытянуть их в строки

0

Можно и в строки вытянуть. Но мне нужно отобрать по условию 6 признаков из 10 и не факт, что совпадающие признаки идут подряд.
Например совпадасть может 1,3,4,5,6,8 признак.

0

значения произвольные или фиксированные?

Добавлено через 6 минут
str_id, par, val
1,1,3
1,2,5
1,3,1
1,4,9
2,1,3
2,2,4
2,3,1
2,4,9
вот таблица, представляющая ваши обе,
ее можно связать по полю par и получить количество совпавших

0

Обычный джоин я уже делал. У меня примерно 10 млн. записей. Мне нужно сравнить эти записи друг с другом по условию, которое я описал выше. В колонках хранятся id из словарей по каждому признаку.
На проверку 1 записи уходит с моими ресурсами примерно 17 секунд. 17 х 10 млн. примерно 5.4 года.
Поэтому очень желательно сначала ограничить выборку.
Или (над чем я сейчас работаю) сформировать какой-то хеш-ключ, по которому можно было бы построить индекс для более быстрого поиска схожих записей.
Например: если я хочу сравнить по первым 6-ти признакам я формирую строку из 6-ти ID разделенную каким либо разделителем (пусть |). По этому полю создаю индекс, потом по нему подбираю соотвествующие записи. Тогда на поиск уходит меньше времени (если не учитывать параллельность при сравнении для 1 записи) на 1 запись уходит 12 секунд.
Можно сформировать сочетания по 6 признаков из 10 и сформировать из этих сочетаний строки, но таких сочетаний получается 210. Это много.
В качестве гипотезы - можно ли вычислить какой-нибудь коэффициент, который будет отражать набор 10 признаков? В последствии его можно будет использовать например при сравнении для 1 записи с коэф k - отобрать все записи с коэффициентами плюс/минус от k на определенную величину (величина будет отражать количество признаков для сравнения)

0

исходную задачу озвучьте
потому что правильный подход я описал выше.
12 сек на одну запись это очень печаль
на самом деле 10 млн или 100 это ужас но не ужас-ужас

что нужно сравнить?
каждую с каждой?
одну конкретную с 10 другими?

0

Задача - нужно создать группы строк из всей выборки, у которых совпадают 6 (3-4-5 или сколько необходимо) признаков из 10. Тоесть сделать аггрегацию по совокупности признаков.
Если ближе к реальности:
Предположим существует набор личных данных населения.
В каких-то строках вместо полного имени введено только начальная буква, или поле оставлено пустым, а имя и фамилия введены в поле "Фамилия". Такая же ситуация наблюдается и с другими полями - например может быть введен или пропущен идентификационный код, разное написание адреса и т.д. Причины ошибок - много источников и человеческий фактор.
Но если вручную начать сравнивать записи, то по совокупности признаков можно определить, что эти записи принадлежат одному человеку.
Пока хеш-ключ остается самым оптимальным решением - полное количество подобных записей находится за 12-14 секунд.
Я не проверял, как быстро запишется результирующая выборка, но прямой джоин вообще не выдает общее количество за "терпимое" количество времени.

0

т.е. все-таки полный перебор всех
ну, 12 сек на 10млн это вполне приемлемое время для такой задачи

0