Re: Bundle of patches

> useful optimizations most of the time. Have you done any benchmarking
> to find out what the cost is when the optimizations don't succeed?
Test runs on my notebook with PIII/512Mb, FreeBSD 6.1, postgres was compiled
with -O0 and --enable-debug --enable-cassert

Test results (ms)
| [1] | [2] | [3]
-----------------------------------------------------------
[I] 8.3 | 88490.275 | 46684.972 | 21.563
[II] 8.3 splited query | 0.492 | 0.560 | 0.635
[III] 8.3 rewrited query | 0.523 | 0.952 | 1.004
[IV] 8.3+patch | 0.444 | 0.410 | 0.679

Query description
All queries are variants of sinple OR clause with index support. In tests
for 8.3 and 8.3+patch usial queries are used. '8.2 splited query' test executes
separate queries for each OR-ed clause (in supposition that apllication should
concatenate results). '8.3 rewrited query' test uses rewritten queries with
the same result of execution and queries are fast as I could find.

Test result shows a big advantage of using such kind of optimization and
doesn't demonstrate performance gap on optimization stage.

Test suite:
# select * into foo from generate_series(1,100000) as f1, generate_series(1,100)
as f2;
# create index idx on foo (f1,f2);
# vacuum analyze foo;

Queries and plans in details:
==================[I] Without patch=======================
[1]
# explain analyze select * from foo where (f1=70000 and f2>95) or f1>70000 order
by f1, f2 limit 10;
Limit (cost=0.00..45.94 rows=10 width=8) (actual time=88490.044..88490.109
rows=10 loops=1)
-> Index Scan using idx on foo (cost=0.00..14113503.78 rows=3071985
width=8) (actual time=88490.035..88490.072 rows=10 loops=1)
Filter: (((f1 = 70000) AND (f2 > 95)) OR (f1 > 70000))
Total runtime: 88490.275 ms

[2]
# explain analyze select * from foo where (f1>40000 and f1<50000) or (f1>60000
and f1<70000) order by f1, f2 limit 10;
Limit (cost=0.00..69.91 rows=10 width=8) (actual time=46684.725..46684.813
rows=10 loops=1)
-> Index Scan using idx on foo (cost=0.00..14138503.78 rows=2022419
width=8) (actual time=46684.717..46684.768 rows=10 loops=1)
Filter: (((f1 > 40000) AND (f1 < 50000)) OR ((f1 > 60000) AND (f1 <
70000)))
Total runtime: 46684.972 ms

[3]
# explain analyze select * from foo where (f1>49980 and f1<50000) or (f1>69980
and f1<70000) order by f1, f2 limit 10;
Limit (cost=13581.04..13581.07 rows=10 width=8) (actual time=20.767..20.809
rows=10 loops=1)
-> Sort (cost=13581.04..13592.03 rows=4393 width=8) (actual
time=20.759..20.773 rows=10 loops=1)
Sort Key: f1, f2
-> Bitmap Heap Scan on foo (cost=102.12..13315.25 rows=4393 width=8)
(actual time=3.495..11.911 rows=3800 loops=1)
Recheck Cond: (((f1 > 49980) AND (f1 < 50000)) OR ((f1 > 69980) AND
(f1 < 70000)))
-> BitmapOr (cost=102.12..102.12 rows=4393 width=0) (actual
time=3.415..3.415 rows=0 loops=1)
-> Bitmap Index Scan on idx (cost=0.00..51.01 rows=2191
width=0) (actual time=1.887..1.887 rows=1900 loops=1)
Index Cond: ((f1 > 49980) AND (f1 < 50000))
-> Bitmap Index Scan on idx (cost=0.00..51.12 rows=2202
width=0) (actual time=1.519..1.519 rows=1900 loops=1)
Index Cond: ((f1 > 69980) AND (f1 < 70000))
Total runtime: 21.563 ms

=================[II] Without patch, Two queries=======================
Here plans are omitted because they are simple index scans.
[1]
# explain analyze select * from foo where f1=70000 and f2>95 order by f1, f2
limit 10;
Total runtime: 0.219 ms
# explain analyze select * from foo where f1>70000 order by f1, f2 limit 10;
Total runtime: 0.273 ms

[2]
# explain analyze select * from foo where f1>40000 and f1<50000 order by f1,
f2 limit 10;
Total runtime: 0.245 ms
# explain analyze select * from foo where f1>60000 and f1<70000 order by f1, f2
limit 10;
Total runtime: 0.315 ms

[3]
# explain analyze select * from foo where f1>49980 and f1<50000 order by f1, f2
limit 10;
Total runtime: 0.292 ms
# explain analyze seleCt * from foo where f1>69980 and f1<70000 order by f1, f2
limit 10;
Total runtime: 0.343 ms

==================[III]Without patch, rewrited query===================
[1]
# explain analyze select * from foo where ((f1=70000 and f2>95) or f1>70000) and
f1>=70000 order by f1, f2 limit 10;
Limit (cost=0.00..50.33 rows=10 width=8) (actual time=0.320..0.387 rows=10 loops=1)
-> Index Scan using idx on foo (cost=0.00..3974489.10 rows=789613
width=8) (actual time=0.313..0.348 rows=10 loops=1)
Index Cond: (f1 >= 70000)
Filter: (((f1 = 70000) AND (f2 > 95)) OR (f1 > 70000))
Total runtime: 0.523 ms

