BUG #2259: never ending select from selects

The following bug has been logged online:

Bug reference: 2259
Logged by: Michal Dvoracek
Email address: michal(dot)dvoracek(at)capitol(dot)cz
PostgreSQL version: 8.1.2
Operating system: Debian testing
Description: never ending select from selects
Details:

Hello,

this query runs very long time - after hour i cancelled it.

SELECT * FROM (SELECT
d.zamestnanci_id,d.prostredky_id,d.zacatek,d.delka,p.budovy_id FROM diar AS

d,prostredky AS p,budovy AS b,X_zamestnanci_skupiny AS x WHERE
x.skupinyzamestnancu_id=7 AND x.zamestnanci_id=d.zamestnanci_id AND
d.ukony_id=0 AND d.zamestnanci_id=777 AND d.zacatek>=1139927357 AND
d.delka>=1800 AND d.prostredky_id=p.id AND p.vhodnost_planovani=0 AND
p.budovy_id=b.id AND b.mesto_id=12702) AS d0,(SELECT
d.zamestnanci_id,d.prostredky_id,d.zacatek,d.delka,p.budovy_id FROM diar AS

d,prostredky AS p,budovy AS b,X_zamestnanci_skupiny AS x WHERE
x.skupinyzamestnancu_id=5 AND x.zamestnanci_id=d.zamestnanci_id AND
d.ukony_id=0 AND d.zamestnanci_id=19 AND d.zacatek>=1139927357 AND
d.delka>=1800 AND d.prostredky_id=p.id AND p.vhodnost_planovani=0 AND
p.budovy_id=b.id AND b.mesto_id=12702) AS d1,(SELECT
d.zamestnanci_id,d.prostredky_id,d.zacatek,d.delka,p.budovy_id FROM diar AS

d,prostredky AS p,budovy AS b,X_zamestnanci_skupiny AS x WHERE
x.skupinyzamestnancu_id=5 AND x.zamestnanci_id=d.zamestnanci_id AND
d.ukony_id=0 AND d.zamestnanci_id=19 AND d.zacatek>=1139927357 AND
d.delka>=1800 AND d.prostredky_id=p.id AND p.vhodnost_planovani=0 AND
p.budovy_id=b.id AND b.mesto_id=12702) AS d2,(SELECT
d.zamestnanci_id,d.prostredky_id,d.zacatek,d.delka,p.budovy_id FROM diar AS

d,prostredky AS p,budovy AS b,X_zamestnanci_skupiny AS x WHERE
x.skupinyzamestnancu_id=5 AND x.zamestnanci_id=d.zamestnanci_id AND
d.ukony_id=0 AND d.zamestnanci_id=19 AND d.zacatek>=1139927357 AND
d.delka>=1800 AND d.prostredky_id=p.id AND p.vhodnost_planovani=0 AND
p.budovy_id=b.id AND b.mesto_id=12702) AS d3 WHERE
d1.zacatek<=(d0.zacatek+-257400) AND
(d1.zacatek+d1.delka)>=(d0.zacatek+-255600) AND d0.budovy_id=d1.budovy_id
AND
d2.zacatek<=(d0.zacatek+-255600) AND
(d2.zacatek+d2.delka)>=(d0.zacatek+-253800) AND d0.budovy_id=d2.budovy_id
AND
d3.zacatek<=(d0.zacatek+-253800) AND
(d3.zacatek+d3.delka)>=(d0.zacatek+-252000) AND d0.budovy_id=d3.budovy_id
ORDER BY d0.zacatek LIMIT 5;

QUERY PLAN

