Finding uniques across a big join

On Tue, Nov 29, 2005 at 09:58:49PM -0500, John D. Burger wrote:

I could use some help with the following:

I have a database of geographic entities with attributes spread across
several tables. I need to determine which entities are unique with
respect to some of those attributes. I'm using the following query:

<snip>

If you put the gazPlaceID as a result of the uniqs subquery, that would
avoid the second lookup, right? Whether it's much faster is the
question. So something like:

select p1.gazPlaceID
from gazPlaces as p1
join gazNamings as n1 using (gazPlaceID)
join gazContainers as c1 using (gazPlaceID)
group by p1.gazPlaceID, p1.featureType, n1.placeNameID, c1.containerID
having count(*) = 1

Secondly, what does the plan look like? Is it materialising or sorting
at any stage?

Finally, what version of postgres?

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/

It will probably be a win to come up with a list of potential records
from each table, instead of after doing the 3-way join. so something
like:

(SELECT gazPlaceID FROM gazPlaces GROUP BY featureType HAVING count(*)=1)
JOIN
(SELECT ...)

If you post the output of explain (or explain analyze is even better)
then people could probably make better suggestions.

On Tue, Nov 29, 2005 at 09:58:49PM -0500, John D. Burger wrote:

I could use some help with the following:

I have a database of geographic entities with attributes spread across
several tables. I need to determine which entities are unique with
respect to some of those attributes. I'm using the following query:

select p2.gazPlaceID from
(select p1.featureType, n1.placeNameID, c1.containerID
from gazPlaces as p1
join gazNamings as n1 using (gazPlaceID)
join gazContainers as c1 using (gazPlaceID)
group by p1.featureType, n1.placeNameID, c1.containerID
having count(*) = 1) as uniqs,
gazPlaces as p2
join gazNamings as n2 using (gazPlaceID)
join gazContainers as c2 using (gazPlaceID)
where uniqs.featureType = p2.featureType
and uniqs.placeNameID = n2.placeNameID
and uniqs.containerID = c2.containerID;

The basic idea is to compute featureType-placeNameID-containerID
combinations with a three-way join, determine which of those have a
count of 1, and then join that back to the same three-way join to get
the gazPlaceIDs corresponding to the unique combos (whew!).

gazPlaces has about 6M entries, gazNamings and gazContainers each about
10M. All of the fields above are integers, and I have indexes on
everything relevant, but the query still takes about eight hours. My
question is not (necessarily) how to improve the efficiency of this
query, but whether anyone can think of a faster way to compute the
uniques. Again, the goal is to find entries in gazPlaces that are the
only ones with their particular combination of feature type, name and
container.

Any help is appreciated!

- John Burger
MITRE

---------------------------(end of broadcast)---------------------------
TIP 4: Have you searched our list archives?

http://archives.postgresql.org

--
Jim C. Nasby, Sr. Engineering Consultant jnasby@pervasive.com
Pervasive Software http://pervasive.com work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461

On Nov 30, 2005, at 01:55, Martijn van Oosterhout wrote:

On Tue, Nov 29, 2005 at 09:58:49PM -0500, John D. Burger wrote:

I could use some help with the following:

I have a database of geographic entities with attributes spread across
several tables. I need to determine which entities are unique with
respect to some of those attributes. I'm using the following query:

<snip>

If you put the gazPlaceID as a result of the uniqs subquery, that would
avoid the second lookup, right? Whether it's much faster is the
question. So something like:

select p1.gazPlaceID
from gazPlaces as p1
join gazNamings as n1 using (gazPlaceID)
join gazContainers as c1 using (gazPlaceID)
group by p1.gazPlaceID, p1.featureType, n1.placeNameID,
c1.containerID
having count(*) = 1

The problem is that then every row is unique, because gazPlaceID is a
primary key. As far as I can see, I need to group on just the other
three columns - they're the ones for which I'm interested in
uniqueness.