[2]
# explain analyze
select * from (
select * from (select * from foo where f1>40000 and f1<50000 order by f1,
f2 limit 10) as t1
union all
select * from (select * from foo where f1>60000 and f1<70000 order by f1,
f2 limit 10) as t2
) as t
order by f1, f2 limit 10;
Limit (cost=28.85..28.87 rows=10 width=8) (actual time=0.586..0.627 rows=10
loops=1)
-> Sort (cost=28.85..28.90 rows=20 width=8) (actual time=0.581..0.594
rows=10 loops=1)
Sort Key: t.f1, t.f2
-> Result (cost=0.00..28.42 rows=20 width=8) (actual
time=0.085..0.431 rows=20 loops=1)
-> Append (cost=0.00..28.42 rows=20 width=8) (actual
time=0.076..0.345 rows=20 loops=1)
-> Limit (cost=0.00..14.11 rows=10 width=8) (actual
time=0.074..0.127 rows=10 loops=1)
-> Index Scan using idx on foo (cost=0.00..1358815.69
rows=963067 width=8) (actual time=0.069..0.098 rows=10 loops=1)
Index Cond: ((f1 > 40000) AND (f1 < 50000))
-> Limit (cost=0.00..14.11 rows=10 width=8) (actual
time=0.101..0.154 rows=10 loops=1)
-> Index Scan using idx on foo (cost=0.00..1527039.50
rows=1082489 width=8) (actual time=0.097..0.121 rows=10 loops=1)
Index Cond: ((f1 > 60000) AND (f1 < 70000))
Total runtime: 0.952 ms

[3]
# explain analyze
select * from (
select * from (select * from foo where f1>49980 and f1<50000 order by f1,
f2 limit 10) as t1
union all
select * from (select * from foo where f1>69980 and f1<70000 order by f1,
f2 limit 10) as t2
) as t
order by f1, f2 limit 10;
Limit (cost=35.61..35.64 rows=10 width=8) (actual time=0.630..0.673 rows=10
loops=1)
-> Sort (cost=35.61..35.66 rows=20 width=8) (actual time=0.626..0.641
rows=10 loops=1)
Sort Key: t.f1, t.f2
-> Result (cost=0.00..35.18 rows=20 width=8) (actual
time=0.114..0.476 rows=20 loops=1)
-> Append (cost=0.00..35.18 rows=20 width=8) (actual
time=0.107..0.401 rows=20 loops=1)
-> Limit (cost=0.00..17.51 rows=10 width=8) (actual
time=0.103..0.156 rows=10 loops=1)
-> Index Scan using idx on foo (cost=0.00..3550.22
rows=2028 width=8) (actual time=0.099..0.126 rows=10 loops=1)
Index Cond: ((f1 > 49980) AND (f1 < 50000))
-> Limit (cost=0.00..17.47 rows=10 width=8) (actual
time=0.129..0.181 rows=10 loops=1)
-> Index Scan using idx on foo (cost=0.00..3804.01
rows=2177 width=8) (actual time=0.125..0.152 rows=10 loops=1)
Index Cond: ((f1 > 69980) AND (f1 < 70000))
Total runtime: 1.004 ms

=================[IV]With patch===================
[1]
# explain analyze select * from foo where (f1=70000 and f2>95) or f1>70000 order
by f1, f2 limit 1
Limit (cost=0.00..1.41 rows=1 width=8) (actual time=0.314..0.316 rows=1 loops=1)
-> Index Scan using idx on foo (cost=0.00..4210762.24 rows=2982440
width=8) (actual time=0.309..0.309 rows=1 loops=1)
Index Cond: (f1 >= 70000)
Filter: (((f1 = 70000) AND (f2 > 95)) OR (f1 > 70000))
Total runtime: 0.444 ms

[2]
# explain analyze select * from foo where (f1>40000 and f1<50000) or (f1>60000
and f1<70000) order by f1, f2 limit 10;
Limit (cost=0.00..14.16 rows=10 width=8) (actual time=0.087..0.192 rows=10 loops=1)
-> Result (cost=0.00..2932816.48 rows=2071539 width=8) (actual
time=0.081..0.160 rows=10 loops=1)
-> Append (cost=0.00..2932816.48 rows=2071539 width=8) (actual
time=0.074..0.123 rows=10 loops=1)
-> Index Scan using idx on foo (cost=0.00..1382937.86 rows=976723
width=8) (actual time=0.069..0.092 rows=10 loops=1)
Index Cond: ((f1 > 40000) AND (f1 < 50000))
-> Index Scan using idx on foo (cost=0.00..1549878.62
rows=1094816 width=8) (never executed)
Index Cond: ((f1 > 60000) AND (f1 < 70000))
Total runtime: 0.410 ms

[3]
# explain analyze select * from foo where (f1>49980 and f1<50000) or (f1>69980
and f1<70000) order by f1, f2 limit 10
Limit (cost=0.00..17.57 rows=10 width=8) (actual time=0.115..0.226 rows=10 loops=1)
-> Result (cost=0.00..6902.27 rows=3928 width=8) (actual
time=0.111..0.197 rows=10 loops=1)
-> Append (cost=0.00..6902.27 rows=3928 width=8) (actual
time=0.102..0.156 rows=10 loops=1)
-> Index Scan using idx on foo (cost=0.00..3427.16 rows=1950
width=8) (actual time=0.099..0.125 rows=10 loops=1)
Index Cond: ((f1 > 49980) AND (f1 < 50000))
-> Index Scan using idx on foo (cost=0.00..3475.11 rows=1978
width=8) (never executed)
Index Cond: ((f1 > 69980) AND (f1 < 70000))
Total runtime: 0.679 ms

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/