Materializing a sequential scan

Hi,

I'm using PostgreSQL 8.1 beta 3 (packages from Debian experimental), and I
have a (rather complex) query that seems to take forever -- when the database
was just installed, it took about 1200ms (which is quite good, considering
that the 7.4 system this runs on today uses about the same time, but has
twice as much CPU power and runs sequential scans up to eight times as fast),
but now I can never even get it to complete. I've tried running it for half
an hour, but it still doesn't complete, so I'm a bit unsure what's going on.

There's a _lot_ of tables and views in here, several hundres lines of SQL,
but experience tells me that posting more is better than posting less, so
here goes. (The data is unfortunately not public since it contains PIN codes
and such, but if anybody asks I can probably send it off-list. It's ~30MB in
plain pg_dump, though.) There might be a few tables that aren't referenced,
but I don't really know a good way to figure out such dependencies
automatically, and I'd guess most of them _are_ used :-) Apologies in advance
for the Norwegian in the names.

=== cut here ===

CREATE TABLE gruppetype (
gruppetype_id integer NOT NULL PRIMARY KEY,
gruppetype varchar
);
CREATE TABLE gruppe (
gruppe_id serial NOT NULL PRIMARY KEY,
gruppe varchar NOT NULL,
beskrivelse varchar,
gruppetype_id integer DEFAULT 1 NOT NULL REFERENCES gruppetype,
adminacl varchar,
aktiv boolean default 't' NOT NULL
);
CREATE TABLE adgangsskjema (
adgangsskjema_id serial NOT NULL PRIMARY KEY,
navn varchar NOT NULL,
rita_navn varchar NOT NULL
);
CREATE TABLE adgangsskjema_gruppe_kobling (
gruppe_id integer NOT NULL REFERENCES gruppe (gruppe_id),
adgangsskjema_id integer NOT NULL REFERENCES adgangsskjema (adgangsskjema_id),
PRIMARY KEY (adgangsskjema_id, gruppe_id)
);
CREATE TABLE kortstatus (
kortstatus_id smallint NOT NULL PRIMARY KEY,
kortstatus varchar
);
CREATE TABLE korttype (
korttype_id serial NOT NULL PRIMARY KEY,
korttype varchar NOT NULL,
beskrivelse varchar
);
CREATE TABLE medlemstatus (
medlemstatus_id serial NOT NULL PRIMARY KEY,
medlemstatus varchar NOT NULL,
beskrivelse varchar
);
CREATE TABLE oblattype (
oblattype_id serial NOT NULL PRIMARY KEY,
oblattype varchar NOT NULL,
varighet interval NOT NULL
);
CREATE TABLE skole (
skole_id serial NOT NULL PRIMARY KEY,
skole varchar NOT NULL,
beskrivelse varchar
);
CREATE TABLE studie (
studie_id serial NOT NULL PRIMARY KEY,
studie varchar NOT NULL,
beskrivelse varchar
);
CREATE TABLE poststed (
postnummer smallint NOT NULL PRIMARY KEY CHECK (postnummer >= 0 AND postnummer <= 9999),
poststed varchar
);
CREATE TABLE gruppekobling (
overgruppe_id integer NOT NULL REFERENCES gruppe (gruppe_id),
undergruppe_id integer NOT NULL REFERENCES gruppe (gruppe_id),
PRIMARY KEY (overgruppe_id, undergruppe_id)
);
CREATE TABLE medlem (
medlem_id serial NOT NULL PRIMARY KEY CHECK (medlem_id > 0),
fornavn varchar NOT NULL,
etternavn varchar NOT NULL,
hjemadresse varchar,
hjem_postnummer smallint REFERENCES poststed (postnummer),
studieadresse varchar,
studie_postnummer smallint REFERENCES poststed (postnummer),
fodselsdato date,
telefon varchar,
mail varchar UNIQUE,
passord character(32) NOT NULL,
registrert date DEFAULT now(),
oppdatert date DEFAULT now(),
skole_id integer REFERENCES skole,
studie_id integer REFERENCES studie,
medlemstatus_id integer DEFAULT 1 NOT NULL REFERENCES medlemstatus,
pinkode smallint CHECK ((pinkode >= 0 AND pinkode <= 9999) OR pinkode IS NULL),
UNIQUE ( LOWER(mail) )
);
CREATE TABLE kort (
kortnummer integer NOT NULL PRIMARY KEY CHECK (kortnummer > 0),
medlem_id integer REFERENCES medlem DEFERRABLE,
korttype_id integer DEFAULT 1 NOT NULL REFERENCES korttype,
serie_registrert date DEFAULT now() NOT NULL,
bruker_registrert date,
kortstatus_id integer DEFAULT 1 NOT NULL REFERENCES kortstatus
);
CREATE TABLE oblat (
oblatnummer integer NOT NULL PRIMARY KEY CHECK (oblatnummer > 0),
oblattype_id integer NOT NULL REFERENCES oblattype,
"start" date NOT NULL,
kortnummer integer REFERENCES kort,
bruker_registrert date,
serie_registrert date DEFAULT NOW() NOT NULL
);
CREATE TABLE verv (
medlem_id integer NOT NULL REFERENCES medlem,
gruppe_id integer NOT NULL REFERENCES gruppe,
"start" date DEFAULT now() NOT NULL,
stopp date,

CHECK ( stopp >= start ),
PRIMARY KEY ( medlem_id, gruppe_id, "start" )
);
CREATE TABLE nytt_passord (
medlem_id integer NOT NULL REFERENCES medlem,
hash varchar NOT NULL,
tidspunkt date DEFAULT now() NOT NULL
);
CREATE VIEW gyldige_medlemskap AS
SELECT medlem_id,MAX("start"+varighet) AS stopp
FROM kort
JOIN oblat ON kort.kortnummer=oblat.kortnummer
NATURAL JOIN oblattype
WHERE kortstatus_id=1
AND medlem_id IS NOT NULL
GROUP BY medlem_id
HAVING MAX("start"+varighet) >= current_date;

