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: (view raw or whole thread)
Lists: pgsql-sql
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 
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,  

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
 N.dbid = ownership.N
 N.dbid = mm_N2R.left AND mm_N2R.right = ownership.R
 N.dbid = mm_N2P.left AND (
     mm_N2P.right = ownership.P
     mm_N2P.right = mm_P2O.left AND (
         mm_P2O.right = ownership.O
         mm_P2O.right = mm_O2O.left AND (
             mm_O2O.right = ownership.O
             mm_O2O.right = mm_O2O1.left AND 
                mm_O2O1.right = ownership.O
 Nazn.dbid = mm_N2F.left AND (
     mm_N2F.right = ownership.F
     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 
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 
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


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-2015 The PostgreSQL Global Development Group