Re:Probabilistic Many-to-Many Relationships (with Bloom Filt...
by wiredfool on Friday August 31, 2012 @03:00PM
(#4461159)
Here's his problem:
-> Seq Scan on movie_person (cost=0.00..10117.01 rows=97 width=8)
(actual time=2.540..59.933 rows=9 loops=1)
Filter: (person_id = 160)
If he had an index on movie_person, that would be a ~ 1ms index lookup, not a table scan. You can't do that sort of database layout without putting indexes on the M2M mapping table.(edit, oh, yeah, it's right there in the parent post....)
Re:Probabilistic Many-to-Many Relationships (with Bloom Filt...
by nierman on Friday August 31, 2012 @03:08PM
(#4461201)
and you probably want to include these indices in any case to enforce that a given (user, movie) pair in the join table is unique (unless you want to track if a rating was changed and when, etc.)
further, you might decide to cluster on the index or partition.
Re:Probabilistic Many-to-Many Relationships (with Bloom Filt...
by wiredfool on Friday August 31, 2012 @04:13PM
(#4461485)
Yep. You'd probably wind up wanting two indexes, a unique one on user,movie and then possibly one on movie only, to speed lookups the other way.
Re:Probabilistic Many-to-Many Relationships (with Bloom Filt...
by alxv on Friday August 31, 2012 @01:17PM
(#4460652)
His query took 65 milliseconds, not 65 seconds, which is totally reasonable.
Re:Probabilistic Many-to-Many Relationships (with Bloom Filt...
by tmoertel on Friday August 31, 2012 @01:22PM
(#4460681)
Thanks for pointing that out. I totally misread the bottom line. Once I had it in my head that those were seconds, no amount of looking at that little "ms" behind the numbers was going to show me anything different.
Re:Probabilistic Many-to-Many Relationships (with Bloom Filt...
by jaekwon on Friday August 31, 2012 @03:59PM
(#4461423)
Skimmed through it, but it seems that there is still an improvement with the bloom filter with a factor of 2~3. Is that correct? (estimated 6(?)ms once corrected with indices, vs 2ms with the bloom)
Re:Probabilistic Many-to-Many Relationships (with Bloom Filt...
by wiredfool on Friday August 31, 2012 @04:20PM
(#4461513)
This sample set is way too small to be arguing about a millisecond here or there. The variation from what's cached, or if something else happens on the machine, or whatever is going to affect the benchmarks. For a 'real' benchmark, I'd like to see a few gigs of data, or something that's not going to fit in cache. The real gain from the bloom filter is going to be in a 4-10x reduction in the working set for the same amount of data. But when the working set is trivial, then the fluctuating and fixed overheads are going to dominate.
I'd also like to see how good the bloom filter's indexing is at scale, or if it winds up being some sort of table scan.
Re:Probabilistic Many-to-Many Relationships (with Bloom Filt...
by tmoertel on Friday August 31, 2012 @05:45PM
(#4461824)
For a "real" benchmark, I'd like to see the query repeated until the response-time distribution stabilizes. Then take the response time at the 90th, 95th, and 99th percentiles, and also the mean. Actually, I'd like to see the CDF plot for the whole distribution.
Re:Probabilistic Many-to-Many Relationships (with Bloom Filt...
by tmoertel on Friday August 31, 2012 @04:58PM
(#4461671)
My hunch is that, in the original environment, PostgreSQL with the right indexes would be as fast as the bloom filter. I emailed the OP about adding an index on movie_person(person_id), and he (besides being very cool and gracious about everything) said that he was going to add it and re-run his timings. I suspect will see new results soon.
I think the reason that OP's join-based queries are slow is that there are no indexes over his junction table's foreign keys:
Thus when he wants the movies associated with person 160, the database must examine the entire junction: Note the sequential scan on movie_person that accounts for 2.5 to 60 seconds. If there were an index on movie_person(person_id), this could be an index scan.(EDITED TO ADD: I totally misread the timings in milliseconds for timings in seconds, so most of what I originally wrote is off by a factor of 1000. I'm leaving it here for entertainment value and because you might want to play with the data set in SQLite. But my point is still valid: a vanilla join is comparable in performance to the OP's bloom-filter method.)
I'm having a hard time believing that the straightforward join on a data set as small as the OP's sample is really going to take 65 seconds on PostgreSQL. Maybe that's what EXPLAIN predicts (with spotty stats, I'd wager), but EXPLAIN is not a reliable way to measure performance. For this data, I'd expect real queries to perform much better.
EDITED TO ADD: The OP's article shows the results for EXPLAIN ANALYZE, which ought to have performed the queries. So I'm not sure why the results are so slow.
Heck, even SQLite, when processing a superset of the data set on my 4-year-old computer, can do the OP's final query (and return additional ratings data) almost instantly:
If you want to try some queries yourself, here you go: Fully enumerating the joined data takes under a second: And even going so far as to print the joined data takes under six seconds: Sometimes, the old stuff works better than we give it credit for.