ieb/sparsemapcontent — Issue #119: Improving the performance of walking all descendants of a given node
Author: marktriggs
Created: 2011-11-03 22:15:54+00:00
State: open

Hi Ian,

I've recently been looking at some of the performance issues that NYU have been seeing in production and I'm wondering if sparsemap could be enhanced to optimise a particularly slow usage pattern that I'm seeing.

To give a little background, we've been seeing requests to list 25 participants of a group (/var/search/groupmembers-all.json) take anywhere from 6 seconds or more--usually more like 10 seconds. I asked the NYU guys to strace the Nakamura JVM while one of these slow requests was running and found that most of the time was spent waiting for Oracle to respond. When I tallied up the different queries being run, here's what I got:

---------------------------------------------------------------------
Query Total Secs Times executed
---------------------------------------------------------------------
select 1 from DUAL 0.0042 1

select b from au_css_b where rid = :1 0.1597 26

select b from ac_css_b where rid = :1 1.3098 258

select b from cn_css_b where rid = :1 3.4691 652

select distinct a.rid 1.1882 337
from cn_css a, cn_css a0
where (a0.cid = :1 and a0.v = :2
and a0.rid = a.rid)
AND 1 = 1
---------------------------------------------------------------------

Around 1,200 queries for a single request. Oracle is generally responding within around 5ms (which seems fairly respectable) but the sheer number of queries is killing us.

After digging around I found two spots in Nakamura's Profile service that access sparsemap with a pattern like:

void doSomethingWith(Content parent) {
for (Content child : parent.listChildren()) {
// do something, then...
doSomethingWith(child);
}
}

That is, we're doing a depth-first walk of the entire tree of content nodes. In the case of the Profile service (which walks the nodes in a user's public authprofile) there are about 5 to 10 nodes to visit on average. Each node generates around 3 SQL queries--one for the call to listChildren, two to populate the properties of the content node, and the number of queries required blows out pretty quickly when we do this for 25 users. Plus, it does this twice, which doesn't help matters :)

I was wondering whether this access pattern could be captured directly by sparsemapcontent so that it could be optimised to avoid the need for all the tiny queries. I had a go at adding a new method called listDescendants() which uses Oracle's CONNECT BY statement to pull back the entire hierarchy in one hit, and then the properties of each content object by doing the selects in batches. My work so far is here:

https://github.com/marktriggs/sparsemapcontent/commit/c27887d64aa1106fd2bcfdabf76e3edf862ac759

I've verified that these changes resolve the performance problems we're seeing, but do you have any thoughts on this approach? Obviously my version only really helps people that are using Oracle, but I imagine people could come up with versions of the same thing optimised for other DB backends. If you think this code would be useful I'm happy to clean it up and submit a pull request, but would be equally happy with any other solution too.

Thanks,

Mark