Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / PostgreSQL Новый топик    Ответить
 задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
Legushka
Member

Откуда: Казань
Сообщений: 609
есть запрос
select count(*) from Таблица WHERE
(группа несвязанных условий А)
or
(группа несвязанных условий B)
or
(группа несвязанных условий С)
or
(группа несвязанных условий D)
or
(группа несвязанных условий E)

или грубо говоря where А+B+C+D+E

для каждых отдельных групп условий есть подходящие индексы, которые перестают работать в случае с OR (стоимость запроса в результате неслабо растет с каждым новым добавлением нового OR)

подсказка: разрешено считать отдельными кусками например

select count(*) from Таблица
WHERE
(группа несвязанных условий А)
AND
(группа несвязанных условий B)
AND
(группа несвязанных условий E)


или грубо говоря where А*B*E
который сработает достаточно быстро (AND прекрасно работает по индексам)


кто сможет составить алгоритм счета что бы все сработало по индексам и был точный count)
сразу скажу что кто догадается то сможет для любого количества OR составить уровнение
26 сен 17, 17:47    [20824691]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
fte
Member

Откуда: Moscow
Сообщений: 303
на вскидку....
with a as (
     select count(*) cnt from Таблица WHERE группа несвязанных условий А
), 
b as (
     select count(*) cnt from Таблица WHERE группа несвязанных условий B
)
select sum(cnt) from (
select * from a
union 
select * from b
) r
26 сен 17, 18:11    [20824748]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
Legushka
Member

Откуда: Казань
Сообщений: 609
fte хорошее начало для двух условий, но у вас будет перебор по общему количеству, в случае если есть общие пересечения-)
26 сен 17, 18:15    [20824760]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
fte
Member

Откуда: Moscow
Сообщений: 303
нет, вот так правильно....
with a as (
     select pkey,1 cnt from Таблица WHERE группа несвязанных условий А
), 
b as (
     select pkey,1 cnt from Таблица WHERE группа несвязанных условий B
)
select sum(cnt) from (
select * from a
intersect
select * from b
) r
26 сен 17, 18:28    [20824790]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
vyegorov
Member

Откуда: Рига
Сообщений: 970
Legushka,

`count(*) FILTER (WHERE …)` ?
26 сен 17, 18:31    [20824795]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
fte
Member

Откуда: Moscow
Сообщений: 303
Виноват
не intersect a union distinct
26 сен 17, 18:31    [20824796]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
Legushka
Member

Откуда: Казань
Сообщений: 609
ладно по двум условиям без лишних pkay:
fte ваш способ изначальный был очень близок, поэтому его и берем)

with a as (
     select count(*) cnt from Таблица WHERE A
), 
b as (
     select count(*) cnt from Таблица WHERE B
),
ab as (
     select count(*) cnt from Таблица WHERE A and B
)
select sum(cnt) from (
select * from a
union all
select * from b
union all
select -* from ab
) r


грубо говоря считаем отдельно:
количество строк в таблице А + количество строк в таблице Б минус количество строк в пересечении АиБ


слабо теперь решить задачу из шапки? )
26 сен 17, 19:09    [20824890]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
Alexius
Member

Откуда:
Сообщений: 637
Legushka,

вы предлагаете такой огород городить?
Картинка с другого сайта.

а какая у вас примерно селективность условий, т.е. какой процент строк таблицы им удовлетворяет ? нельзя как-то планировщик bitmapor заставить использовать?
27 сен 17, 08:26    [20825663]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
Legushka
Member

Откуда: Казань
Сообщений: 609
Alexius, вы хитрец и вы тоже уловили фишку)
но ладно раскрою секрет более простого решения, что бы огород не был таким страшным)


для одного уловия
А

для двух
А + B - AB

для трех условий
А + B + C - AB - AC - BC + ABC

для четырех условий
А + B + C + D - AB - AC - BC - AD - BC - BD - CD + ABC + ABD + BCD - ABCD

и тд,
где например А это отдельно посчитанные count по группе условий А,
АB это отдельно посчитанные count по условию А and B
АBC это отдельно посчитанные count по условию А and B and C
и тд

видно что нечетные переборы условий всегда суммируем, четные вычитаем, с каждым новым добавлением OR количество переборов нехило возрастает, но это не так страшно,
ведь все условия работают через AND, OR не используется, если есть подходящие индексы то запрос будет летать)

