Performance bricht abrupt ein bei großen Ergebnismengen

Hi Leute,

wahrscheinlich habe ich irgend etwas grundlegendes übersehen, aber
vielleicht kann mir jemand auf die Sprünge helfen.

Ich hab hier eine Datenbank mit einigen recht großen Tabellen (einige
zig Millionen Einträge) und benötige Abfragen, die recht recht große
Ergebnismengen liefern werden (einige 100000 bis Millionen Einträge),
zudem möchte ich Views über diese Tabellen zur Verfügung stellen. Das
funktioniert bis zu einer gewissen Größe ziemlich passabel, aber es
scheint eine ziemlich harte Grenze zu geben, bei der die Geschwindigkeit
abrupt einbricht.

Warum ist das so und was kann man dagegen tun?

Ein Beispiel. Zwei Tabellen, wobei die erste mehrere Fremdschlüssel auf
die zweite hat:

Tabelle 1 (derzeit ca. 1,4 Millionen Einträge):

CREATE TABLE vquest_aa
(
id bigint NOT NULL DEFAULT nextval('vquest_aa_id_seq'::regclass),
sequence_id character varying(80) NOT NULL,
vdj bigint,
vregion bigint,
fr1_imgt bigint,

-- some fields omitted for clarity...

entrydate timestamp without time zone NOT NULL DEFAULT now(),

CONSTRAINT vquest_aa_pkey PRIMARY KEY (id),

CONSTRAINT vquest_aa_fr1_imgt_fkey FOREIGN KEY (fr1_imgt)
REFERENCES sequences (id) MATCH SIMPLE
ON UPDATE NO ACTION ON DELETE CASCADE,

--more constraints omitted for clarity

CONSTRAINT vquest_aa_vdj_fkey FOREIGN KEY (vdj)
REFERENCES sequences (id) MATCH SIMPLE
ON UPDATE NO ACTION ON DELETE CASCADE,
CONSTRAINT vquest_aa_vregion_fkey FOREIGN KEY (vregion)
REFERENCES sequences (id) MATCH SIMPLE
ON UPDATE NO ACTION ON DELETE CASCADE,
CONSTRAINT vquest_aa_sequence_id_key UNIQUE (sequence_id)
),

Tabelle 2 (derzeit ca. 22 Millionen Einträge):

CREATE TABLE sequences
(
id bigserial NOT NULL,
entrydate timestamp with time zone DEFAULT now(),

"type" character varying(3) NOT NULL DEFAULT 'DNA'::character varying,
seq character varying(10485759) NOT NULL,

CONSTRAINT biosequences_pkey PRIMARY KEY (id),

CONSTRAINT biosequences_type_check CHECK (type::text = 'DNA'::text OR
type::text = 'PEP'::text)
)
WITH (
OIDS=FALSE
);

Eine Query über diese beiden Tabellen, man beachte das "Limit XXX":

with aa as (select vquest_aa.sequence_id, vdj,
vregion, fr1_imgt (...omitted...)
from vquest_aa limit XXX) select
sequence_id, s1.seq as vdj_seq, s2.seq as vregion_seq,
s3.seq as fr1_seq (...omitted...)
from aa left outer join sequences as s1 on s1.id = vdj
left outer join sequences as s2 on s2.id = vregion
left outer join sequences as s3 on s3.id = fr1_imgt
(...omitted...)

Wenn man das mit verschiedenen Werten für Limit XXX ausführt kommt man
zu folgenden Laufzeiten:
---------------------------
result set size (by Limit) query execution time in ms rows per ms

1 32 0,03
10 31 0,32
100 31 3,23
500 78 6,41
1000 141 7,09
10000 1656 6,04
20000 5327 3,75
50000 9593 5,21
100000 14779 6,77
110000 18232 6,03
115000 19784 5,81
117000 22597 5,18
118000 89717 1,32
119000 70435 1,69
119500 179472 0,67
120000 cancelled after 300000ms n.d.
200000 cancelled after 300000ms n.d.
-----------------------------

Irgendwo bei 120000 bricht die Geschwindigkeit dramatisch ein, das
passiert je nach Komplexität der Abfragen bei unterschiedlichen
"Grenzwerten" und auch dann, wenn man ein praxisnäheres Auswahlkriterium
benutzt als "Limit".

OK, woran liegt dieses Verhalten, was kann man dagegen tun?

Bin für jeden Tipp dankbar.

Viele Grüße, V. Sievert

--
Volker Sievert
AG Konthur
Max Planck Institute for Molecular Genetics
Department of Vertebrate Genomics (Prof. H. Lehrach)
Ihnestr.63, 14195 Berlin, Germany
Tel.: +49/30/ 8413-1578
Fax.: +49/30/ 8413-1718 or -1365
sievert(at)molgen(dot)mpg(dot)de
http://www.molgen.mpg.de/~in-vitro/