pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feeddum query plan: more info.
3+ messages / 3 participants
[nested] [flat]
* dum query plan: more info.
@ 2003-04-16 22:02 Jonathan Moore <moore@discern.com>
0 siblings, 2 replies; 3+ messages in thread
From: Jonathan Moore @ 2003-04-16 22:02 UTC (permalink / raw)
To: pgsql-performance
I now under stand that my join was rong but none of the seguestions are
the optimal solution to the problime. You can make this order n if you
try. The trick is to use a mearg join using sorted list of the unique
keys in each colum join. The question you are asking is what left hand
entrys do not exist on the right.
select A.left form pairs A, pairs B where A.left != B.right;
(note: my code in the first example select left form the rong table but
it dosn't change the search.)
take the DB:
(1,2)
(2,1)
(1,5)
(4,5)
(5,2)
Sort the colums:
left right
==== =====
1 1
2 2
4 5
5
Start at the top you see that you have 1 in both columes there for you
know that 1 is not a answer. pop both colums. same for 2. Whe you get to
the top of the lists as 4, 5; you know that 4 apperas on the only in the
left colum as you don't see it on the right. pop the left colum. now you
see that 5 is on both sides so 5 is not a canadate. You are out of
options so you are done 4 is the only value that is on the left and only
on the left.
This methoud is order O(n) if both colums have b-tree indexes so you
don't have to pre sort them othere wise it is O(n*log(n)) as the sort is
the greatest complexity. In eathere case it is way better then O(n^2)
for almost any n.
I have this implmented in my code by selecting each colum and then doing
the mearg my self more expensive then a in db join as there is pointless
data copys.
sudo perl for the hole thing is:
#!/usr/bin/not-realy-perl
my @left = select distinct left_entry from entry_pairs order by
left_entry;
my @right = select distinct right_entry from entry_pairs order by
right_entry;
my @only_left;
while (1) {
if (not @left) {
last; #done
}
elsif (not @right) {
push @only_left, $left[0];
pop @left;
}
elsif ($left[0] == $right[0]) {
pop @left;
pop @right;
}
elsif ($left[0] < $right[0]) {
push @only_left, $left[0];
pop @left;
}
elsif ($left[0] > $right[0]) {
pop @right;
}
}
-Jonathan
^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: dum query plan: more info.
@ 2003-04-17 16:24 Manfred Koizar <mkoi-pg@aon.at>
parent: Jonathan Moore <moore@discern.com>
1 sibling, 0 replies; 3+ messages in thread
From: Manfred Koizar @ 2003-04-17 16:24 UTC (permalink / raw)
To: Jonathan Moore <moore@discern.com>; +Cc: pgsql-performance
On 16 Apr 2003 15:02:49 -0700, Jonathan Moore <moore@discern.com>
wrote:
>select A.left form pairs A, pairs B where A.left != B.right;
>
>take the DB:
>
>(1,2)
>(2,1)
>(1,5)
>(4,5)
>(5,2)
>
>[...] 4 is the only value that is on the left and only
>on the left.
But this is not the answer to your SQL statement. The correct answer
is:
left
------
1
1
1
1
2
2
2
1
1
1
1
4
4
4
4
4
5
5
5
(19 rows)
What you are looking for is more like
SELECT left FROM pairs
EXCEPT
SELECT right FROM pairs;
>This methoud is order O(n) if both colums have b-tree indexes so you
>don't have to pre sort them othere wise it is O(n*log(n)) as the sort is
>the greatest complexity. In eathere case it is way better then O(n^2)
>for almost any n.
And I'm sure it will not take O(n^2) time in Postgres.
Servus
Manfred
^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: dum query plan: more info.
@ 2003-04-17 16:31 Tom Lane <tgl@sss.pgh.pa.us>
parent: Jonathan Moore <moore@discern.com>
1 sibling, 0 replies; 3+ messages in thread
From: Tom Lane @ 2003-04-17 16:31 UTC (permalink / raw)
To: Jonathan Moore <moore@discern.com>; +Cc: pgsql-performance
Jonathan Moore <moore@discern.com> writes:
> I now under stand that my join was rong but none of the seguestions are
> the optimal solution to the problime. You can make this order n if you
> try. The trick is to use a mearg join using sorted list of the unique
> keys in each colum join. The question you are asking is what left hand
> entrys do not exist on the right.
In that case maybe what you are after is
select a.* from a left join b on (a.left = b.right) where b.right is null;
which is a pretty grotty hack using the outer-join rules, but should
work efficiently.
regards, tom lane
^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2003-04-17 16:31 UTC | newest]
Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2003-04-16 22:02 dum query plan: more info. Jonathan Moore <moore@discern.com>
2003-04-17 16:24 ` Manfred Koizar <mkoi-pg@aon.at>
2003-04-17 16:31 ` Tom Lane <tgl@sss.pgh.pa.us>
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