помогите составить высокопроизводительный запрос для выборки пересекающихся данных / MySQL

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

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

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / MySQL [игнор отключен] [закрыт для гостей] / помогите составить высокопроизводительный запрос для выборки пересекающихся данных

16 сообщений из 16, страница 1 из 1

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38341532

dark_drakon

Гость

Всем доброго времени суток.

Имеется таблица вида:
ID|k1|k2
*|1|554
*|1|34
*|1|354
*|1|353
*|1|654
...
*|2|4
*|2|34
*|2|34
*|2|124
*|2|6424
...

Поле ID интереса не представляет. Каждый элемент из поля k1 всегда имеет 15 значений в поле k2. Таблица может иметь больше миллиарда строк. У некоторых элементов k1 есть несколько одинаковых параметров k2.

На основании этой таблицы, нужно составить таблицу вида |ID|grp|k1|, где id не важен, k1 - это ключ из первой таблицы, grp - это номер группы ключей. Ключи k1 нужно сгруппировать по следующей логике: Если ключи из k1 имеют больше 5 совпадающих значений в столбце k2, то они принадлежат одной группе. Если ключ из k1 не имеет достаточного количества совпадающих значений - то он просто единственный член своей группы. Т.е. стоит задача группировки ключей имеющих пересечения параметров.

Скрипт группировки будет выполняться редко, но учитывая большой объем данных, нужно подумать над производительностью.
Можно задействовать вспомогательные таблицы. Т.к. количество параметров k2 у ключа k1 всегда одинаковое и равно 15 - то можно начальную таблицу сделать вида |id|k1|par1|par2|...|par15|, если это как-то повысит скорость выборки.

Если какому-либо гуру будет лень расписывать алгоритм решения в коде, то я буду рад прочитать любые идеи просто на уровне алгоритмов. Уже голову сломал над оптимальным алгоритмом. Тупым перебором решить можно, но учитывая то, что строк может быть больше миллиарда - то хочется иметь наиболее оптимальное решение.

Заранее благодарю всех высказавшихся по существу.

...

Рейтинг:

0 / 0

24.07.2013, 03:54:46

| Ответить | Цитировать | Написать

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38341537

javajdbc

Участник

Откуда: Montreal

Сообщения: 18 207

Рейтинг: 0 / 0

dark_drakon,

круто!
представим себе что все пятняшки одинаковые.
Тогда на милиард К1 будет милиард-милиардов груп!
ну ок, пол-милиард-милиардов груп...
плюс-минус милиард погоды не делает.

Опять дейтинг сайт на котором надо совпадение по интересам искать?
или програмка для перлюстрации емаилов?

По теме: как не крути -- полный картезиан будет наиболее быстрым
при частых совпадений. Если совпадения редкие, то , возможно,
перебор с кусором быдет интересным.... заранее вам
поможет предсказать руководство Спортлото.

...

Рейтинг:

0 / 0

24.07.2013, 04:38:53

| Ответить | Цитировать | Написать

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38342044

miksoft

Участник

Сообщения: 36 746

Рейтинг: 0 / 0

dark_drakon,

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

...

Рейтинг:

0 / 0

24.07.2013, 13:32:32

| Ответить | Цитировать | Написать

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38342046

miksoft

Участник

Сообщения: 36 746

Рейтинг: 0 / 0

javajdbcdark_drakon,

круто!
представим себе что все пятняшки одинаковые.
Тогда на милиард К1 будет милиард-милиардов груп!Почему? Насколько я понял задачу, в результате количество записей не может быть больше, чем в исходных данных, и не меньше, чем 1/15.

...

Рейтинг:

0 / 0

24.07.2013, 13:34:01

| Ответить | Цитировать | Написать

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38342269

deblogger

Участник

Сообщения: 829

Рейтинг: 0 / 0

Не по теме, но по теме

Все вопросы по БД делятся на две категории. 1 - от новичков которые не хотят читать документацию, и 2 - от программистов которые выдумывают несусветные способы как покончить жизнь самоубийством. :)

Это номер 2. :)

...

Рейтинг:

0 / 0

24.07.2013, 15:08:18

| Ответить | Цитировать | Написать

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38343029

dark_drakon

Гость

Постараюсь описать задачу поподробней.
Пусть это будет пример таблицы исходных данных: (Разнесу данные по столбцам для удобства визуального восприятия, но это все одна таблица из 3-х колонок)

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.

