[web-devel] Join support in persistent

[Greg Weber]

On Sat, Apr 2, 2011 at 11:50 PM, Michael Snoyman <michael at snoyman.com>wrote:

>
>
> On Sun, Apr 3, 2011 at 9:40 AM, Greg Weber <greg at gregweber.info> 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]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/web-devel/attachments/20110403/06a9670e/attachment.htm>