Re: [web-devel] Join support in persistent

On Sat, Apr 2, 2011 at 11:50 PM, Michael Snoyman wrote:

On Sun, Apr 3, 2011 at 9:40 AM, Greg Weber wrote:

...

[snip]

I think you're solving a different problem. Are you talking about the

...

fact that the EntryAuthorIn constructor takes a list instead of a Set? That's not where the slowdown comes from. Actually, for the current backends, a set would needlessly slow things down, since the In constructor simply converts things to SQL and lets the database do the work.

I'm not sure what you're suggesting here to be honest, can you clarify?

An O(m + n) implementation instead of O(m * n) by using constant lookups instead of repeatedly searching through a list.

But where will you use the Set? The slowdown is because we end up with two lists: [(Key one, one)] and [(Key many, many)]. For each (Key one, one), we need to filter the entire [(Key many, many)] to find the records which match each one. As far as the code is concerned, doing the initial filter to the relevant (Key many) values is constant*.

We end up with 2 lists because we are building 2 lists. We should build data structures that allow for an efficient implementation of this function. Greg [snip]