|id|k1 |k2 |      |id|k1 |k2 |      |id|k1 |k2 |      |id|k1 |k2 |      |id|k1 |k2 |      |id|k1 |k2 |      
......................................................................................................
| *|1  |12 |      | *|2  |27 |      | *|3  |13 |      | *|4  |57 |      | *|5  |72 |      | *|6  |11 |
| *|1  |13 |      | *|2  |28 |      | *|3  |19 |      | *|4  |58 |      | *|5  |73 |      | *|6  |16 |
| *|1  |14 |      | *|2  |29 |      | *|3  |44 |      | *|4  |59 |      | *|5  |74 |      | *|6  |13 |
| *|1  |15 |      | *|2  |18 |      | *|3  |45 |      | *|4  |60 |      | *|5  |75 |      | *|6  |90 |
| *|1  |16 |      | *|2  |19 |      | *|3  |46 |      | *|4  |61 |      | *|5  |76 |      | *|6  |91 |
| *|1  |17 |      | *|2  |32 |      | *|3  |47 |      | *|4  |62 |      | *|5  |77 |      | *|6  |92 |
| *|1  |18 |      | *|2  |13 |      | *|3  |18 |      | *|4  |63 |      | *|5  |78 |      | *|6  |77 |
| *|1  |19 |      | *|2  |34 |      | *|3  |49 |      | *|4  |16 |      | *|5  |79 |      | *|6  |78 |
| *|1  |20 |      | *|2  |12 |      | *|3  |50 |      | *|4  |65 |      | *|5  |80 |      | *|6  |95 |
| *|1  |21 |      | *|2  |15 |      | *|3  |51 |      | *|4  |13 |      | *|5  |81 |      | *|6  |96 |
| *|1  |22 |      | *|2  |37 |      | *|3  |52 |      | *|4  |67 |      | *|5  |82 |      | *|6  |97 |
| *|1  |23 |      | *|2  |38 |      | *|3  |15 |      | *|4  |68 |      | *|5  |83 |      | *|6  |86 |
| *|1  |24 |      | *|2  |16 |      | *|3  |15 |      | *|4  |69 |      | *|5  |84 |      | *|6  |85 |
| *|1  |25 |      | *|2  |40 |      | *|3  |12 |      | *|4  |70 |      | *|5  |85 |      | *|6  |72 |
| *|1  |26 |      | *|2  |41 |      | *|3  |16 |      | *|4  |12 |      | *|5  |86 |      | *|6  |73 |

Все значения параметров k2 для каждого ключа k1 всегда разные между собой.

Результат обработки вышеуказанной таблицы имеет вид

Код: plaintext

1.
2.
3.
4.
5.
6.
7.

id|grp|k1
* |1  |1
* |1  |2
* |1  |3
* |2  |5
* |2  |6
* |3  |4

Ключи 1,2,3 принадлежат 1 группе, т.к. имеют больше 5 общих параметров. (помечены красным) Ключ 4 не входит ни в одну группу, т.к. не имеет ни с кем больше 5 совпадений. Ключи 5 и 6 принадлежат одной группе, т.к. имеют больше 5 пересечений данных. (помечены зеленым)

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

...

Рейтинг:

0 / 0

25.07.2013, 01:08:52

| Ответить | Цитировать | Написать

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38343875

lookat

Гость

dark_drakon,

Уточняющие вопросы:

1. Сколько примерно будет
select distinct count(k2) ?
Ну и select distinct count(k1) до кучи.

2. Если, например, ключи k1=1 и k1=2
имеют 6 совпадений по одному набору k2,
а k1=1 и k1=3 -- по другому набору k2,
а k=2 и k=3 -- по третьему набору k2,
и эти наборы ключей k2 совсем разные
(или частично совпадают)?
Каков должен быть ответ?

Удачи

...

Рейтинг:

0 / 0

25.07.2013, 15:45:02

| Ответить | Цитировать | Написать

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38343942

tanglir

Участник

Сообщения: 30 379

Рейтинг: 0 / 0

lookatКаков должен быть ответ?три группы же
вроде бы тс ясно всё описал

...

Рейтинг:

0 / 0

25.07.2013, 16:28:24

| Ответить | Цитировать | Написать

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38343971

dark_drakon

Гость

lookatdark_drakon,

Уточняющие вопросы:

1. Сколько примерно будет
select distinct count(k2) ?
Ну и select distinct count(k1) до кучи.

2. Если, например, ключи k1=1 и k1=2
имеют 6 совпадений по одному набору k2,
а k1=1 и k1=3 -- по другому набору k2,
а k=2 и k=3 -- по третьему набору k2,
и эти наборы ключей k2 совсем разные
(или частично совпадают)?
Каков должен быть ответ?

Удачи

1) Не могу дать ответ, т.к. набор исходных данных может быть различным.

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

...

Рейтинг:

0 / 0

25.07.2013, 16:39:55

| Ответить | Цитировать | Написать

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38343994

tanglir

Участник

Сообщения: 30 379

Рейтинг: 0 / 0

dark_drakonЕсли один ключ может принадлежать разным группам по разным наборам параметров - то выполняется привязка к той группе, с которой больше совпадений параметров.хмм... а вот теперь я вообще НХНП. А если он, к примеру, принадлежит к 2 (или более) разным группам с одинаковым количеством параметров(, пересекающимся попарно только по этому ключу)?

...

Рейтинг:

0 / 0

25.07.2013, 16:49:44

| Ответить | Цитировать | Написать

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38344028

javajdbc

Участник

Откуда: Montreal