----------------------------------------------------------------------------
----------------------------------------------------------------------------
----------------------------------------------------------------------------
-----------------------
----------------------------------------------------------------------------
----------------------------------------------------------------------------
-
Limit (cost=3227.94..3227.94 rows=1 width=80)
-> Sort (cost=3227.94..3227.94 rows=1 width=80)
Sort Key: d.zacatek
-> Nested Loop (cost=1167.30..3227.93 rows=1 width=80)
-> Nested Loop (cost=1167.30..3222.16 rows=1
width=80)
Join Filter: (("outer".zacatek <=
("inner".zacatek +
-253800)) AND (("outer".zacatek + "outer".delka) >= ("inner".zacatek +
-252000)) AND ("outer".zacatek <= ("inner".zacatek + -255600)) AND
(("outer".zacatek + "outer".delka) >= (
"inner".zacatek + -253800)) AND ("outer".zacatek <= ("inner".zacatek +
-257400)) AND (("outer".zacatek + "outer".delka) >= ("inner".zacatek +
-255600)))
-> Nested Loop (cost=1144.82..3195.61
rows=1 width=68)
Join Filter: ("outer".budovy_id =
"inner".budovy_id)
-> Nested Loop
(cost=1101.76..2136.66 rows=1
width=60)
-> Nested Loop
(cost=1101.76..2132.29
rows=1 width=52)
-> Hash Join
(cost=1101.76..2117.51
rows=3 width=48)
Hash
Cond: ("outer".budovy_id =
"inner".budovy_id)
->
Nested Loop
(cost=43.05..1058.65 rows=24 width=24)

-> Index Scan using
i_x_zamestnanci_skupiny_zam_id on x_zamestnanci_skupiny x (cost=0.00..5.76

rows=1 width=4)

Index Cond: (19 =
zamestnanci_id)

Filter:
(skupinyzamestnancu_id = 5)

-> Hash Join
(cost=43.05..1052.65 rows=24 width=24)

Hash Cond:
("outer".prostredky_id = "inner".id)

-> Bitmap Heap Scan
on diar d (cost=3.72..1012.15 rows=186 width=16)

Recheck Cond:
((zamestnanci_id = 19) AND (zacatek >= 1139927357))

Filter:
((ukony_id = 0) AND (delka >= 1800))

-> Bitmap
Index Scan on i_diar_zamestnanci_id_zacatek (cost=0.00..3.72 rows=287
width=0)

Index
Cond: ((zamestnanci_id = 19) AND (zacatek >= 1139927357))

-> Hash
(cost=39.08..39.08 rows=99 width=12)

-> Hash Join
(cost=13.76..39.08 rows=99 width=12)

Hash
Cond: ("outer".budovy_id = "inner".id)

-> Seq
Scan on prostredky p (cost=0.00..20.54 rows=760 width=8)


Filter: (vhodnost_planovani = 0)

-> Hash
(cost=13.52..13.52 rows=95 width=4)

->
Bitmap Heap Scan on budovy b (cost=2.33..13.52 rows=95 width=4)


Recheck Cond: (mesto_id = 12702)


-> Bitmap Index Scan on i_budovy_mesto_id (cost=0.00..2.33 rows=95
width=0)


Index Cond: (mesto_id = 12702)
->
Hash (cost=1058.65..1058.65
rows=24 width=24)

-> Nested Loop
(cost=43.05..1058.65 rows=24 width=24)

-> Index Scan using
i_x_zamestnanci_skupiny_zam_id on x_zamestnanci_skupiny x (cost=0.00..5.76

rows=1 width=4)

Index Cond: (19
= zamestnanci_id)

Filter:
(skupinyzamestnancu_id = 5)

-> Hash Join
(cost=43.05..1052.65 rows=24 width=24)

Hash Cond:
("outer".prostredky_id = "inner".id)

-> Bitmap Heap
Scan on diar d (cost=3.72..1012.15 rows=186 width=16)

Recheck
Cond: ((zamestnanci_id = 19) AND (zacatek >= 1139927357))

Filter:
((ukony_id = 0) AND (delka >= 1800))

->
Bitmap Index Scan on i_diar_zamestnanci_id_zacatek (cost=0.00..3.72
rows=287
width=0)


Index Cond: ((zamestnanci_id = 19) AND (zacatek >= 1139927357))

-> Hash
(cost=39.08..39.08 rows=99 width=12)

-> Hash
Join (cost=13.76..39.08 rows=99 width=12)


Hash Cond: ("outer".budovy_id = "inner".id)

->
Seq Scan on prostredky p (cost=0.00..20.54 rows=760 width=8)


Filter: (vhodnost_planovani = 0)

->
Hash (cost=13.52..13.52 rows=95 width=4)


