Re: Controlling complexity in queries

From: Alban Hertroys <haramrae(at)gmail(dot)com>
To: Jay Levitt <jay(dot)levitt(at)gmail(dot)com>
Cc: Merlin Moncure <mmoncure(at)gmail(dot)com>, Craig Ringer <ringerc(at)ringerc(dot)id(dot)au>, David Johnston <polobo(at)yahoo(dot)com>, Robert James <srobertjames(at)gmail(dot)com>, Postgres General <pgsql-general(at)postgresql(dot)org>
Subject: Re: Controlling complexity in queries
Date: 2011-12-14 22:24:18
Message-ID: D9F50FCD-1619-4EB6-AFEC-CCEA753D053F@gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-general

>>> [1] Since this is my current favorite problem, the pathological case is:
>>>
>>> select questions.id
>>> from questions
>>> join (
>>> select u.id
>>> from users as u
>>> group by u.id
>>> ) as s
>>> on s.id = questions.user_id
>>> where questions.id = 1;
>>>
>>> With users.id as a primary key, it's obvious that this can return only one
>>> row, but it has to scan the users table to get there. See the "Subjquery in
>>> a JOIN not getting restricted?" thread on pgsql-performance for Tom's
>>> explanation of why that's a hard problem to solve.
>>
>> Yeah -- here and there you run into difficult to optimize queries.
>> (For my part, I'd just have converted that to WHERE EXISTS for the
>> semi-join).
>
> I think I'm about to learn a very important relational-algebra equivalence... could you elaborate?

You could write that as:

select questions.id
from questions as q
where exists (select 1 from users as u where u.id = q.user_id)
and questions.id = 1;

That's basically what you are doing, checking that a user with a given id from the questions table exists in the users table. Writing it as WHERE EXISTS is a matter of "phrasing the question" more accurately, which gives the query planner a hint that for your answer a single hit is sufficient - no need to check whether there are other matches after the first one.

That said, wouldn't a foreign key constraint help you even better? If questions.user_id is required to refer to an existing users.id (by an FK constraint), than the check in the query becomes moot.

Alban Hertroys

--
Screwing up is an excellent way to attach something to the ceiling.

In response to

Responses

Browse pgsql-general by date

  From Date Subject
Next Message Leif Biberg Kristensen 2011-12-15 00:25:49 Re: Philosophical question
Previous Message David Owen 2011-12-14 22:17:31 Re: Philosophical question