Question on a select

There are several ways. I am making the simplifying assumption that name,
type and dir cannot be NULL in either table. If they are the query is a
little more complicated.

The following are a couple of many techniques.

SELECT a.a_name
, a.a_type
, a.a_dir
FROM a_table a
WHERE NOT EXISTS
( SELECT NULL
FROM b_table b
WHERE b.b_name = a.a_name
AND b.b_type = a.a_type
AND b.b_dir = a.a_dir
)

SELECT a.a_name
, a.a_type
, a.a_dir
FROM a_table a
LEFT JOIN b_table b
ON a.a_table = b.b_table
AND a.a_type = b.b_type
AND a.a_dir = b.b_type
WHERE b.b_table IS NULL // assumes that b.b_table
is a not null column.

Let's say that dir could be null and dir is a string, then (assuming that
dir can never be 'xyz') you could say something like

COALESCE(a.a_dir,'xyz') = COALESCE(b.b_dir,'xyz')

Since NULL never equal NULL, if you want NULL in one table to match a NULL
in another table, you need to change it to something not NULL. However this
depends on what you want in your application.

Queries like this are used often to check the integrity of your data.
Examples of this are 1) What orders don't have order items? 2) What books
have no authors? etc.

----- Original Message -----
From: "Madison Kelly" <linux@alteeve.com>
To: "PgSQL General List" <pgsql-general@postgresql.org>
Sent: Saturday, January 01, 2005 7:32 PM
Subject: [GENERAL] Question on a select

On Sat, Jan 01, 2005 at 22:32:17 -0500,
Madison Kelly <linux@alteeve.com> wrote:

Hi all,

This is my first post here so please let me know if I miss any list
guidelines. :)

I was hoping to get some help, advice or pointers to an answer for a
somewhat odd (to me at least) SELECT. What I am trying to do is select
that values from one table where matching values do not exist in another
table.

For example:

Let's say 'table_a' has the columns 'a_name, a_type, a_dir,
a_<others>' and 'table_b' has the columns 'b_name, b_type, b_dir,
b_<others>' where 'others' are columns unique to each table. What I need
to do is select all the values in 'a_name, a_type, a_dir' from 'table_a'
where there is no matching entries in "table_b's" 'b_name, b_type, b_dir'.

SELECT a_name, a_type, a_dir, a_<others> FROM table_a
WHERE a_name, a_type, a_dir NOT IN (
SELECT b_name, b_type, b_dir FROM table_b)
;

In pre 7.4 versions or if there are NULLs in the key columns for table_b
then you probably want to use NOT EXISTS (with a moodified WHERE clause)
instead on NOT IN.

Vincent Hikida wrote:

There are several ways. I am making the simplifying assumption that
name, type and dir cannot be NULL in either table. If they are the query
is a little more complicated.

The following are a couple of many techniques.

SELECT a.a_name
, a.a_type
, a.a_dir
FROM a_table a
WHERE NOT EXISTS
( SELECT NULL
FROM b_table b
WHERE b.b_name = a.a_name
AND b.b_type = a.a_type
AND b.b_dir = a.a_dir
)

SELECT a.a_name
, a.a_type
, a.a_dir
FROM a_table a
LEFT JOIN b_table b
ON a.a_table = b.b_table
AND a.a_type = b.b_type
AND a.a_dir = b.b_type
WHERE b.b_table IS NULL // assumes that
b.b_table is a not null column.

Let's say that dir could be null and dir is a string, then (assuming
that dir can never be 'xyz') you could say something like

COALESCE(a.a_dir,'xyz') = COALESCE(b.b_dir,'xyz')

Since NULL never equal NULL, if you want NULL in one table to match a
NULL in another table, you need to change it to something not NULL.
However this depends on what you want in your application.

Queries like this are used often to check the integrity of your data.
Examples of this are 1) What orders don't have order items? 2) What
books have no authors? etc.

This is wonderful! Thank you for responding so quickly! :) I should
mention that I am still very much learning so I apologise in advance if
I miss the obvious. ^.^;

They are all 'not null' and I am trying to do exactly the kind of
task you described. I tried the first example on my DB and got a syntax
error:

tle-bu=> SELECT a.file_name, a.file_parent_dir, a.file_type FROM
file_info_1 a WHERE NOT EXIST (SELECT NULL FROM file_set_1 b WHERE
b.fs_name=a.file_name, b.fs_parent_dir=a.file_parent_dir,
b.fs_type=a.file_type);
ERROR: syntax error at or near "SELECT" at character 88

The second example you gave seems to work perfectly (as I will show
near the bottom of this email). What are the benefits and down sides of
each method? Is there a simple reason why the first method failed
(probably a typo I imagine...)?