удачного всем дня
27 сен 17, 15:05    [20826902]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
qwwq
Member

Откуда:
Сообщений: 2277
Legushka
Alexius, вы хитрец и вы тоже уловили фишку)
но ладно раскрою секрет более простого решения, что бы огород не был таким страшным)


ну ты, мальчик, де-Билл.
написал то же самое, только в кривых необщепризнанных обозначениях, и радости полные штаны
27 сен 17, 16:02    [20827108]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
Sergei.Agalakov
Member

Откуда:
Сообщений: 551
Вот прямо сейчас такой запрос полетит.
Пять запросов в начальном условии. Пусть каждое условие коснется ~5% данных с возможным небольшим пересечением. При подсчете в лоб читается вся таблица для подсчета ~25% строк. Каждый блок читается один раз. А теперь подглядеть сколько чтений потребуется при предлагаемом хитрож хитроумном подходе с обязательным использованием индексов, и постигаем дзен.
Я уж не говорю про поддержку такого кода. Для пятничной задачки еще бы сошло.
27 сен 17, 17:58    [20827497]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
qwwq
Member

Откуда:
Сообщений: 2277
Sergei.Agalakov, а если 1% в итоге ?

там пж либо пустится в битмап--оры, что решает задачу, теоретиццки -- в ту же цену, и даже дешевле (все эти юнион--иксепты и прочие интерсеки они не задаром).
, либо ошибется с планированием, и упадет в фулл-скан.
28 сен 17, 10:37    [20828439]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
Sergei.Agalakov
Member

Откуда:
Сообщений: 551
Я, собственно, спорил с утверждением, что вот такой запрос при наличии индексов просто обязан летать. Ну очень зависит от данных. Вполне возможно построить пример где такой запрос будет быстрее, но как серебрянная пуля для решения поставленной задачи он не годится вообще. Ключевые слова из начального условия 'группа несвязанных условий'. Для произвольных условий, да еще если можно новую группу добавить... Единственное универсальное решение - фулл скан, расслабиться и получить удовольствие. Для частных и фиксированных случаев можно попробовать найти более оптимальное частное решение.
28 сен 17, 19:41    [20830075]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
qwwq
Member

Откуда:
Сообщений: 2277
Sergei.Agalakov,

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

а пж будет пользоваться моделью независимых условий. и очень быстро вылетит в прогнозах на порядки. а то и порядки порядков.(хотя бы двоичных). и припустится фуллсканить.

и ещё у ТС наверняка не всё сказано -- там очень могут где--то лимиты быть в рукаве, при необъявленных, но явно подразумеваемых аппендах по партициям. которые по битмап--орам не просовываются в мердж-аппенды, например.
28 сен 17, 20:29    [20830152]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
Sergei.Agalakov
Member

Откуда:
Сообщений: 551
qwwq,

Ты исходишь из того, что все условия изначально избирательные. Достаточно одного условия где фулл скан выгоднее, и все остальное уже неважно. Пример с неявной корреляцией работает против индексов. Вот у тебя условие ABCDE, где у каждой колонки избирательность 25%. Постгрес радостно насчитывает что ему надо вернуть 1/1024 от общего количества записей, и промахивается на пару порядков, поскольку в реальности колонки сильно коррелируют.
В общем, как я уже говорил, такой подход можно использовать в очень частных случаях заранее известных условий и распределения данных.
29 сен 17, 02:40    [20830630]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
qwwq
Member

Откуда:
Сообщений: 2277
Sergei.Agalakov
qwwq,

Ты исходишь из того, что все условия изначально избирательные. Достаточно одного условия где фулл скан выгоднее, и все остальное уже неважно. Пример с неявной корреляцией работает против индексов. Вот у тебя условие ABCDE, где у каждой колонки избирательность 25%. Постгрес радостно насчитывает что ему надо вернуть 1/1024 от общего количества записей, и промахивается на пару порядков, поскольку в реальности колонки сильно коррелируют.
В общем, как я уже говорил, такой подход можно использовать в очень частных случаях заранее известных условий и распределения данных.