CREATE SCHEMA kortsys2;

CREATE FUNCTION kortsys2.effektiv_dato(date) RETURNS date
AS
'SELECT CASE WHEN $1 < CURRENT_DATE THEN CURRENT_DATE ELSE $1 END'
LANGUAGE SQL STABLE;

CREATE VIEW kortsys2.mdb_personer AS
SELECT * FROM (
SELECT DISTINCT ON (medlem_id) medlem_id,fornavn,etternavn,mail,pinkode,kort.kortnummer AS kortnummer
FROM medlem
NATURAL JOIN kort -- the member must have an ID card
WHERE
kortstatus_id=1 -- the card must be active
AND korttype_id IN (2,3) -- the card must be an ID card or UKA ID card
AND pinkode IS NOT NULL -- the member must have a PIN
AND medlem_id IN ( -- the member must be active in at least one group
SELECT medlem_id
FROM verv
WHERE stopp IS NULL OR stopp >= current_date
)
AND medlem_id IN ( -- the member must have a valid membership
SELECT medlem_id FROM gyldige_medlemskap
)
ORDER BY
medlem_id, -- needed for the DISTINCT
korttype_id -- prioritize ID cards over UKA ID cards
) AS t1
UNION ALL
SELECT * FROM eksterne_kort.eksterne_personer;

CREATE TABLE kortsys2.rita_personer (
medlem_id integer PRIMARY KEY NOT NULL,
fornavn varchar NOT NULL,
etternavn varchar NOT NULL,
mail varchar NOT NULL,
pinkode smallint NOT NULL CHECK (pinkode >= 0 AND pinkode <= 9999),
kortnummer integer UNIQUE NOT NULL
);
CREATE TABLE kortsys2.personer_tving_sletting (
medlem_id integer PRIMARY KEY NOT NULL
);
CREATE VIEW kortsys2.personer_skal_slettes AS
SELECT medlem_id
FROM kortsys2.rita_personer
WHERE (medlem_id,pinkode,kortnummer) NOT IN (
SELECT medlem_id,pinkode,kortnummer
FROM kortsys2.mdb_personer
)
UNION
SELECT medlem_id
FROM kortsys2.personer_tving_sletting;

CREATE TABLE kortsys2.personer_nylig_slettet (
medlem_id integer PRIMARY KEY NOT NULL
);

CREATE VIEW kortsys2.personer_skal_eksporteres AS
SELECT *
FROM kortsys2.mdb_personer
WHERE medlem_id NOT IN (
SELECT medlem_id FROM kortsys2.rita_personer
)
AND medlem_id NOT IN (
SELECT medlem_id FROM kortsys2.personer_nylig_slettet
);

CREATE TABLE kortsys2.mdb_gruppekobling_temp (
overgruppe_id INTEGER NOT NULL,
undergruppe_id INTEGER NOT NULL
);