A little more specifics about my DB:

'file_info_1' and 'file_set_1' are two tables I use to store
information of files and directories (this is a backup program).

'file_info_#' stores dynamic info like file size, owner and such.
This table is dropped and recreated before a new scan of the partition
creates a mass 'COPY' load (the '_1' indicates the first partition).

'file_set_#' stores static information such as "has the file been
selected for backup" which is why I keep it in a separate table. I want
to run this select first to write entries for newly added files and
directories (the values will match the file's parent) and then again in
reverse to remove from 'file_set_#' entries that no longer exist on the
partition.

If it helps, here is the structure of the tables:

CREATE TABLE file_info_ID (
file_acc_time bigint not null,
file_group_name varchar(255) not null,
file_group_uid int not null,
file_mod_time bigint not null,
file_name varchar(255) not null,
file_parent_dir varchar(255) not null,
file_perm varchar(10) not null,
file_size bigint not null,
file_type varchar(2) not null default 'f',
file_user_name varchar(255) not null,
file_user_uid int not null
);

CREATE TABLE file_set_# (
fs_backup boolean not null default 't',
fs_display boolean not null default 'f',
fs_name varchar(255) not null,
fs_parent_dir varchar(255) not null,
fs_restore boolean not null default 'f',
fs_type varchar(2) not null default 'f'
);

And here is some sample data that I have to work with (yes, it's a
win2k partition... I use it to test other aspects of my program and, if
I blow it away, I won't be upset. ^.^; All of this is being done on a
Fedora Core 3 install in case it makes a difference):

tle-bu=> SELECT file_type, file_parent_dir, file_name FROM file_info_1
WHERE file_parent_dir='/' LIMIT 30;
file_type | file_parent_dir | file_name
-----------+-----------------+------------------------
d | / | .
d | / | downloads
d | / | Documents and Settings
d | / | Program Files
f | / | io.sys
f | / | msdos.sys
f | / | _NavCClt.Log
d | / | WUTemp
d | / | Recycled
f | / | pagefile.sys
d | / | winnt
f | / | ntldr
f | / | ntdetect.com
f | / | boot.ini
f | / | config.sys
f | / | autoexec.bat
f | / | t5r4e3w2q1.exe
f | / | 1q2w3e4r5t.exe
f | / | logon.exe
f | / | arcldr.exe
f | / | arcsetup.exe
(21 rows)

tle-bu=> SELECT fs_type, fs_parent_dir, fs_name FROM file_set_1 WHERE
fs_parent_dir='/' LIMIT 30;
fs_type | fs_parent_dir | fs_name
---------+---------------+------------------------
d | / | .
d | / | downloads
d | / | Documents and Settings
d | / | Program Files
d | / | WUTemp
d | / | Recycled
d | / | winnt
(7 rows)

In this example I deleted manually all the 'f' entries so that when I
do the select I should get:

file_type | file_parent_dir | file_name
-----------+-----------------+------------------------
f | / | io.sys
f | / | msdos.sys
f | / | _NavCClt.Log
f | / | pagefile.sys
f | / | ntldr
f | / | ntdetect.com
f | / | boot.ini
f | / | config.sys
f | / | autoexec.bat
f | / | t5r4e3w2q1.exe
f | / | 1q2w3e4r5t.exe
f | / | logon.exe
f | / | arcldr.exe
f | / | arcsetup.exe

Which is exactly what your second example provides:

tle-bu=> SELECT a.file_name, a.file_parent_dir, a.file_type FROM
file_info_1 a LEFT JOIN file_set_1 b ON a.file_name=b.fs_name AND
a.file_parent_dir=b.fs_parent_dir AND a.file_type=b.fs_type WHERE
b.fs_name IS NULL;
file_name | file_parent_dir | file_type
----------------+-----------------+-----------
1q2w3e4r5t.exe | / | f
arcldr.exe | / | f
arcsetup.exe | / | f
autoexec.bat | / | f
boot.ini | / | f
config.sys | / | f
io.sys | / | f
logon.exe | / | f
msdos.sys | / | f
_NavCClt.Log | / | f
ntdetect.com | / | f
ntldr | / | f
pagefile.sys | / | f
t5r4e3w2q1.exe | / | f
(14 rows)

Thank you very much for your help!

Madison

Bruno Wolff III wrote:

SELECT a_name, a_type, a_dir, a_<others> FROM table_a
WHERE a_name, a_type, a_dir NOT IN (
SELECT b_name, b_type, b_dir FROM table_b)
;

