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

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/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQFDjUz6IB7bNG8LQkwRAmnDAJ4s2o7D0C1hEjJl/LdedlidaOMxJgCfUEBf
y2aMBR6ISBsLRsLyx/Z6RRQ=
=tTHk
-----END PGP SIGNATURE-----

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

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

http://archives.postgresql.org

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)


---------------------------(end of broadcast)---------------------------
TIP 1: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql.org so that your
message can get through to the mailing list cleanly

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


---------------------------(end of broadcast)---------------------------
TIP 5: don't forget to increase your free space map settings

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/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQFDjf3nIB7bNG8LQkwRApF1AJ4w1WM7Fcz8n+XxTPMI4I BGBqmqTgCfVyJv
PIy9uWKFzYUM/gibciBuUTg=
=sdoD
-----END PGP SIGNATURE-----

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?


---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match

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


---------------------------(end of broadcast)---------------------------
TIP 1: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql.org so that your
message can get through to the mailing list cleanly

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.

---------------------------(end of broadcast)---------------------------
TIP 5: don't forget to increase your free space map settings

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

---------------------------(end of broadcast)---------------------------
TIP 6: explain analyze is your friend