pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Jonathan Moore <moore@discern.com>
To: pgsql-performance@postgresql.org
Subject: dum query plan: more info.
Date: 16 Apr 2003 15:02:49 -0700
Message-ID: <1050530569.20873.120.camel@spunge-bob> (raw)

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




view thread (3+ messages)  latest in thread

Message-ID: <1050530569.20873.120.camel@spunge-bob>
Permalink:  ../1050530569.20873.120.camel@spunge-bob/
Also on:    postgresql.org/message-id/1050530569.20873.120.camel@spunge-bob

 · 

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-performance@postgresql.org
  Cc: moore@discern.com
  Subject: Re: dum query plan: more info.
  In-Reply-To: <1050530569.20873.120.camel@spunge-bob>
  References: <1050530569.20873.120.camel@spunge-bob>

* 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