Secondly, what does the plan look like? Is it materialising or sorting
at any stage?
Finally, what version of postgres?

Version is 7.4.8 for Solaris. Below is (a version of) the query again,
as well as the plan. No materialization, I think, but it appears to be
sorting the first three-way join to do the counts, then sorting the
second one to merge. Cost estimates are way off, as the final result
has almost 10M rows, but everything is analyzed, with indexes on every
column, although none of them get used.

Again, any suggestions on tweaking this query, or a completely
different approach to finding the entities with unique combinations,
would be much appreciated.

- John Burger
MITRE

select p2.gazPlaceID, u.*
into table tempCanonical_nameMatchEquiver_3435_1
from
(select p1.featureType, n1.placeNameID, c1.containerID
from gazPlaces as p1
join gazNamings as n1 using (gazPlaceID)
join gazContainers as c1 using (gazPlaceID)
group by p1.featureType, n1.placeNameID, c1.containerID
having count(*) = 1) as u,
gazPlaces as p2
join gazNamings as n2 using (gazPlaceID)
join gazContainers as c2 using (gazPlaceID)
where u.featureType = p2.featureType
and u.placeNameID = n2.placeNameID
and u.containerID = c2.containerID;

Hash Join (cost=4009535.96..4316595.92 rows=306 width=16)
Hash Cond: (("outer".gazplaceid = "inner".gazplaceid) AND
("outer".containerid = "inner".containerid))
-> Seq Scan on gazcontainers c2 (cost=0.00..141636.45 rows=9193945
width=8)
-> Hash (cost=4006472.81..4006472.81 rows=282029 width=20)
-> Merge Join (cost=3777226.54..4006472.81 rows=282029
width=20)
Merge Cond: (("outer".featuretype = "inner".featuretype)
AND ("outer".placenameid = "inner".placenameid))
-> Subquery Scan u (cost=2107001.20..2259698.67
rows=5552635 width=12)
-> GroupAggregate (cost=2107001.20..2204172.32
rows=5552635 width=12)
Filter: (count(*) = 1)
-> Sort (cost=2107001.20..2120882.79
rows=5552635 width=12)
Sort Key: p1.featuretype,
n1.placenameid, c1.containerid
-> Hash Join
(cost=688064.17..1217844.46 rows=5552635 width=12)
Hash Cond: ("outer".gazplaceid =
"inner".gazplaceid)
-> Seq Scan on gaznamings n1
(cost=0.00..156331.05 rows=10147805 width=8)
-> Hash
(cost=642816.39..642816.39 rows=6128713 width=16)
-> Hash Join
(cost=160244.91..642816.39 rows=6128713 width=16)
Hash Cond:
("outer".gazplaceid = "inner".gazplaceid)
-> Seq Scan on
gazcontainers c1 (cost=0.00..141636.45 rows=9193945 width=8)
-> Hash
(cost=120982.13..120982.13 rows=6128713 width=8)
-> Seq Scan
on gazplaces p1 (cost=0.00..120982.13 rows=6128713 width=8)
-> Sort (cost=1670225.33..1685547.11 rows=6128713
width=16)
Sort Key: p2.featuretype, n2.placenameid
-> Hash Join (cost=160244.91..684040.19
rows=6128713 width=16)
Hash Cond: ("outer".gazplaceid =
"inner".gazplaceid)
-> Seq Scan on gaznamings n2
(cost=0.00..156331.05 rows=10147805 width=8)
-> Hash (cost=120982.13..120982.13
rows=6128713 width=8)
-> Seq Scan on gazplaces p2
(cost=0.00..120982.13 rows=6128713 width=8)

Jim C. Nasby wrote:

It will probably be a win to come up with a list of potential records
from each table, instead of after doing the 3-way join. so something
like:

(SELECT gazPlaceID FROM gazPlaces GROUP BY featureType HAVING
count(*)=1)
JOIN
(SELECT ...)

