David ... a problem with most/all of the ideas above is that PG's not going to do an indexed scan on the table containing the potential parents, but rather a sequential scan - which is the problem.in a nutshell.
The current scheme I've got leads to simple enough queries to find all parents, once you get the hang of it:
select parents.*
from foo_table parents, foo_table child
where child.foo_key = :foo_key
where tree_ancestor_p(parents.tree_sortkey, child.tree_sortkey);
The trick is to come up with a query that will use the index on parents.tree_sortkey, which this query will not.
Generating the correct prefixes via a recursive SQL function would allow you to say something like
select parents.*
from foo_table parents, foo_table child
where child.foo_key = :foo_key
and parents.tree_sortkey in tree_ancestor_sortkeys(child.tree_sorktey);
but, alas, this will not use the index on parents.tree_sortkey either.
Now ... generating the list of parent sortkeys separately and passing a list of literal tree_sortkeys as the right operand to "in" might do so ... but I'm not sure. I may do some testing.
But ... using the GiST index method and defining proper "contains" and "contained by operators would use the index on tree_sortkey and be readable, as well ("@" is the PG "contains" operator):
select parents.*
from foo_table parents, foo_table child
where child.foo_key = :foo_key
and child.tree_sortkey @ parents.tree_sortkey;
But this is going to have to wait a bit ...