CREATE OR REPLACE FUNCTION kortsys2.mdb_gruppekobling_transitiv_tillukning() RETURNS SETOF gruppekobling AS
'
DECLARE
r RECORD;
BEGIN
INSERT INTO kortsys2.mdb_gruppekobling_temp
SELECT overgruppe_id,undergruppe_id FROM gruppekobling gk
JOIN gruppe g1 ON gk.overgruppe_id=g1.gruppe_id
JOIN gruppe g2 ON gk.overgruppe_id=g2.gruppe_id
WHERE g1.aktiv AND g2.aktiv;
LOOP
INSERT INTO kortsys2.mdb_gruppekobling_temp
SELECT g1.overgruppe_id, g2.undergruppe_id
FROM kortsys2.mdb_gruppekobling_temp g1
JOIN kortsys2.mdb_gruppekobling_temp g2
ON g1.undergruppe_id=g2.overgruppe_id
WHERE (g1.overgruppe_id, g2.undergruppe_id) NOT IN (
SELECT * FROM kortsys2.mdb_gruppekobling_temp
);
EXIT WHEN NOT FOUND;
END LOOP;
FOR r IN SELECT * from kortsys2.mdb_gruppekobling_temp LOOP
RETURN NEXT r;
END LOOP;
DELETE FROM kortsys2.mdb_gruppekobling_temp;
RETURN;
END;
' LANGUAGE plpgsql;

CREATE VIEW kortsys2.mdb_gruppetilgang AS
SELECT DISTINCT
gk.undergruppe_id AS gruppe_id,
rita_navn
FROM (
SELECT * FROM mdb_gruppekobling_transitiv_tillukning()
UNION SELECT gruppe_id,gruppe_id FROM gruppe WHERE aktiv
) gk
JOIN adgangsskjema_gruppe_kobling ak ON gk.overgruppe_id=ak.gruppe_id
NATURAL JOIN adgangsskjema;

CREATE VIEW kortsys2.mdb_tilgang AS
SELECT
t1.medlem_id AS medlem_id,
rita_navn,
"start",
CASE WHEN m_stopp < stopp OR stopp IS NULL THEN m_stopp ELSE stopp END AS stopp
FROM (
SELECT
medlem_id,
gruppe_id,
ms.stopp AS m_stopp,
MIN("start") AS start,
MAX(v.stopp) AS stopp
FROM (
SELECT * FROM verv
UNION ALL
SELECT * FROM eksterne_kort.vervekvivalens
) v
JOIN (
SELECT * FROM gyldige_medlemskap ms
UNION ALL
SELECT medlem_id,stopp FROM eksterne_kort.vervekvivalens
) ms
USING (medlem_id)

WHERE ( v.stopp IS NULL OR v.stopp >= current_date )
GROUP BY medlem_id,gruppe_id,ms.stopp
) t1
JOIN mdb_gruppetilgang gt ON t1.gruppe_id=gt.gruppe_id
WHERE medlem_id IN (
SELECT medlem_id FROM mdb_personer
)
;

CREATE VIEW kortsys2.mdb_effektiv_tilgang AS
SELECT
medlem_id,
rita_navn,
MIN("start") AS "start",
MAX(stopp) AS stopp
FROM kortsys2.mdb_tilgang
GROUP BY medlem_id,rita_navn
HAVING MAX(stopp) >= current_date;

CREATE TABLE kortsys2.rita_tilgang (
medlem_id integer NOT NULL REFERENCES kortsys2.rita_personer,
rita_navn varchar NOT NULL,
"start" date NOT NULL,
stopp date NOT NULL,

PRIMARY KEY ( medlem_id, rita_navn )
);

CREATE VIEW kortsys2.tilganger_skal_slettes AS
SELECT * FROM kortsys2.rita_tilgang
WHERE medlem_id NOT IN (
SELECT medlem_id FROM kortsys2.personer_nylig_slettet
)
AND (medlem_id,rita_navn,kortsys2.effektiv_dato("start"),stopp) NOT IN (
SELECT medlem_id,rita_navn,kortsys2.effektiv_dato("start"),stopp FROM kortsys2.mdb_effektiv_tilgang
);

CREATE VIEW kortsys2.tilganger_skal_gis AS
SELECT medlem_id,rita_navn,"start",stopp
FROM kortsys2.mdb_effektiv_tilgang
WHERE medlem_id NOT IN (
SELECT medlem_id FROM kortsys2.personer_nylig_slettet
)
AND (medlem_id,rita_navn,kortsys2.effektiv_dato("start"),stopp) NOT IN (
SELECT medlem_id,rita_navn,kortsys2.effektiv_dato("start"),stopp FROM kortsys2.rita_tilgang
);

=== cut here ===

Now for the simple query:

mdb2_jodal=# explain select * from kortsys2.tilganger_skal_gis ;

