Re: optimizing a query over tree-like structure

Hi, Svil

I 'd like to first fully understand the background of your problem before 
figurin out if I can be of any help (or not).

You have a tree, of which N is the root, is this correct?
Then, what are the next sublevel?
F, P and R? If so, why is R linked to a sibling (F) ?
And the next one?
O and Z?
Is O connected to itself?
And i am not understanding your concept of "shortcuts". Could you please 
explain ?
What kind of tree do you have exactly? Binary? Trenary?
The mm_* tables keep relations between nodes, I guess.... If so , the mm_N2Z 
one is empty, in this example, right?As there is no edge from N to Z (not 
direct).
But what is the Nazn table? What records does it keep?
And what is the ownership table? And the value?
Could you tell which columns these tables have, at least the relevant ones 
for your problem ?

Please kindly advice me on these issues.
I am not very specialized in optimizing queries, but I see you have a lot of 
cartesian products on your FROM clause, which, from my own experience,
I guess it has tendency to be slow...

Best,

Oliveiros

----- Original Message ----- 
From: <az@svilendobrev.com>
To: <pgsql-sql@postgresql.org>
Sent: Tuesday, September 30, 2008 9:32 AM
Subject: [SQL] optimizing a query over tree-like structure


> 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
>
> -- 
> Sent via pgsql-sql mailing list (pgsql-sql@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-sql