-> Bitmap Heap Scan on budovy b (cost=2.33..13.52 rows=95 width=4)


Recheck Cond: (mesto_id = 12702)


-> Bitmap Index Scan on i_budovy_mesto_id (cost=0.00..2.33 rows=95
width=0)


Index Cond: (mesto_id = 12702)
-> Index Scan
using budovy_pkey on
budovy b (cost=0.00..4.91 rows=1 width=4)
Index
Cond: ("outer".budovy_id =
b.id)
Filter:
(mesto_id = 12702)
-> Index Scan using
i_prostredky_budovy_id
on prostredky p (cost=0.00..4.36 rows=1 width=8)
Index Cond:
(p.budovy_id = "outer".id)
Filter:
(vhodnost_planovani = 0)
-> Nested Loop
(cost=43.05..1058.65 rows=24
width=24)
-> Index Scan using
i_x_zamestnanci_skupiny_zam_id on x_zamestnanci_skupiny x (cost=0.00..5.76

rows=1 width=4)
Index Cond: (19 =
zamestnanci_id)
Filter:
(skupinyzamestnancu_id = 5)
-> Hash Join
(cost=43.05..1052.65 rows=24
width=24)
Hash Cond:
("outer".prostredky_id =
"inner".id)
-> Bitmap Heap
Scan on diar d
(cost=3.72..1012.15 rows=186 width=16)
Recheck
Cond: ((zamestnanci_id =
19) AND (zacatek >= 1139927357))
Filter:
((ukony_id = 0) AND
(delka >= 1800))
->
Bitmap Index Scan on
i_diar_zamestnanci_id_zacatek (cost=0.00..3.72 rows=287 width=0)

Index Cond:
((zamestnanci_id = 19) AND (zacatek >= 1139927357))
-> Hash
(cost=39.08..39.08 rows=99
width=12)
->
Hash Join (cost=13.76..39.08
rows=99 width=12)

Hash Cond:
("outer".budovy_id = "inner".id)

-> Seq Scan on prostredky
p (cost=0.00..20.54 rows=760 width=8)

Filter:
(vhodnost_planovani = 0)

-> Hash
(cost=13.52..13.52 rows=95 width=4)

-> Bitmap Heap Scan
on budovy b (cost=2.33..13.52 rows=95 width=4)

Recheck Cond:
(mesto_id = 12702)

-> Bitmap
Index Scan on i_budovy_mesto_id (cost=0.00..2.33 rows=95 width=0)

Index
Cond: (mesto_id = 12702)
-> Bitmap Heap Scan on diar d
(cost=22.48..26.50 rows=1
width=16)
Recheck Cond: ((d.zamestnanci_id =
777) AND
(d.zacatek >= 1139927357) AND (d.prostredky_id = "outer".id))
Filter: ((ukony_id = 0) AND (delka
>= 1800))
-> BitmapAnd (cost=22.48..22.48
rows=1 width=0)
-> Bitmap Index Scan on

i_diar_zamestnanci_id_zacatek (cost=0.00..3.72 rows=287 width=0)
Index Cond:
((zamestnanci_id = 777) AND
(zacatek >= 1139927357))
-> Bitmap Index Scan on
i_diar_prostredky_id
(cost=0.00..18.51 rows=3003 width=0)
Index Cond:
(d.prostredky_id =
"outer".id)
-> Index Scan using i_x_zamestnanci_skupiny_zam_id
on
x_zamestnanci_skupiny x (cost=0.00..5.76 rows=1 width=4)
Index Cond: (777 = zamestnanci_id)
Filter: (skupinyzamestnancu_id = 7)
(93 rows)

first inner select:
SELECT d.zamestnanci_id,d.prostredky_id,d.zacatek,d.delka,p.budovy_id FROM
diar AS d,prostredky AS p,budovy AS b,X_zamestnanci_skupiny AS x WHERE
x.skupinyzamestnancu_id=7 AND x.zamestnanci_id=d.zamestnanci_id AND
d.ukony_id=0 AND d.zamestnanci_id=777 AND d.zacatek>=1139927357 AND
d.delka>=1800 AND d.prostredky_id=p.id AND p.vhodnost_planovani=0 AND
p.budovy_id=b.id AND b.mesto_id=12702