это в рамочку и на стену.
если не понятно -- смотрим ещё раз на условие OR , а не AND (для которого пж именно так бы и поступил, и сделал бы верно).
я понимаю, что вы от быстродумия, а не со зла или по недоумию
но радует , как чаплин в луже


теперь ещё раз -- для неккорелированных оров пж всё так же считал бы радостно малыми не объединения, а пересечения, т.е. по сути складывал бы прогнозы по орам. когда их 10--ки , и они, на деле сильно кореллированы -- т.е. пересекаются почти полностью -- прогноз ошибёцца в эти самые почти десять раз. (набрать много больше нам вряд ли удасцо).

с заключением про частность и заранеесть соглпасен более чем полностью. именно поэтому такие штуки в норме (но пока не в пж) должен делать сам оптимайзер.

но, чудится мне, у ТС-а там ещё какие--то часные особости есть, которых мы не знаем.
29 сен 17, 11:13    [20831150]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
qwwq
Member

Откуда:
Сообщений: 2277
qwwq,

как зоркей сокол, признаю, что у тс в старте написано не вообще об запросах, но только о count(). полагаю, он имел в виду IOS по хорошо отмапленным(без хип--фетчей) и прогретым индексам . тогда переход на битмап--ор приведет к обязательным хип--фетчам (хотя бы на речек), которые могут быть холодными. и речь, возможно, вообще не про разницу с фулл-сканом, а про смену с IOS на IS+BitmapOr

всё имхо, могу врать
29 сен 17, 11:24    [20831189]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
Sergei.Agalakov
Member

Откуда:
Сообщений: 551
qwwq
Sergei.Agalakov
qwwq,

Ты исходишь из того, что все условия изначально избирательные. Достаточно одного условия где фулл скан выгоднее, и все остальное уже неважно. Пример с неявной корреляцией работает против индексов. Вот у тебя условие ABCDE, где у каждой колонки избирательность 25%. Постгрес радостно насчитывает что ему надо вернуть 1/1024 от общего количества записей, и промахивается на пару порядков, поскольку в реальности колонки сильно коррелируют.
В общем, как я уже говорил, такой подход можно использовать в очень частных случаях заранее известных условий и распределения данных.


это в рамочку и на стену.
если не понятно -- смотрим ещё раз на условие OR , а не AND (для которого пж именно так бы и поступил, и сделал бы верно).

И с чего бы это я должен смотреть на OR, когда у автора в решении AND?
20826902
qwwq
для четырех условий
А + B + C + D - AB - AC - BC - AD - BC - BD - CD + ABC + ABD + BCD - ABCD

и тд,
где например А это отдельно посчитанные count по группе условий А,
АB это отдельно посчитанные count по условию А and B
АBC это отдельно посчитанные count по условию А and B and C
и тд


qwwq
я понимаю, что вы от быстродумия, а не со зла или по недоумию...
:^)
29 сен 17, 17:49    [20832401]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
qwwq
Member

Откуда:
Сообщений: 2277
Sergei.Agalakov,

ts
для каждых отдельных групп условий есть подходящие индексы, которые перестают работать в случае с OR (стоимость запроса в результате неслабо растет с каждым новым добавлением нового OR)


аффтар многа что написаль
но вот те "унд" которые у вас -- у него проиндексированы, типа.
а вот те "ор" которые у меня -- они у тс в шапке темы, ага.
и в стартовом посте, например.
т.ч. давайте уже, не задерживайтесь, чоле.
29 сен 17, 22:06    [20832680]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
qwwq
Member

Откуда:
Сообщений: 2277
ps нашел настоящую задачу "на зосыпку"
5052714

посчитать обратную матрицу чистым SQL . с with recursive; filter в window-fun и lateral --ами оно кажеццо уже д.б. близко. всего то 3--уровня лупов надо реализовать.

начать с
5050997
дополнить расчетным столбцом E --диагональной, и пихать по жордану свою в диагональ, а E в искомую.

есть дартаньяны ?
насколь скл стал полным языком коддинга, проверить.

а то большие матрички в питоне не считаются.
29 сен 17, 22:21    [20832709]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
LeXa NalBat
Member

Откуда: Москва
Сообщений: 2883
Legushka
для каждых отдельных групп условий есть подходящие индексы, которые перестают работать в случае с OR
Не перестают. BitmapOr отлично работает.

                                                          QUERY PLAN                                                           