In pre 7.4 versions or if there are NULLs in the key columns for table_b
then you probably want to use NOT EXISTS (with a moodified WHERE clause)
instead on NOT IN.

Hi Bruno,

Thank you for replying! I tried your example but I am getting a
syntax error:

tle-bu=> SELECT file_name, file_parent_dir, file_type FROM file_info_1
WHERE file_name, file_parent_dir, file_type NOT IN (SELECT fs_name,
fs_parent_dir, fs_type FROM file_set_1);
ERROR: syntax error at or near "," at character 78

I just replied to Vincent's post with a lot of detail on what I am
trying to do and how my DB is constructed. His second example worked but
I also had a syntax error on his first example. This program will be
working with very large data sets so I would love to get your method
working so that I could try benchmarking them to see which, in my
application, would be most effective.

Thank you very kindly for helping!

Madison

On Sun, Jan 02, 2005 at 01:58:20 -0500,
Madison Kelly <linux@alteeve.com> wrote:

Bruno Wolff III wrote:

SELECT a_name, a_type, a_dir, a_<others> FROM table_a
WHERE a_name, a_type, a_dir NOT IN (
SELECT b_name, b_type, b_dir FROM table_b)
;

In pre 7.4 versions or if there are NULLs in the key columns for table_b
then you probably want to use NOT EXISTS (with a moodified WHERE clause)
instead on NOT IN.

Hi Bruno,

Thank you for replying! I tried your example but I am getting a
syntax error:

tle-bu=> SELECT file_name, file_parent_dir, file_type FROM file_info_1
WHERE file_name, file_parent_dir, file_type NOT IN (SELECT fs_name,
fs_parent_dir, fs_type FROM file_set_1);
ERROR: syntax error at or near "," at character 78

There should be parenthesis around the list to test.
WHERE a_name, a_type, a_dir NOT IN (
should be
WHERE (a_name, a_type, a_dir) NOT IN (

I just replied to Vincent's post with a lot of detail on what I am
trying to do and how my DB is constructed. His second example worked but
I also had a syntax error on his first example. This program will be
working with very large data sets so I would love to get your method
working so that I could try benchmarking them to see which, in my
application, would be most effective.

I believe that the NOT IN query should run comparably to the LEFT JOIN
example supplied by the other person (at least in recent versions of
Postgres). I would expect this to run faster than using NOT EXISTS.
You probably want to try all 3. The semantics of the three ways of doing
this are not all equivalent if there are NULLs in the data being used
to eliminate rows. As you indicated you don't have NULLs this shouldn't
be a problem.

Another way to write this is using set different (EXCEPT or EXCEPT ALL)
using the key fields and then joining back to table a to pick up the
other fields. However this will almost certianly be slower than the
other methods.

Bruno Wolff III wrote:

There should be parenthesis around the list to test.
WHERE a_name, a_type, a_dir NOT IN (
should be
WHERE (a_name, a_type, a_dir) NOT IN (

That did it (I think)!

I believe that the NOT IN query should run comparably to the LEFT JOIN
example supplied by the other person (at least in recent versions of
Postgres). I would expect this to run faster than using NOT EXISTS.
You probably want to try all 3. The semantics of the three ways of doing
this are not all equivalent if there are NULLs in the data being used
to eliminate rows. As you indicated you don't have NULLs this shouldn't
be a problem.

Another way to write this is using set different (EXCEPT or EXCEPT ALL)
using the key fields and then joining back to table a to pick up the
other fields. However this will almost certianly be slower than the
other methods.

Something odd, now that I have the other method working (I think)...

tle-bu=> SELECT a.file_name, a.file_parent_dir, a.file_type FROM
file_info_1 a LEFT JOIN file_set_1 b ON a.file_name=b.fs_name AND
a.file_parent_dir=b.fs_parent_dir AND a.file_type=b.fs_type WHERE
b.fs_name IS NULL;

returns the results in roughly 1 or 2 seconds on a test data set of
15,000 entries. I have an index on both 'file_info_1' covering
'fs_name', 'fs_parent_dir' and 'fs_type' and on 'file_set_1' covering
'file_name', 'file_parent_dir' and 'file_type'. When I try the seconds
method though:

tle-bu=> SELECT file_name, file_parent_dir, file_type FROM file_info_1
WHERE (file_name, file_parent_dir, file_type) NOT IN (SELECT fs_name,
fs_parent_dir, fs_type FROM file_set_1);

It took so long to process that after roughly three minutes I stopped
the query for fear of overheating my laptop (which happend a while back
forcing a thermal shut down).

The indexes are:

CREATE INDEX file_info_#_display_idx ON file_info_# (file_type,
file_parent_dir, file_name);
CREATE INDEX file_set_#_sync_idx ON file_set_# (fs_name, fs_parent_dir,
fs_type)

Are these not effective for the second query? If not, what should I
change or add? If so, would you have any insight into why there is such
an incredible difference in performance?

Thanks very much again!!

Madison

They are all 'not null' and I am trying to do exactly the kind of task
you described. I tried the first example on my DB and got a syntax error:

tle-bu=> SELECT a.file_name, a.file_parent_dir, a.file_type FROM
file_info_1 a WHERE NOT EXIST (SELECT NULL FROM file_set_1 b WHERE
b.fs_name=a.file_name, b.fs_parent_dir=a.file_parent_dir,
b.fs_type=a.file_type);
ERROR: syntax error at or near "SELECT" at character 88

I've quickly read the thread and I don't think you got an answer as to why
you are getting a syntax error here. Your query shows something line

WHERE b.fs_name=a.file_name, b.fs_parent_dir=a.file_parent_dir

you need to put an AND instead of a comma:

WHERE b.fs_name=a.file_name AND b.fs_parent_dir=a.file_parent_dir

As for which of the queries is best I don't know. My background is as an
Oracle developer. I think that Bruno already suggested testing the three
queries. There is a trace utility which shows some of what happens under the
covers of a query. I've used it extensively in Oracle but have never used it
in Postgresql.

If I understand what you said, the NOT IN was significantly slower. That has
been my experience in Oracle long time ago so I've tended to shy away from
that syntax. I'm sure optimizers are much better now then when I
experimented with NOT IN but my coworker who tried it in Oracle was getting
a slower response than with a subselect about a year ago. Theoretically if 3
queries are logically equivalent as the three queries you've been given, an
optimizer should find the same best query plan to execute it. I don't think
that optimizers are that smart yet.

The outer join is probably doing either a sort merge or a hash join. In your
application this should be the best option. (A sort merge sorts both tables
first or at least the key columns and then merges the tables together.)

Bruno said that the subselect would be slower. It may be that he thinks it
will do a nested loop. That is that it will read each row in table A and try
to find that concatenated key in table B's index. I don't think that a
nested loop would be very good in your particular application.

As for the indexes you set up, I think they are correct indexes.

Vincent

The indexes are:

CREATE INDEX file_info_#_display_idx ON file_info_# (file_type,
file_parent_dir, file_name);
CREATE INDEX file_set_#_sync_idx ON file_set_# (fs_name, fs_parent_dir,
fs_type)