explain:


QUERY PLAN
----------------------------------------------------------------------------
----------------------------------------------------------------------------
------
Nested Loop (cost=43.05..1058.65 rows=24 width=20) (actual
time=6.812..7.875
rows=59 loops=1)
-> Index Scan using i_x_zamestnanci_skupiny_zam_id on
x_zamestnanci_skupiny x (cost=0.00..5.76 rows=1 width=4) (actual
time=0.020..0.027 rows=1 loops=1)
Index Cond: (777 = zamestnanci_id)
Filter: (skupinyzamestnancu_id = 7)
-> Hash Join (cost=43.05..1052.65 rows=24 width=20) (actual
time=6.780..7.490 rows=59 loops=1)
Hash Cond: ("outer".prostredky_id = "inner".id)
-> Bitmap Heap Scan on diar d (cost=3.72..1012.15 rows=186

width=16) (actual time=0.104..0.455 rows=59 loops=1)
Recheck Cond: ((zamestnanci_id = 777) AND (zacatek >=

1139927357))
Filter: ((ukony_id = 0) AND (delka >= 1800))
-> Bitmap Index Scan on
i_diar_zamestnanci_id_zacatek
(cost=0.00..3.72 rows=287 width=0) (actual time=0.065..0.065 rows=157
loops=1)
Index Cond: ((zamestnanci_id = 777) AND
(zacatek >=
1139927357))
-> Hash (cost=39.08..39.08 rows=99 width=8) (actual
time=6.660..6.660 rows=142 loops=1)
-> Hash Join (cost=13.76..39.08 rows=99 width=8)
(actual
time=0.759..6.155 rows=142 loops=1)
Hash Cond: ("outer".budovy_id = "inner".id)
-> Seq Scan on prostredky p
(cost=0.00..20.54 rows=760
width=8) (actual time=0.006..2.651 rows=760 loops=1)
Filter: (vhodnost_planovani = 0)
-> Hash (cost=13.52..13.52 rows=95
width=4) (actual
time=0.730..0.730 rows=95 loops=1)
-> Bitmap Heap Scan on budovy b
(cost=2.33..13.52
rows=95 width=4) (actual time=0.045..0.420 rows=95 loops=1)
Recheck Cond: (mesto_id =
12702)
-> Bitmap Index Scan on
i_budovy_mesto_id
(cost=0.00..2.33 rows=95 width=0) (actual time=0.033..0.033 rows=95
loops=1)
Index Cond:
(mesto_id = 12702)
Total runtime: 8.165 ms
(22 rows)