-------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on t1 (cost=192.84..4767.84 rows=9975 width=8) (actual time=1.954..6.332 rows=1994 loops=1)
Recheck Cond: ((f1 = 1) OR (f2 = 2))
Heap Blocks: exact=1608
-> BitmapOr (cost=192.84..192.84 rows=10000 width=0) (actual time=1.194..1.194 rows=0 loops=1)
-> Bitmap Index Scan on t1_f1_idx (cost=0.00..93.92 rows=5000 width=0) (actual time=0.617..0.617 rows=1002 loops=1)
Index Cond: (f1 = 1)
-> Bitmap Index Scan on t1_f2_idx (cost=0.00..93.92 rows=5000 width=0) (actual time=0.573..0.573 rows=994 loops=1)
Index Cond: (f2 = 2)
Planning time: 0.432 ms
Execution time: 6.651 ms
(10 строк)

+
rollback;

begin;

create table t1(
    f1 integer,
    f2 integer
);
insert into t1 select 1000*random(), 1000*random() from generate_series(1, 1000000);
create index on t1(f1);
create index on t1(f2);

explain(analyze) select * from t1 where f1=1 or f2=2;

-- commit;
3 окт 17, 14:42    [20839123]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
qwwq
Member

Откуда:
Сообщений: 2277
LeXa NalBat,
там разница в буферах набегает для IOS vs IS

+
drop table t1;

create table t1(
f1 integer
,f2 integer
,f3 integer
,f4 integer
,t1 text --+width
,t2 text
);
insert into t1 select 1000*random(),1000*random(),1000*random(),1000*random()
	,rpad('assa',100,'assa'),rpad('lexa',100,'lexa') from generate_series(1, 1000000);
create index on t1(f1);
create index on t1(f2);
create index on t1(f3);
create index on t1(f4);
vacuum freeze analyze t1;

explain (analyze,timing,buffers ) select count(1) from t1 where f1=1 or f2=2; --1983
/*
"Aggregate  (cost=6196.28..6196.29 rows=1 width=8) (actual time=2.132..2.132 rows=1 loops=1)"
"  Buffers: shared hit=1938"
*/
explain (analyze,timing,buffers) select (select count(1) from t1 where f1=1) +
				 (select count(1) from t1 where f2=2) -
				 (select count(1) from t1 where f1=1 and f2=2) ; --1983
/*
"Result  (cost=107.13..107.14 rows=1 width=8) (actual time=0.598..0.598 rows=1 loops=1)"
"  Buffers: shared hit=24"
*/
explain (analyze,timing,buffers ) select count(1) from t1 where f1=1 or f2=2 or f3=3;--3049
/*"Aggregate  (cost=8716.97..8716.98 rows=1 width=8) (actual time=3.136..3.137 rows=1 loops=1)"
"  Buffers: shared hit=2918"
*/
explain (analyze,timing,buffers) select (select count(1) from t1 where f1=1)
				+(select count(1) from t1 where f2=2)
				+(select count(1) from t1 where f3=3)
				-(select count(1) from t1 where f1=1 and f2=2)
				-(select count(1) from t1 where f1=1 and f3=3)
				-(select count(1) from t1 where f2=2 and f3=3)
				+(select count(1) from t1 where f1=1 and f2=2 and f3=3)
				; --3049
/*"Result  (cost=269.60..269.62 rows=1 width=8) (actual time=1.342..1.342 rows=1 loops=1)"
"  Buffers: shared hit=65"
*/
и.т.д.

для холодных данных это весьма будет заметно
3 окт 17, 16:15    [20839457]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
Legushka
Member

Откуда: Казань
Сообщений: 609
LeXa NalBat,
а если в группе условий А, B, С... участвует subplan ?
видимо из за этого в "моем" персональном случае использования буферов накрутило
4 окт 17, 10:26    [20841111]     Ответить | Цитировать Сообщить модератору
 Re: задача на засыпку, count работающий по индексам (в where есть несколько условий через OR)  [new]
LeXa NalBat
Member

Откуда: Москва
Сообщений: 2883
Legushka, не знаю, надо план смотреть.

qwwq, да, IOS крут.
5 окт 17, 11:40    [20844746]     Ответить | Цитировать Сообщить модератору
Все форумы / PostgreSQL Ответить