Сообщения: 18 207

Рейтинг: 0 / 0

dark_drakonlookatdark_drakon,

Уточняющие вопросы:

1. Сколько примерно будет
select distinct count(k2) ?
Ну и select distinct count(k1) до кучи.

2. Если, например, ключи k1=1 и k1=2
имеют 6 совпадений по одному набору k2,
а k1=1 и k1=3 -- по другому набору k2,
а k=2 и k=3 -- по третьему набору k2,
и эти наборы ключей k2 совсем разные
(или частично совпадают)?
Каков должен быть ответ?

Удачи

1) Не могу дать ответ, т.к. набор исходных данных может быть различным.

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

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

...

Рейтинг:

0 / 0

25.07.2013, 17:05:48

| Ответить | Цитировать | Написать

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38344254

Arhat109

Участник

Откуда: из СССР

Сообщения: 2 387

Рейтинг: 0 / 0

javajdbc,

полагаю (глядя в ХШ) что задача оптимизации ключей доступа при организации их в "связки ключей"... есть така проблема с ключами...

...

Рейтинг:

0 / 0

25.07.2013, 19:25:10

| Ответить | Цитировать | Написать

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38344303

dark_drakon

Гость

tanglirdark_drakonЕсли один ключ может принадлежать разным группам по разным наборам параметров - то выполняется привязка к той группе, с которой больше совпадений параметров.хмм... а вот теперь я вообще НХНП. А если он, к примеру, принадлежит к 2 (или более) разным группам с одинаковым количеством параметров(, пересекающимся попарно только по этому ключу)?

Подойдет любая из этих групп.

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

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

Судя по всему, действительно, в таком виде задача получается слишком громоздкой. )) Ладно, немного упростим. Пусть вопрос будет звучать так:
Берем список параметров k2 для ключа k1. Т.е. имеется набор из 15 чисел. Ключ k1 уже не интересен. Каким наиболее быстрым способом сделать выборку из таблицы ключей k1, имеющих более 5 совпадающих параметров с этим набором чисел?
Надеюсь, что этот вопрос уже можно считать конкретным. ))

...

Рейтинг:

0 / 0

25.07.2013, 20:09:05

| Ответить | Цитировать | Написать

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38344348

javajdbc

Участник

Откуда: Montreal

Сообщения: 18 207

Рейтинг: 0 / 0

dark_drakon,

при некоторых условия вот это может быть быстрым.
Условие -- достаточно большая селективность по К2.
Решение для параметров N=3, минимум совпадений M=3

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.

select k1
from
(
select k1 
from k1k2_table k
where k2 = param1
union all
select k1 
from k1k2_table k
where k2 = param2
union all
select k1 
from k1k2_table k
where k2 = param3
) z
group by k1
having count(1) > 2

При малой селективности может (а может и нет) простой перебор
будет быстрее:

Код: sql

1.
2.
3.
4.
5.

select k1
from k1k2
where k2 in (param1,param2,param3)
group by k1
having count(1)>2

...

Рейтинг:

0 / 0

25.07.2013, 20:52:57

| Ответить | Цитировать | Написать

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38346127

dark_drakon

Гость

javajdbc, спасибо за информацию, буду пробовать.

...

Рейтинг:

0 / 0

26.07.2013, 23:17:52

| Ответить | Цитировать | Написать

помогите составить высокопроизводительный запрос для выборки пересекающихся данных

#38346203

Arhat109

Участник

Откуда: из СССР

Сообщения: 2 387

Рейтинг: 0 / 0

dark_drakon,

Подумал тут, а задачка достаточно интересна. По сути, если правильно понял, то надо найти такие одинаковые наборы к1, у которых одинаковый (какой-то) комплект к2 (по 5 или сколько там штук)...

Несколько соображений:
1. Группировка по к2 исходной таблицы, позволяет свернуть через GROUP_CONCAT(к1 ORDER BY к1), или как ещё определиться со всеми к1, принадлежащие этому к2.
2. Группировка по такой свертке, даст группу всех к2 подходящих к такой группе к1. Остается подсчитать количество собранных к2 и отобрать те, где их больше заданного (5).

нет?

Как пример, у себя нашел подобное решение:

Заявка на покупку рассылается фирмам-поставщикам. Надо выбрать все заявки, в которых участвовало не менее 5 одних и тех же фирм-поставщиков... делал так, но у меня таблички не миллиардные.

...

Рейтинг:

0 / 0

27.07.2013, 06:14:27

| Ответить | Цитировать | Написать

16 сообщений из 16, страница 1 из 1

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=47&fpage=216&tid=1836382]:	0ms
get settings:	8ms
get forum list:	12ms
check forum access:	2ms
check topic access:	2ms
track hit:	24ms
get topic data:	6ms
get forum data:	1ms
get page messages:	28ms
get tp. blocked users:	1ms
others:	224ms

total:	308ms

	Необходимые cookie
	Cookie для сбора статистики
	Cookie для маркетинга и рекламы