Hmm, not sure I understand. Joining the uniques wrt each of the three
columns does not result in the unique triples, or even a superset of
them, at least in this case.

If you post the output of explain (or explain analyze is even better)
then people could probably make better suggestions.

Okay, I just posted the query plan. I will try to run an EXPLAIN
ANALYZE tonight.

Again, I'm also interested in completely different approaches to
discovering the entities with unique attribute combinations.
Intuitively, the query I posted is doing "too much work", because it's
computing the total count for each combo, when all I really need is to
know if the count is 1 or greater than 1.

Thanks!

- John Burger
MITRE

On Wed, Nov 30, 2005 at 01:20:19PM -0500, John D. Burger wrote:

select p1.gazPlaceID
from gazPlaces as p1
join gazNamings as n1 using (gazPlaceID)
join gazContainers as c1 using (gazPlaceID)
group by p1.gazPlaceID, p1.featureType, n1.placeNameID,
c1.containerID
having count(*) = 1

The problem is that then every row is unique, because gazPlaceID is a
primary key. As far as I can see, I need to group on just the other
three columns - they're the ones for which I'm interested in
uniqueness.

AIUI, according to the JOIN conditions in the query you have
n1.gazPlaceID = c1.gazPlaceID = p1.gazPlaceID so grouping by one of
those shouldn't affect the query result.

Are the tables wide? Maybe you're losing a lot of time transferring
data you don't need. Other than that I can't think of any neat
tricks...

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/

On Tue, 2005-11-29 at 20:58, John D. Burger wrote:

I could use some help with the following:

I have a database of geographic entities with attributes spread across
several tables. I need to determine which entities are unique with
respect to some of those attributes. I'm using the following query:

select p2.gazPlaceID from
(select p1.featureType, n1.placeNameID, c1.containerID
from gazPlaces as p1
join gazNamings as n1 using (gazPlaceID)
join gazContainers as c1 using (gazPlaceID)
group by p1.featureType, n1.placeNameID, c1.containerID
having count(*) = 1) as uniqs,
gazPlaces as p2
join gazNamings as n2 using (gazPlaceID)
join gazContainers as c2 using (gazPlaceID)
where uniqs.featureType = p2.featureType
and uniqs.placeNameID = n2.placeNameID
and uniqs.containerID = c2.containerID;

The basic idea is to compute featureType-placeNameID-containerID
combinations with a three-way join, determine which of those have a
count of 1, and then join that back to the same three-way join to get
the gazPlaceIDs corresponding to the unique combos (whew!).

gazPlaces has about 6M entries, gazNamings and gazContainers each about
10M. All of the fields above are integers, and I have indexes on
everything relevant, but the query still takes about eight hours. My
question is not (necessarily) how to improve the efficiency of this
query, but whether anyone can think of a faster way to compute the
uniques. Again, the goal is to find entries in gazPlaces that are the
only ones with their particular combination of feature type, name and
container.

OK, let's assume that the basic part of it, before the group by, has
been put into a view, so we can then do:

select pkey1, field2, field3, field4 from view;

And we know that pkey1 is unique, but we want the records where pkey1 is
the only thing different between them, right?

select
v1.pkey1,
v1.field2,
v1.field3,
v1.field4,
v2.pkey1,
v2.field2,
v2.field3,
v2.field4,
from
view v1
join
view v2
on (
v1.field2=v2.field2 and
v1.field3=v2.field3 and
v1.field3=v2.field3 and
v1.pkey1<>v2.pkey
)

How does that work?

Scott Marlowe wrote:

OK, let's assume that the basic part of it, before the group by, has
been put into a view, so we can then do:

select pkey1, field2, field3, field4 from view;

And we know that pkey1 is unique, but we want the records where pkey1
is
the only thing different between them, right?