returns :
zamestnanci_id | prostredky_id | zacatek | delka | budovy_id
----------------+---------------+------------+-------+-----------
777 | 587 | 1141380000 | 3600 |
342
777 | 555 | 1141201800 | 1800 |
1
777 | 587 | 1141034400 | 1800 |
342
777 | 13 | 1143036000 | 3600 |
1
777 | 13 | 1141732800 | 7200 |
1
777 | 13 | 1143027000 | 7200 |
1
777 | 587 | 1140170400 | 3600 |
342
777 | 499 | 1141385400 | 7200 |
342
777 | 587 | 1141639200 | 3600 |
342
777 | 499 | 1141644600 | 7200 |
342
777 | 13 | 1141817400 | 12600 |
1
777 | 13 | 1141903800 | 9000 |
1
777 | 587 | 1141984800 | 3600 |
342
777 | 499 | 1141990200 | 7200 |
342
777 | 587 | 1142244000 | 3600 |
342
777 | 499 | 1142249400 | 7200 |
342
777 | 13 | 1142508600 | 9000 |
1
777 | 587 | 1142589600 | 3600 |
342
777 | 499 | 1142595000 | 7200 |
342
777 | 587 | 1142848800 | 3600 |
342
777 | 499 | 1142854200 | 7200 |
342
777 | 13 | 1142940600 | 9000 |
1
777 | 13 | 1143113400 | 9000 |
1
777 | 499 | 1143189000 | 5400 |
342
777 | 587 | 1143194400 | 3600 |
342
777 | 499 | 1143199800 | 7200 |
342
777 | 499 | 1143444600 | 5400 |
342
777 | 587 | 1143450000 | 3600 |
342
777 | 499 | 1143455400 | 7200 |
342
777 | 13 | 1143541800 | 9000 |
1
777 | 13 | 1143628200 | 12600 |
1
777 | 13 | 1143714600 | 9000 |
1
777 | 499 | 1143790200 | 5400 |
342
777 | 587 | 1143795600 | 3600 |
342
777 | 499 | 1143801000 | 7200 |
342
777 | 13 | 1143529200 | 10800 |
1
777 | 13 | 1143619200 | 7200 |
1
777 | 555 | 1141801200 | 7200 |
1
777 | 555 | 1143010800 | 7200 |
1
777 | 555 | 1143612000 | 7200 |
1
777 | 499 | 1142242200 | 1800 |
342
777 | 499 | 1141637400 | 1800 |
342
777 | 13 | 1142328600 | 3600 |
1
777 | 499 | 1141981200 | 3600 |
342
777 | 13 | 1142931600 | 7200 |
1
777 | 499 | 1142584200 | 1800 |
342
777 | 499 | 1142587800 | 1800 |
342
777 | 13 | 1142499600 | 7200 |
1
777 | 13 | 1143021600 | 3600 |
1
777 | 555 | 1142406000 | 7200 |
1
777 | 13 | 1142416800 | 3600 |
1
777 | 13 | 1142335800 | 9000 |
1
777 | 499 | 1141045200 | 1800 |
342
777 | 499 | 1142843400 | 5400 |
342
777 | 499 | 1140175800 | 7200 |
342
777 | 13 | 1143702000 | 3600 |
1
777 | 13 | 1143707400 | 5400 |
1
777 | 13 | 1142422200 | 9000 |
1
777 | 13 | 1143102600 | 9000 |
1
(59 rows)

second, third, fourth inner select:
SELECT d.zamestnanci_id,d.prostredky_id,d.zacatek,d.delka,p.budovy_id FROM
diar AS d,prostredky AS p,budovy AS b,X_zamestnanci_skupiny AS x WHERE
x.skupinyzamestnancu_id=5 AND x.zamestnanci_id=d.zamestnanci_id AND
d.ukony_id=0 AND d.zamestnanci_id=19 AND d.zacatek>=1139927357 AND
d.delka>=1800 AND d.prostredky_id=p.id AND p.vhodnost_planovani=0 AND
p.budovy_id=b.id AND b.mesto_id=12702

explain:


QUERY PLAN
----------------------------------------------------------------------------
----------------------------------------------------------------------------
------
Nested Loop (cost=43.05..1058.65 rows=24 width=20) (actual
time=7.530..8.251
rows=42 loops=1)
-> Index Scan using i_x_zamestnanci_skupiny_zam_id on
x_zamestnanci_skupiny x (cost=0.00..5.76 rows=1 width=4) (actual
time=0.020..0.028 rows=1 loops=1)
Index Cond: (19 = zamestnanci_id)
Filter: (skupinyzamestnancu_id = 5)
-> Hash Join (cost=43.05..1052.65 rows=24 width=20) (actual
time=7.498..7.963 rows=42 loops=1)
Hash Cond: ("outer".prostredky_id = "inner".id)
-> Bitmap Heap Scan on diar d (cost=3.72..1012.15 rows=186

width=16) (actual time=0.057..0.257 rows=42 loops=1)
Recheck Cond: ((zamestnanci_id = 19) AND (zacatek >=

1139927357))
Filter: ((ukony_id = 0) AND (delka >= 1800))
-> Bitmap Index Scan on
i_diar_zamestnanci_id_zacatek
(cost=0.00..3.72 rows=287 width=0) (actual time=0.038..0.038 rows=70
loops=1)
Index Cond: ((zamestnanci_id = 19) AND
(zacatek >=
1139927357))
-> Hash (cost=39.08..39.08 rows=99 width=8) (actual
time=7.419..7.419 rows=142 loops=1)
-> Hash Join (cost=13.76..39.08 rows=99 width=8)
(actual
time=0.714..6.944 rows=142 loops=1)
Hash Cond: ("outer".budovy_id = "inner".id)
-> Seq Scan on prostredky p
(cost=0.00..20.54 rows=760
width=8) (actual time=0.006..3.482 rows=760 loops=1)
Filter: (vhodnost_planovani = 0)
-> Hash (cost=13.52..13.52 rows=95
width=4) (actual
time=0.687..0.687 rows=95 loops=1)
-> Bitmap Heap Scan on budovy b
(cost=2.33..13.52
rows=95 width=4) (actual time=0.043..0.366 rows=95 loops=1)
Recheck Cond: (mesto_id =
12702)
-> Bitmap Index Scan on
i_budovy_mesto_id
(cost=0.00..2.33 rows=95 width=0) (actual time=0.032..0.032 rows=95
loops=1)
Index Cond:
(mesto_id = 12702)
Total runtime: 8.485 ms
(22 rows)

