Slow join query optimisation?

From: Douglas Thomson <dougt(at)mugc(dot)cc(dot)monash(dot)edu(dot)au>
To: pgsql-interfaces(at)postgreSQL(dot)org
Subject: Slow join query optimisation?
Date: 1999-11-27 02:12:54
Message-ID: 199911270212.NAA10098@mugca.cc.monash.edu.au
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-interfaces

I am trying to execute a moderately complex join to combine student
enrolment data with the various tables that define the foreign keys
used by the enrolment table. Here is a sample SELECT statement:
SELECT
users.name,
subjects.canonical,
periods.description,
courses.description,
campuses.description,
studyModes.description
FROM
t25 agents,
t27 offerings,
t30 enrolments,
t26 subjects,
t29 periods,
t28 courses,
t23 campuses,
t21 studyModes,
t24 users
WHERE
agents.agent='/Subjects/1999/sem1/GCO/1812' AND
offerings.masterPeriod=agents.period AND
offerings.masterSubject=agents.subject AND
enrolments.offeringPeriod=offerings.period AND
enrolments.offeringSubject=offerings.subject AND
subjects.subject=enrolments.offeringSubject AND
periods.period=enrolments.offeringPeriod AND
courses.course=enrolments.course AND
campuses.campus=enrolments.campus AND
studyModes.studyMode=enrolments.studyMode AND
users.studentID=enrolments.studentID;

This seems to execute unusually slowly, regardless of how little data
may be in the tables. The time is all in the backend. It takes almost
a second (PII 333MHz, 128M RAM, repeated test so no disk I/O involved)
even with all empty tables.

However, as I just slightly simplify the query (by removing all
reference to one table) the time drops:
11 tables: 6.97s
10 tables: 2.47s
9 tables: 0.99s (this is the SELECT shown above)
8 tables: 0.39s
7 tables: 0.19s
6 tables: 0.12s
5 tables: 0.09s

It seems to make no difference which tables I remove; the issue seems
to be the total number of tables that I am joining. If it matters, all
the tables have indexes on the combinations of attributes used in my
WHERE clause.

My question for the list: Is there something in the query optimiser
that will take a time that is something like exponential on the number
of tables being joined?

And if so, is there any way to get around it (other than using
several smaller selects and combining the data myself or
denormalising my tables)?

Doug.

P.S. I am using version 6.5.1, but I couldn't see anything in the
HISTORY for 6.5.3 that sounded likely to affect this particular
issue...

Browse pgsql-interfaces by date

  From Date Subject
Next Message Tom Lane 1999-11-27 05:36:41 Re: [INTERFACES] Slow join query optimisation?
Previous Message Oscar Serrano 1999-11-26 19:29:21 RE: [INTERFACES] Spanish format on date and numbers