and the monster of a query plan (no EXPLAIN ANALYZE because, well, it never
finishes):
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Subquery Scan mdb_effektiv_tilgang (cost=19821.69..4920621.69 rows=10000 width=48)
Filter: ((NOT (hashed subplan)) AND (NOT (subplan)))
-> HashAggregate (cost=19238.48..20838.48 rows=40000 width=52)
Filter: (max(CASE WHEN ((m_stopp < (stopp)::timestamp without time zone) OR (stopp IS NULL)) THEN m_stopp ELSE (stopp)::timestamp without time zone END) >= (('now'::text)::date)::timestamp without time zone)
-> Merge Join (cost=12231.86..16091.27 rows=251777 width=52)
Merge Cond: ("outer".gruppe_id = "inner".gruppe_id)
-> Unique (cost=483.64..514.68 rows=4138 width=30)
-> Sort (cost=483.64..493.99 rows=4138 width=30)
Sort Key: gk.undergruppe_id, adgangsskjema.rita_navn
-> Merge Join (cost=149.81..235.06 rows=4138 width=30)
Merge Cond: ("outer".overgruppe_id = "inner".gruppe_id)
-> Unique (cost=92.52..101.21 rows=1159 width=8)
-> Sort (cost=92.52..95.41 rows=1159 width=8)
Sort Key: overgruppe_id, undergruppe_id
-> Append (cost=0.00..33.53 rows=1159 width=8)
-> Function Scan on mdb_gruppekobling_transitiv_tillukning (cost=0.00..12.50 rows=1000 width=8)
-> Seq Scan on gruppe (cost=0.00..9.44 rows=159 width=4)
Filter: aktiv
-> Sort (cost=57.29..59.08 rows=714 width=30)
Sort Key: ak.gruppe_id
-> Hash Join (cost=1.60..23.45 rows=714 width=30)
Hash Cond: ("outer".adgangsskjema_id = "inner".adgangsskjema_id)
-> Seq Scan on adgangsskjema_gruppe_kobling ak (cost=0.00..11.14 rows=714 width=8)
-> Hash (cost=1.48..1.48 rows=48 width=30)
-> Seq Scan on adgangsskjema (cost=0.00..1.48 rows=48 width=30)
-> Sort (cost=11748.21..11778.64 rows=12169 width=24)
Sort Key: t1.gruppe_id
-> Hash Join (cost=8975.45..10922.49 rows=12169 width=24)
Hash Cond: ("outer".medlem_id = "inner".medlem_id)
-> HashAggregate (cost=5180.87..6093.55 rows=60845 width=24)
-> Merge Join (cost=3496.19..4420.31 rows=60845 width=24)
Merge Cond: ("outer".medlem_id = "inner".medlem_id)
-> Sort (cost=2743.39..2749.11 rows=2290 width=12)
Sort Key: ms.medlem_id
-> Subquery Scan ms (cost=2483.70..2615.60 rows=2290 width=12)
-> Append (cost=2483.70..2592.70 rows=2290 width=12)
-> HashAggregate (cost=2483.70..2545.82 rows=2259 width=24)
Filter: (max(("start" + varighet)) >= (('now'::text)::date)::timestamp without time zone)
-> Hash Join (cost=662.54..2427.49 rows=7494 width=24)
Hash Cond: ("outer".oblattype_id = "inner".oblattype_id)
-> Hash Join (cost=661.50..2314.03 rows=7494 width=12)
Hash Cond: ("outer".kortnummer = "inner".kortnummer)
-> Seq Scan on oblat (cost=0.00..632.17 rows=37817 width=12)
-> Hash (cost=614.81..614.81 rows=18673 width=8)
-> Seq Scan on kort (cost=0.00..614.81 rows=18673 width=8)
Filter: ((kortstatus_id = 1) AND (medlem_id IS NOT NULL))
-> Hash (cost=1.04..1.04 rows=4 width=20)
-> Seq Scan on oblattype (cost=0.00..1.04 rows=4 width=20)
-> Subquery Scan "*SELECT* 2" (cost=0.00..1.70 rows=31 width=4)
-> Seq Scan on eksterne_kort (cost=0.00..1.39 rows=31 width=4)
-> Sort (cost=752.80..766.08 rows=5314 width=16)
Sort Key: v.medlem_id
-> Append (cost=0.00..370.84 rows=5314 width=16)
-> Seq Scan on verv (cost=0.00..316.31 rows=5283 width=16)
Filter: ((stopp IS NULL) OR (stopp >= ('now'::text)::date))
-> Subquery Scan "*SELECT* 2" (cost=0.01..1.70 rows=31 width=8)
-> Result (cost=0.01..1.39 rows=31 width=8)
One-Time Filter: (('2030-01-01'::date IS NULL) OR ('2030-01-01'::date >= ('now'::text)::date))
-> Seq Scan on eksterne_kort (cost=0.00..1.31 rows=31 width=8)
-> Hash (cost=3794.48..3794.48 rows=40 width=4)
-> HashAggregate (cost=3794.08..3794.48 rows=40 width=4)
-> Append (cost=3791.65..3793.58 rows=40 width=106)
-> Subquery Scan t1 (cost=3791.65..3791.79 rows=9 width=106)
-> Unique (cost=3791.65..3791.70 rows=9 width=60)
-> Sort (cost=3791.65..3791.68 rows=9 width=60)
Sort Key: medlem.medlem_id, public.kort.korttype_id
-> Nested Loop (cost=2922.47..3791.51 rows=9 width=60)
Join Filter: ("outer".medlem_id = "inner".medlem_id)
-> Hash Join (cost=2918.46..3454.13 rows=42 width=60)
Hash Cond: ("outer".medlem_id = "inner".medlem_id)
-> Hash Join (cost=2574.06..3106.62 rows=538 width=56)
Hash Cond: ("outer".medlem_id = "inner".medlem_id)
-> Seq Scan on medlem (cost=0.00..500.01 rows=3623 width=52)
Filter: (pinkode IS NOT NULL)
-> Hash (cost=2568.41..2568.41 rows=2259 width=4)
-> HashAggregate (cost=2483.70..2545.82 rows=2259 width=24)
Filter: (max(("start" + varighet)) >= (('now'::text)::date)::timestamp without time zone)
-> Hash Join (cost=662.54..2427.49 rows=7494 width=24)
Hash Cond: ("outer".oblattype_id = "inner".oblattype_id)
-> Hash Join (cost=661.50..2314.03 rows=7494 width=12)
Hash Cond: ("outer".kortnummer = "inner".kortnummer)
-> Seq Scan on oblat (cost=0.00..632.17 rows=37817 width=12)
-> Hash (cost=614.81..614.81 rows=18673 width=8)
-> Seq Scan on kort (cost=0.00..614.81 rows=18673 width=8)
Filter: ((kortstatus_id = 1) AND (medlem_id IS NOT NULL))
-> Hash (cost=1.04..1.04 rows=4 width=20)
-> Seq Scan on oblattype (cost=0.00..1.04 rows=4 width=20)
-> Hash (cost=341.42..341.42 rows=1191 width=4)
-> HashAggregate (cost=329.51..341.42 rows=1191 width=4)
-> Seq Scan on verv (cost=0.00..316.31 rows=5283 width=4)
Filter: ((stopp IS NULL) OR (stopp >= ('now'::text)::date))
-> Bitmap Heap Scan on kort (cost=4.01..8.02 rows=1 width=12)
Recheck Cond: ((("outer".medlem_id = kort.medlem_id) AND (kort.korttype_id = 2)) OR (("outer".medlem_id = kort.medlem_id) AND (kort.korttype_id = 3)))
Filter: (kortstatus_id = 1)
-> BitmapOr (cost=4.01..4.01 rows=1 width=0)
-> Bitmap Index Scan on maksimalt_ett_aktivt_kort_per_medlem (cost=0.00..2.01 rows=1 width=0)
Index Cond: (("outer".medlem_id = kort.medlem_id) AND (kort.korttype_id = 2))
-> Bitmap Index Scan on maksimalt_ett_aktivt_kort_per_medlem (cost=0.00..2.01 rows=1 width=0)
Index Cond: (("outer".medlem_id = kort.medlem_id) AND (kort.korttype_id = 3))
-> Subquery Scan "*SELECT* 2" (cost=0.00..1.70 rows=31 width=25)
-> Seq Scan on eksterne_kort (cost=0.00..1.39 rows=31 width=25)
SubPlan
-> Materialize (cost=546.45..742.37 rows=19592 width=38)
-> Seq Scan on rita_tilgang (cost=0.00..526.86 rows=19592 width=38)
-> Seq Scan on personer_nylig_slettet (cost=0.00..31.40 rows=2140 width=4)
(105 rows)

There's two oddities here at first sight:

1. Why does it materialize the sequential scan? What use would that have?
2. Why does it estimate four million disk page fetches in the top node?
I can't find anything like that in the bottom nodes...

All the obvious things are taken care of: The tables are freshly loaded,
VACUUM ANALYZE just ran, sort_mem/shared_buffers/effective_cache_size is the
same as on the 7.4 machine with the same amount of RAM (1GB).

/* Steinar */
--
Homepage: http://www.sesse.net/