each returns:
zamestnanci_id | prostredky_id | zacatek | delka | budovy_id
----------------+---------------+------------+-------+-----------
19 | 482 | 1141111800 | 12600 |
1
19 | 482 | 1140166800 | 3600 |
1
19 | 482 | 1140678000 | 14400 |
1
19 | 482 | 1142406000 | 5400 |
1
19 | 482 | 1142413200 | 7200 |
1
19 | 482 | 1142578800 | 1800 |
1
19 | 482 | 1142582400 | 10800 |
1
19 | 482 | 1140073200 | 1800 |
1
19 | 482 | 1141282800 | 14400 |
1
19 | 482 | 1141801200 | 14400 |
1
19 | 482 | 1141887600 | 14400 |
1
19 | 482 | 1142233200 | 14400 |
1
19 | 482 | 1142319600 | 14400 |
1
19 | 482 | 1142492400 | 14400 |
1
19 | 482 | 1142838000 | 14400 |
1
19 | 482 | 1142924400 | 14400 |
1
19 | 482 | 1143010800 | 14400 |
1
19 | 482 | 1143097200 | 14400 |
1
19 | 482 | 1143183600 | 14400 |
1
19 | 482 | 1143439200 | 14400 |
1
19 | 482 | 1143525600 | 14400 |
1
19 | 482 | 1143612000 | 14400 |
1
19 | 482 | 1143698400 | 14400 |
1
19 | 482 | 1143784800 | 14400 |
1
19 | 482 | 1141977600 | 10800 |
1
19 | 482 | 1141714800 | 12600 |
1
19 | 482 | 1140764400 | 7200 |
1
19 | 482 | 1140775200 | 3600 |
1
19 | 482 | 1141374600 | 9000 |
1
19 | 482 | 1140505200 | 1800 |
1
19 | 482 | 1140508800 | 10800 |
1
19 | 482 | 1141029000 | 9000 |
1
19 | 482 | 1139995800 | 5400 |
1
19 | 482 | 1140424200 | 9000 |
1
19 | 482 | 1140598800 | 7200 |
1
19 | 482 | 1140172200 | 1800 |
1
19 | 482 | 1141196400 | 5400 |
1
19 | 482 | 1141204500 | 6300 |
1
19 | 482 | 1141628400 | 1800 |
1
19 | 482 | 1141632000 | 10800 |
1
19 | 482 | 1140078600 | 9000 |
1
19 | 482 | 1140591600 | 1800 |
1
(42 rows)

when you create tables d0 as first inner select, d1 as second inner select,
d2
as third inner select, d3 as fourth select and run query with where
condition
select * from d0, d1, d2, d3 WHERE d1.zacatek<=(d0.zacatek+-257400) AND
(d1.zacatek+d1.delka)>=(d0.zacatek+-255600) AND d0.budovy_id=d1.budovy_id
AND
d2.zacatek<=(d0.zacatek+-255600) AND
(d2.zacatek+d2.delka)>=(d0.zacatek+-253800) AND d0.budovy_id=d2.budovy_id
AND
d3.zacatek<=(d0.zacatek+-253800) AND
(d3.zacatek+d3.delka)>=(d0.zacatek+-252000) AND d0.budovy_id=d3.budovy_id
ORDER BY d0.zacatek LIMIT 5;

you got 3 rows

but if you put together never returns (i think that it take ages)