Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / MySQL [игнор отключен] [закрыт для гостей] / помогите составить высокопроизводительный запрос для выборки пересекающихся данных / 16 сообщений из 16, страница 1 из 1
24.07.2013, 03:54:46
    #38341532
dark_drakon
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, 04:38:53
    #38341537
javajdbc
javajdbc
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
dark_drakon,

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

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

По теме: как не крути -- полный картезиан будет наиболее быстрым
при частых совпадений. Если совпадения редкие, то , возможно,
перебор с кусором быдет интересным.... заранее вам
поможет предсказать руководство Спортлото.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
24.07.2013, 13:32:32
    #38342044
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
dark_drakon,

Чтобы лучше понять задачу - приведите пример исходных данных для для одного-двух значений k1 и результат, который из них должен получиться.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
24.07.2013, 13:34:01
    #38342046
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
javajdbcdark_drakon,

круто!
представим себе что все пятняшки одинаковые.
Тогда на милиард К1 будет милиард-милиардов груп!Почему? Насколько я понял задачу, в результате количество записей не может быть больше, чем в исходных данных, и не меньше, чем 1/15.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
24.07.2013, 15:08:18
    #38342269
deblogger
deblogger
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
Не по теме, но по теме

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

Это номер 2. :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.07.2013, 01:08:52
    #38343029
dark_drakon
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, 15:45:02
    #38343875
lookat
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, 16:28:24
    #38343942
tanglir
tanglir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
lookatКаков должен быть ответ?три группы же
вроде бы тс ясно всё описал
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.07.2013, 16:39:55
    #38343971
dark_drakon
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:49:44
    #38343994
tanglir
tanglir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
dark_drakonЕсли один ключ может принадлежать разным группам по разным наборам параметров - то выполняется привязка к той группе, с которой больше совпадений параметров.хмм... а вот теперь я вообще НХНП. А если он, к примеру, принадлежит к 2 (или более) разным группам с одинаковым количеством параметров(, пересекающимся попарно только по этому ключу)?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.07.2013, 17:05:48
    #38344028
javajdbc
javajdbc
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
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, 19:25:10
    #38344254
Arhat109
Arhat109
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
javajdbc,

полагаю (глядя в ХШ) что задача оптимизации ключей доступа при организации их в "связки ключей"... есть така проблема с ключами...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.07.2013, 20:09:05
    #38344303
dark_drakon
dark_drakon
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
tanglirdark_drakonЕсли один ключ может принадлежать разным группам по разным наборам параметров - то выполняется привязка к той группе, с которой больше совпадений параметров.хмм... а вот теперь я вообще НХНП. А если он, к примеру, принадлежит к 2 (или более) разным группам с одинаковым количеством параметров(, пересекающимся попарно только по этому ключу)?

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


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

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

Судя по всему, действительно, в таком виде задача получается слишком громоздкой. )) Ладно, немного упростим. Пусть вопрос будет звучать так:
Берем список параметров k2 для ключа k1. Т.е. имеется набор из 15 чисел. Ключ k1 уже не интересен. Каким наиболее быстрым способом сделать выборку из таблицы ключей k1, имеющих более 5 совпадающих параметров с этим набором чисел?
Надеюсь, что этот вопрос уже можно считать конкретным. ))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.07.2013, 20:52:57
    #38344348
javajdbc
javajdbc
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
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
| Ответить | Цитировать | Написать  
26.07.2013, 23:17:52
    #38346127
dark_drakon
dark_drakon
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
javajdbc, спасибо за информацию, буду пробовать.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.07.2013, 06:14:27
    #38346203
Arhat109
Arhat109
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
dark_drakon,

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

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

нет?

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

Заявка на покупку рассылается фирмам-поставщикам. Надо выбрать все заявки, в которых участвовало не менее 5 одних и тех же фирм-поставщиков... делал так, но у меня таблички не миллиардные.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / MySQL [игнор отключен] [закрыт для гостей] / помогите составить высокопроизводительный запрос для выборки пересекающихся данных / 16 сообщений из 16, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 369ms
Закрыть
start [/forum/topic.php?fid=47&tablet=1&tid=1836382]:
 0ms
get settings:
 7ms
get forum list:
 16ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 53ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 51ms
get tp. blocked users:
 1ms
others: 224ms
total:  369ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]