Hmm, I'm explaining this really badly :). I should have defined a view
like you suggest to help simplify it. What I want is the pkeys (and
the field values) where no other pkey has that triple of field values.
That's why my earlier query does a group by the fields and then having
count(*) = 1. Also, FWIW, pkey1 is unique in its original table, but
not in the view, since some of the other tables are one-to-many.

select
v1.pkey1,
v1.field2,
v1.field3,
v1.field4,
v2.pkey1,
v2.field2,
v2.field3,
v2.field4,
from
view v1
join
view v2
on (
v1.field2=v2.field2 and
v1.field3=v2.field3 and
v1.field3=v2.field3 and
v1.pkey1<>v2.pkey
)

How does that work?

Won't this be a massive cross product of all pkey pairs that have the
same field values?

Here's what I'm currently using, in terms of your very helpful view:

select v1.pkey1, v1.field2, v1.field3, v1.field4
from view as v1
join
(select v2.field1, v2.field2, v2.field3
from view as v2
group by v2.field2, v2.field3, v2.field4
having count(*) = 1)
using (field2, field3, field4);

This is the one that takes eight hours. :( Another way to express what
I want is this:

select v1.pkey1, v1.field2, v1.field3, v1.field4
from view as v1
where not exists
(select true from view as v2
where v1.field2 = v2.field2
and v1.field3 = v2.field3
and v1.field4 = v2.field4
and v1.pkey1 <> v2.pkey1);

That looks like a horrible nested loop, but I suppose I should try it
to make sure it is indeed slower then the previous query.

- John Burger
MITRE

On Wed, 2005-11-30 at 16:27, John D. Burger wrote:

Scott Marlowe wrote:

select
v1.pkey1,
v1.field2,
v1.field3,
v1.field4,
v2.pkey1,
v2.field2,
v2.field3,
v2.field4,
from
view v1
join
view v2
on (
v1.field2=v2.field2 and
v1.field3=v2.field3 and
v1.field3=v2.field3 and
v1.pkey1<>v2.pkey
)

How does that work?

Won't this be a massive cross product of all pkey pairs that have the
same field values?

Yes, assuming there are a lot of them. OTOH, if there are only a few
duplicates you're looking for...

How many are you expecting, percentage wise, to get back?

Here's what I'm currently using, in terms of your very helpful view:

select v1.pkey1, v1.field2, v1.field3, v1.field4
from view as v1
join
(select v2.field1, v2.field2, v2.field3
from view as v2
group by v2.field2, v2.field3, v2.field4
having count(*) = 1)
using (field2, field3, field4);

This is the one that takes eight hours. :( Another way to express what
I want is this:

select v1.pkey1, v1.field2, v1.field3, v1.field4
from view as v1
where not exists
(select true from view as v2
where v1.field2 = v2.field2
and v1.field3 = v2.field3
and v1.field4 = v2.field4
and v1.pkey1 <> v2.pkey1);

That looks like a horrible nested loop, but I suppose I should try it
to make sure it is indeed slower then the previous query.

If you can allocated enough shared memory for the set to fit in memory,
you might be able to get a hash agg method, which is much faster than
most other methods for this kind of thing, since it requires no sort.

In a side point, I'm currently mushing 888,000,000 6 character codes up
against each other to check for duplicates. I have 6 machines doing
this, at 1 million codes compared to 1 million codes every 0.5 seconds
aggregate. That gets me down to about 1 week. So, 8 hours is seeming
quite fast. :)

On Wed, Nov 30, 2005 at 01:29:17PM -0500, John D. Burger wrote:

Jim C. Nasby wrote:

It will probably be a win to come up with a list of potential records
from each table, instead of after doing the 3-way join. so something
like:

(SELECT gazPlaceID FROM gazPlaces GROUP BY featureType HAVING
count(*)=1)
JOIN
(SELECT ...)

Hmm, not sure I understand. Joining the uniques wrt each of the three
columns does not result in the unique triples, or even a superset of
them, at least in this case.

So featureType is *unique* within gazPlaces?

If you look at the query plan, it's estimating 120k to scan one of the
tables, but if you look at the hash join that joins the 3rd table to the
first two it's estimating 1.2M. That's because it's dealing with a
monsterous dataset; it's joining every single row with every other
possible row.

What I was trying to do was eliminate rows from that join that would
mean you couldn't have a count of only 1. But my example actually
changes the output, so that won't work.

If you post the output of explain (or explain analyze is even better)
then people could probably make better suggestions.

Okay, I just posted the query plan. I will try to run an EXPLAIN
ANALYZE tonight.

Again, I'm also interested in completely different approaches to
discovering the entities with unique attribute combinations.
Intuitively, the query I posted is doing "too much work", because it's
computing the total count for each combo, when all I really need is to
know if the count is 1 or greater than 1.

The problem I see is that as you add more criteria (which is what each
JOIN does), you reduce the count that you might get for every
combination. Of course adding more rows increases the potential count.
Combine the two and I don't think there's any other way to come up with
the list of what's truely unique any other way.

What I'm not sure of is if knowing certain things about gazPlaceID would
allow you to make some assumptions that could simplify the query. I
can't think of anything that would help there.

Basically, I think you're stuck with the ugly 3-way join that's the core
of the slowness. But, there is a gain to be had: doing the second set of
joins bumps you from 1.2M to over 4M. Someone else suggested adding
gazPlaceID to the GROUP BY; I definately think you should do that.
Because of the equality conditions I can't conceive of any way that
it would change anything. What *might* make a difference is which table
you pull gazPlaceID from; again, because of the equality condition it
doesn't matter which table you get them from, but I don't know if the
optimizer understands that. So changing which table you pull that from
could drastically effect how the 3-way join is done, which could also
drastically effect the cost involved. Ideally you'd like the first 2-way
join to be the one that results in the smallest amount of overlap.

Also, if you're on 8.1, you might try experimenting with different
indexes on the 3 tables. I think this could be an ideal candidate for a
bitmap scan; I believe it's possible to build the entire set you want
with a scan of 6 bitmaps, but I don't know if there's that much brains
in the bitmap code yet. Actually, I think what would be ideal would be
to build 3 bitmaps for the 3 fields you really want to group by and
compare those; the trick would be building those bitmaps using indexes
of gazPlaceID and the field you care about from each table.

BTW, it might be easier for someone to come up with a solution if you
post a plain-english description of what you're trying to find out,
along with any facts about the data (such as what's unique, etc).
--
Jim C. Nasby, Sr. Engineering Consultant jnasby@pervasive.com
Pervasive Software http://pervasive.com work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461

Scott Marlowe wrote:

Won't this be a massive cross product of all pkey pairs that have the
same field values?

Yes, assuming there are a lot of them. OTOH, if there are only a few
duplicates you're looking for...

I'm not looking for duplicates, I'm looking for uniques - note the
Subject line :). Here's an analogous problem: everybody in the room
has eye color, hair color, and skin color. I want to find the people
whose particular three-way combination is unique - no one else has that
eye-hair-skin combo. The analogue to my current query is then like
this:

select p1.personID, p1.eyeColor, p1.hairColor, p1.skinColor
from persons as p1
join
(select p2.eyeColor, p2.hairColor, p2.skinColor
from persons as p2
group by p2.eyeColor, p2.hairColor, p2.skinColor
having count(*) = 1)
using (eyeColor, hairColor, skinColor);

The inner select finds the unique combinations, the outer one goes back
and finds the peopleID corresponding to each unique combo. And the
persons table is actually a view on a big three-way join.

Jim Nasby wrote:

Someone else suggested adding gazPlaceID to the GROUP BY; I definately
think you should do that.

That changes the semantics of what I want. If I group by personID
above, then every FOUR-way combo is of course unique. What I'd like to
do is group by the three attributes, and select for personID as well.
But of course you can't select for columns you haven't grouped by.

Sorry, I can't think of any other ways to explain what I'm doing. But
thank you for your replies.

- John Burger
MITRE

On Wed, Nov 30, 2005 at 20:44:30 -0500,
"John D. Burger" <john@mitre.org> wrote:

That changes the semantics of what I want. If I group by personID
above, then every FOUR-way combo is of course unique. What I'd like to
do is group by the three attributes, and select for personID as well.
But of course you can't select for columns you haven't grouped by.

Assuming that personID is an ordered type, you can select max(personID)
in the GROUP BY and save the join at the end.

Bruno Wolff III wrote:

That changes the semantics of what I want. If I group by personID
above, then every FOUR-way combo is of course unique. What I'd like
to
do is group by the three attributes, and select for personID as well.
But of course you can't select for columns you haven't grouped by.

Assuming that personID is an ordered type, you can select max(personID)
in the GROUP BY and save the join at the end.

I'm not sure what this means - do you mean:

select p2.eyeColor, p2.hairColor, p2.skinColor
from persons as p2
group by max(p2.personID), p2.eyeColor, p2.hairColor, p2.skinColor
having count(*) = 1;

I don't know what that does. If you mean:

select max(p2.personID), p2.eyeColor, p2.hairColor, p2.skinColor
from persons as p2
group by p2.personID, p2.eyeColor, p2.hairColor, p2.skinColor
having count(*) = 1;

then I don't think that works either - if I include personID in the
GROUP BY, then the COUNT doesn't do what I want, right? I just want
uniques wrt the three attribute fields. If I group by personID, then
personID counts towards uniqueness.

Thanks for all the suggestions, folks.

- John Burger
MITRE

John D. Burger napisaďż˝(a):

select v1.pkey1, v1.field2, v1.field3, v1.field4
from view as v1
join
(select v2.field1, v2.field2, v2.field3
from view as v2
group by v2.field2, v2.field3, v2.field4
having count(*) = 1)
using (field2, field3, field4);

This is the one that takes eight hours. :( Another way to express
what I want is this:

select v1.pkey1, v1.field2, v1.field3, v1.field4
from view as v1
where not exists
(select true from view as v2
where v1.field2 = v2.field2
and v1.field3 = v2.field3
and v1.field4 = v2.field4
and v1.pkey1 <> v2.pkey1);

That looks like a horrible nested loop, but I suppose I should try it
to make sure it is indeed slower then the previous query.

Hi!

Did you try the second query? I guess I should take consirerably less
time than the first one. Usualy I do "these things" like this...
This is the only possibility for the planner to use indexes. The query
plan you send us shows that are mostly seq scans are used.

Regards,

Marcin Inkielman

"John D. Burger" <john@mitre.org> writes:

I don't know what that does. If you mean:

select max(p2.personID), p2.eyeColor, p2.hairColor, p2.skinColor
from persons as p2
group by p2.personID, p2.eyeColor, p2.hairColor, p2.skinColor
having count(*) = 1;

then I don't think that works either - if I include personID in the GROUP BY,

select max(personid) as personid, eyecolor, haircolor, skincolor
from persons
group by eyecolor, haircolor, skincolor
having count(*) = 1

--
greg

Greg Stark wrote:

select max(personid) as personid, eyecolor, haircolor, skincolor
from persons
group by eyecolor, haircolor, skincolor
having count(*) = 1

Aha, I understand Bruno's suggestion now! I was actually trying to
think of some way of using an aggregate on personid, but couldn't
figure it out. Of course max does just what I want in this case, since
max on one value gives that value - min and some other aggregate
functions would work too. Very clever!

On my actual problem, where "persons" is actually three joined tables,
my original query took eight hours. The new query, modeled after the
above, runs in almost exactly a tenth of the time.

Thanks for all the suggestions!

- John D. Burger
MITRE