Skip site navigation (1) Skip section navigation (2)

optimizing a query over tree-like structure

From: az(at)svilendobrev(dot)com
To: pgsql-sql(at)postgresql(dot)org
Subject: optimizing a query over tree-like structure
Date: 2008-09-30 08:32:51
Message-ID: 200809301132.51493.az@svilendobrev.com (view raw or flat)
Thread:
Lists: pgsql-sql
hi.
sorry for the vague syntax used below, but the query is huge so i've 
tried to present it in simple terms. And sorry if i'm doing obviously 
stupid things, i have lots of years programming behind me but NO sql 
involved.
i have a somewhat tree-like structure of objects that link to each 
other via many2many associations. it looks like:
(N is "root")
 N links to R,P,F
 R links to F 
 P links to O,F
 O links to O,F #recursively
 F links to Z
All links to F but the one in O are "shortcuts", to avoid looking it 
up recursively.
each of these objects has some associated values (again many2many,  
ownership).

what i want is to get all the values related to a given N and its  
sublevels, in one query.

one variant of what i've invented so far is (~pseudocode, no recursion 
on O):

SELECT ownership.*, value.*
FROM Nazn, mm_N2P, mm_P2O, mm_O2O, mm_O2O AS mm_O2O1, mm_N2Z, 
     ownership JOIN value ON ownership.value = value.dbid
WHERE (
 N.dbid = ownership.N
 OR
 N.dbid = mm_N2R.left AND mm_N2R.right = ownership.R
 OR
 N.dbid = mm_N2P.left AND (
     mm_N2P.right = ownership.P
     OR
     mm_N2P.right = mm_P2O.left AND (
         mm_P2O.right = ownership.O
         OR
         mm_P2O.right = mm_O2O.left AND (
             mm_O2O.right = ownership.O
             OR
             mm_O2O.right = mm_O2O1.left AND 
                mm_O2O1.right = ownership.O
 )))
 OR
 Nazn.dbid = mm_N2F.left AND (
     mm_N2F.right = ownership.F
     OR
     mm_N2Z.right = ownership.Z
 )
) AND ownership.value = value.dbid AND N.obj = whatever-filter-by-N

----------------
this scales very poor. 
it uses the shortcut to F present in N.
for just 200 rows with related associations, it takes 4 seconds to get 
result.
if i use the shortcut to F present in P, it takes 2 seconds - but 
thats still inacceptable.
seems that the number or consequtive ORs on same level is killing it.
EXPLAIN gives nested loops all over.
What am i doing wrong here? 
should i expand the A-to-B links of the sort 
mm_N2P.right = mm_P2O.left 
into 
mm_N2P.right = P.dbid and P.dbid == mm_P2O.left ?

the query is generated via sqlalchemy and a layer on top, so i can 
tweak it any way required (and it has many other sub/filterings which 
i've ommited for brevity - they dont make it better/worse).

any pointers of how such queries should be written are appreciated - 
e.g. what is considered fine, what doable and what is a no-no. 

thanks ahead
ciao
svil

www.svilendobrev.com
dbcook.sf.net

Responses

pgsql-sql by date

Next:From: Glenn GillenDate: 2008-09-30 12:16:06
Subject: Can COPY update or skip existing records?
Previous:From: Steve MidgleyDate: 2008-09-30 06:05:32
Subject: Re: Finding sequential records

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group