pg.ddx.io  pgsql-sql@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Herouth Maoz <herouth@oumail.openu.ac.il>
To: pierre <pierre@desertmoon.com>
Cc: pgsql-sql@postgreSQL.org
Subject: Re: [SQL] MINUS and slow 'not in'
Date: Tue, 24 Nov 1998 11:14:42 +0200
Message-ID: <l03110702b28025746cbe@[147.233.159.109]> (raw)
In-Reply-To: <199811240453.EAA50170@out4.ibm.net>

At 6:53 +0200 on 24/11/98, pierre wrote:


> I then tried using a 'not in' clause.
>
> select * from A where user_id not in (select * from B);
>
> This is VERY slow, and examining the explain output tells me that it will
> use the user_id index for table B, but a sequential scan of A even though
> A has an index for the user_id column.

First, I assume you meant "select user_id from B", not "select *", or
something is very strange here.

Anyway, suppose you had two tables. How would you go about doing this while
using *both* indices? I don't think it's possible. You have a condition
that says: include each row which doesn't meet a certain criteria. The only
way to do it is to scan each row, get the value of its user_id, and then go
to be, and use its index to find if the user_id we already have is NOT
there.

You can use an index only when you have a specific value to search for. A
NOT IN clause doesn't supply a specific value, so you can't use the outer
index.

You may try to convert the NOT IN to a NOT EXISTS clause, and see if it
improves anything, but it will still require a sequential search.

If I needed this query often, I'd try to optimize it by adding a column to
table A, marking the records that match, and then selecting all the records
which don't match. I'm not sure whether one can index a boolean field in
the current version of PostgreSQL, but if not, you can probably use a char
field instead. I suppose you can make sure this column stays up-to-date
with rules, or do the update as a preparatory step: Update all to "N", then
update all the fields that match to "Y" with a join. VACUUM, ANALYZE, and
then you can start selecting.

This requires two sequential scans plus vacuums before you start selecting,
so it may not be worth it if you only select once by this criteria... I'd
go with the NOT IN or NOT EXISTS solution, which gives you a sequential
scan with minimal search over the index of table B.

SELECT * FROM A
WHERE NOT EXISTS (
   SELECT * FROM B
   WHERE B.user_id = A.user_id
);

By the way, if you have any specific criteria on A, besides the NOT EXISTS
or NOT IN, they may cause an index scan on A as well.

Herouth

--
Herouth Maoz, Internet developer.
Open University of Israel - Telem project
http://telem.openu.ac.il/~herutma





view thread (9+ messages)  latest in thread

Message-ID: <l03110702b28025746cbe@[147.233.159.109]>
Permalink:  ../l03110702b28025746cbe@%5B147.233.159.109%5D/
Also on:    postgresql.org/message-id/l03110702b28025746cbe@[147.233.159.109]

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-sql@postgresql.org
  Cc: herouth@oumail.openu.ac.il, pierre@desertmoon.com
  Subject: Re: [SQL] MINUS and slow 'not in'
  In-Reply-To: <l03110702b28025746cbe@[147.233.159.109]>
  References: <199811240453.EAA50170@out4.ibm.net> <l03110702b28025746cbe@[147.233.159.109]>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox