Greg Stark wrote:
The sort of question I do need to answer is this: starting from individual
X, find all the ancestors and descendants for n generations. This involves n
iterations of a loop, joining the relatives found so far with the next
generation. If there are p people in the tree this has something like O(n
log p) complexity. On the other hand, if I stored all users' data in the
same tables and I had u users, this operation would have O(n log (u*p))
complexity. My guess is that it would be about an order of magnitude slower.
You're omitting the time spent finding the actual table for the correct user
in your current scheme. That's exactly the same as the log(u) factor above.
I hope not - can anyone confirm?
I have the impression that within a plpgsql function, the table lookup
cost happens once, and subsequent accesses to the same table are cheap.
In fact this characteristic has caused problems for me in the past,
see http://archives.postgresql.org/pgsql-general/2004-09/msg00316.php
I hope that the same is true of PQexecPrepared - can anyone confirm?
You might be interested in the ltree contrib module and gist indexes. You
might be able to do this recursive algorithm in a single indexed non-recursive
query using them.
I could use something like "CONNECT BY", though last time I investigated
I believe there were some stability concerns with the patch.
Unfortunately genealogies are not trees in anything other than the
informal sense of the word, so I don't think ltree is applicable.
The individual users' sites are entirely disjoint - there are no queries that
overlap them.
If you had a more flexible design you might find that you have a wealth of
data that you're currently not able to see because your design hides it.
I have a wealth of data that the majority of my users want me to keep
private. There are other sites that try to match up peoples'
genealogies, and I'm not competing with them.
Thanks for your suggestions Greg, but I think I know what I'm doing.
The Postgresql core copes well with this setup. It's just peripheral
things, like autovacuum and this stats writing issue, where poor big-O
complexity had gone un-noticed.
--Phil.
---------------------------(end of broadcast)---------------------------
TIP 4: Have you searched our list archives?
http://archives.postgresql.org