Are these not effective for the second query? If not, what should I
change or add? If so, would you have any insight into why there is such an
incredible difference in performance?

I didn't look at your indexes closely enough. When you have concatenated
index, you want to have the most selective colum first. I guess that
file_type is not very selective. file_name is probably the most selective.
In the above, the index on file_set_# is optimal. The index on file_info_#
is suboptimal.

However, if the query is doing a hash join or sort merge, an index is not
used so the index doesn't matter. However, you probably do other queries
that do use the index so it should be fixed.

Vincent

Vincent Hikida wrote:

The indexes are:

CREATE INDEX file_info_#_display_idx ON file_info_# (file_type,
file_parent_dir, file_name);
CREATE INDEX file_set_#_sync_idx ON file_set_# (fs_name,
fs_parent_dir, fs_type)

Are these not effective for the second query? If not, what should I
change or add? If so, would you have any insight into why there is
such an incredible difference in performance?

I didn't look at your indexes closely enough. When you have concatenated
index, you want to have the most selective colum first. I guess that
file_type is not very selective. file_name is probably the most
selective. In the above, the index on file_set_# is optimal. The index
on file_info_# is suboptimal.

However, if the query is doing a hash join or sort merge, an index is
not used so the index doesn't matter. However, you probably do other
queries that do use the index so it should be fixed.

Vincent

Thank you, Vincent!

I didn't realize that the order made a difference. A sign of how much
learning I need to do. :p For reference, I think 'file_parent_dir' and
'fs_parent_dir' are the most important because I do an 'ORDER BY
[fs|file]_parent_dir ASC' on most queries. I've made the changes, thank
you again!

Madison

I didn't realize that the order made a difference. A sign of how much
learning I need to do. :p For reference, I think 'file_parent_dir' and
'fs_parent_dir' are the most important because I do an 'ORDER BY
[fs|file]_parent_dir ASC' on most queries. I've made the changes, thank
you again!

If you SELECT ... WHERE condition on A order by B :

an index on A will be used, but an index on B won't

If you SELECT ... WHERE condition on A order by A, B :

an index on A,B will be used because it will give the rows in already
sorted order