[sql] как искать цепочки?
Сначала пара вопросов:
1. То есть таблица items нам как бы и не нужна?
2. База какая?
3. Я правильно понимаю что position — уникальный ключ?
4. Какие есть индексы на таблице idx и можно ли их создавать?
Теперь по существу:
есть — используй переменные подстановки, остальное зависит от БД
сильно зависит от того как будет построен план: если будет использоваться hash-join то линейно, если nested loop то экспоненциально.
1. То есть таблица items нам как бы и не нужна?
2. База какая?
3. Я правильно понимаю что position — уникальный ключ?
4. Какие есть индексы на таблице idx и можно ли их создавать?
Теперь по существу:
есть что-нибудь более мудрое, нежели для каждой цепочки, которую нужно найти, генерировать такой запрос...
есть — используй переменные подстановки, остальное зависит от БД
насколько это неэффективно для 3-4-5 элементных цепочек?
сильно зависит от того как будет построен план: если будет использоваться hash-join то линейно, если nested loop то экспоненциально.
1. items - там названия. да, для этой задачи не нужна.
2. mysql - это принципиально?
3*. не совсем, но можно считать что да, уникальный.
4. пока никаких. даст ли индекс по position преимущество?
дальше мои знания в БД заканчиваются, ответить на вопросы затрудняюсь.
* бывают случаи, что на одном месте стоит 2-3 разных item - это образуется в случае, когда в исходном потоке не удаётся определить к какому конкретно item относится элемент. тогда ставится ссылка на несколько.
работает по принципу "или".
считается, что в таких случаях цепочка найдена, если хотя подходит хотя бы один вариант
2. mysql - это принципиально?
3*. не совсем, но можно считать что да, уникальный.
4. пока никаких. даст ли индекс по position преимущество?
дальше мои знания в БД заканчиваются, ответить на вопросы затрудняюсь.
* бывают случаи, что на одном месте стоит 2-3 разных item - это образуется в случае, когда в исходном потоке не удаётся определить к какому конкретно item относится элемент. тогда ставится ссылка на несколько.
работает по принципу "или".
считается, что в таких случаях цепочка найдена, если хотя подходит хотя бы один вариант
2. mysql - это принципиально?Конечно ещё и версию нужно указывать.
Например если у тебя был бы SQL Server, Oracle или Postgress(не уверен) можно было бы использовать аналитические функции
4. пока никаких. даст ли индекс по position преимущество?
Индекс по position преимуществ не даст, а вот по item скорее всего поможет: вместо выборки всех 10 млн. записей нужно будет поднять примерно 10 млн./10 тыс. = 1000 записей, что уже гораздо проще.
Ещё может помочь индекс по item, position (именно в этом порядке) но, честно говоря, в этом я не уверен. Нужно проверять.
Дальше насколько я понял в MySql реализован только алгоритм соединения Nested Loops, получается что каждая новая таблица — это ещё один уровень в цикле, т.е. примерно в 1000 раз больше операций.
А не проще ли будет найти позиции начал предполагаемых цепочек и потом проверить каждую из них? Тем более, если на одной позиции может находиться вся цепочка сразу
Если есть возможность использовать дополнительную таблицу, то я бы делал так:
Создание таблицы:
Собственно поиск цепочки:
Создание таблицы:
create table temp_idx (item integer, position integer);
create index on temp_idx(position);
Собственно поиск цепочки:
truncate table temp_idx; -- delete from table temp_idx если нужна параллельная обработка
insert into temp_idx(item, position)
select item, position from idx where item in (3774, 4478);
select
t1.position
from
temp_idx t1,temp_idx t2
where
t1.item_id=3774
and t2.item_id=4478
and t2.position=t1.position+1;
truncate table temp_idx; -- delete from table temp_idx если нужна параллельная обработка
...найти позиции начал предполагаемых цепочек и потом проверить каждую из них?Это как?
ну ты же знаешь элемент-начало цепочки - поиск position по этому значению, результат куда-нибудь сохранить, дальше - насколько фантазии хватит, хоть курсором, хоть джойном
mysql Ver 14.12 Distrib 5.0.76, for pc-linux-gnu (i686) using readline 6.0
возможно, можно переключиться на oracle 9i или 10g
т.е. сделать временную таблицу только на нужные item-ы и там искать подряд идущие позиции - хм, понятно.
ну ты же знаешь элемент-начало цепочки - поиск position по этому значению, результат куда-нибудь сохранить, дальше - насколько фантазии хватит, хоть курсором, хоть джойном
В целом это и делает запрос в первом посте. В памяти формируется rowset по критерию
t1.item_id=3774 дальше во время соединения таблиц для каждой строки из полученного rowset проверяется критерий t2.item_id=4478 and t2.position=t1.position+1
Тут ты завязываешься на position + 1 и на два элемента в цепи. Еще один элемент - еще один джойн
возможно, можно переключиться на oracle 9i или 10gА оно вам надо? Даже не вспоминая про такие мелочи как лицензия, миграция проекта с одной БД на другую дело очень мерзкое.
Про временную таблицу: решение будет плохо работать если распределение строк в таблице idx сильно перекошено в сторону какого-либо элемента. Например если один из item занимает в ней хотя бы 1млн. строк
А вообще идея здравая, реализуется вот так, требует, как минимум, индекса по position:
select t1.position
from idx t1
where
t1.item = :v_itm1
and exists(select 1 from idx t2 where t2.item = :v_itm2 and t2.position = t1.position + 1)
and exists(select 1 from idx t2 where t2.item = :v_itm3 and t2.position = t1.position + 2)
and exists(select 1 from idx t2 where t2.item = :v_itm4 and t2.position = t1.position + 3)
and exists(select 1 from idx t2 where t2.item = :v_itm5 and t2.position = t1.position + 4)
Ну вот набросал на MSSQL - что-нить такое. Индексы на #positions тоже стоит повесить я думаю
create table #idx (position int, itemID int)
create clustered index #IX_pos on #idx(position)
create index #IX_item on #idx (itemID)
-- insert numbers 0..2047
insert into #idx (position, itemID)
select
row_number over (order by number)
, (number % 10) * case when number between 100 and 200 and (number % 10) = 6 then 0 else 1 end -- exclude some chains
from
master..spt_values
where 1 = 1
and type = 'P'
create table #chain (id int, itemID int)
insert into #chain (id, itemID)
select 1,4
union all
select 2,5
union all
select 3,6
create table #positions (position int)
insert into #positions (position)
select
#idx.position
from
#idx
inner join #chain
on #chain.itemID = #idx.itemID
and #chain.id = 1
;with tmp as (
select
p.position start
, #idx.position position
, #idx.itemID itemID
, row_number over (partition by p.position order by #idx.position) rowID
from
#positions p
inner join #idx
on #idx.position between p.position and p.position + 2 -- we know the length
)
select
tmp.start
from
#chain c
inner join tmp
on tmp.itemID = c.itemID
and tmp.rowID = c.ID
group by
tmp.start
having 1 = 1
and count(*) = 3 -- we know the length
order by
tmp.start
drop table #idx, #chain, #positions
Ну вот набросал на MSSQL
Решение красивое (слегка извращённое, но красивое есть два замечания:
1. Не работает когда на одном position висит больше одного элемента.
2. MySQL так не умеет.
1. Не работает, если на одной позиции два звена цепочки
Хороший вопрос.
To : может ли цепочка иметь два и более звена под одни position?
Т.е. подходит ли для цепочки 2,3 вариант:
item, position
--------------
2 , 1
3 , 1
нет, в цепочке строго определённые элементы. они идут подряд, позиции у них не повторяются.
С лицензированием проблем нет.
Проект пока на стадии проектирования, поэтому если на оракле он будет с существенным приростом производительности работать - на него и пересядем.
Есть перекосы на некоторые item. Как обычно - правило 20-80: 20% item-ов образуют 80% массы.
Но можно с уверенностью сказать, что цепочки по большей части будут начинаться именно с "редких".
Проект пока на стадии проектирования, поэтому если на оракле он будет с существенным приростом производительности работать - на него и пересядем.
Есть перекосы на некоторые item. Как обычно - правило 20-80: 20% item-ов образуют 80% массы.
Но можно с уверенностью сказать, что цепочки по большей части будут начинаться именно с "редких".
Проект пока на стадии проектирования, поэтому если на оракле он будет с существенным приростом производительности работать - на него и пересядем.Вряд ли с существенным, но всегда можно попробовать, если перейдёте на oracle напиши мне я тебе патчи выкачаю.
У тебя ведь наверняка есть тестовая БД. Можешь на ней выполнить и построить execution plan моего запроса который с exists, очень интересно как он работает.
Оставить комментарий
yolki
есть таблица idx:item_id INTEGER
position INTEGER
есть таблица items:
item_id INTEGER
name VARCHAR(50)
есть необходимость искать цепочки из 2-3-4 (больше 10 точно не будет) items. - т.е. нужно найти, в каких местах они идут подряд.
есть что-нибудь более мудрое, нежели для каждой цепочки, которую нужно найти, генерировать такой запрос (искомый результат - позиция, с которой цепочка начинается):
(например, нужно найти где встречаются подряд идущие #4478)
насколько это неэффективно для 3-4-5 элементных цепочек?
примерные оценки: idx: ~10 млн записей. количество различных item_id примерно 10 тысяч.