ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / MySQL [игнор отключен] [закрыт для гостей] / помогите составить высокопроизводительный запрос для выборки пересекающихся данных
16 сообщений из 16, страница 1 из 1
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
    #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, 03:54:46
| Ответить | Цитировать | Написать  
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
    #38341537
Фотография javajdbc
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
javajdbc
Участник
dark_drakon,

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

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

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

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

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

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

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

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

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


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

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

Судя по всему, действительно, в таком виде задача получается слишком громоздкой. )) Ладно, немного упростим. Пусть вопрос будет звучать так:
Берем список параметров k2 для ключа k1. Т.е. имеется набор из 15 чисел. Ключ k1 уже не интересен. Каким наиболее быстрым способом сделать выборку из таблицы ключей k1, имеющих более 5 совпадающих параметров с этим набором чисел?
Надеюсь, что этот вопрос уже можно считать конкретным. ))
...
Рейтинг: 0 / 0
25.07.2013, 20:09:05
| Ответить | Цитировать | Написать  
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
    #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
25.07.2013, 20:52:57
| Ответить | Цитировать | Написать  
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
    #38346127
dark_drakon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dark_drakon
Гость
javajdbc, спасибо за информацию, буду пробовать.
...
Рейтинг: 0 / 0
26.07.2013, 23:17:52
| Ответить | Цитировать | Написать  
помогите составить высокопроизводительный запрос для выборки пересекающихся данных
    #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
27.07.2013, 06:14:27
| Ответить | Цитировать | Написать  
16 сообщений из 16, страница 1 из 1
Форумы / MySQL [игнор отключен] [закрыт для гостей] / помогите составить высокопроизводительный запрос для выборки пересекающихся данных
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=47&msg=38346127&tid=1836382]:
 0ms
get settings:
 5ms
get forum list:
 9ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 426ms
get topic data:
 6ms
get forum data:
 1ms
get page messages:
 30ms
get tp. blocked users:
 1ms
others: 203ms
total:  685ms
созд. / загр.: 685ms
x
x
Закрыть


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