On Fri, Mar 7, 2008 at 1:26 AM, Jared Williams <jared.williams1(a)ntlworld.com> wrote: Of course! Thanks, Magnus

Yeah did notice that, think it could be replaced with something like. SELECT ci_page FROM {$table_categoryintersections} WHERE ci_hash IN (implode(',', $hashes)) GROUP BY ci_page HAVING COUNT(*) = count($hashes) LIMIT $this->max_hash_results Yeah, I think chances of hash collisions are unlikely, whats far more likely is someone recategorizing a page after a search. Which means the double check could be removed. Jared

On Fri, Mar 7, 2008 at 5:00 PM, Magnus Manske <magnusmanske(a)googlemail.com> wrote: Manually calculating all intersections beforehand isn't terribly elegant either. :) Later versions mostly gain new features that contribute nothing to performance, which is what we care about. In most cases, MySQL internally rewrites subqueries to joins or worse anyway, so it's not like you gain much. Try running EXPLAIN on the query. I'd expect to see a temporary table created with intermediate results at each step: want to prove me wrong? Almost certainly doesn't help, as I said. I would be surprised if subqueries worked with any kind of remotely acceptable efficiency. And too much network latency, and too much network traffic. You're talking about megabytes being sent either way in the worst case, with intersections of hundreds of thousands (consider Men intersect Living people, with flattened categories so that Men is properly populated). The most extreme would be to just store every possible intersection individually. This isn't quite as insane as it sounds, since almost all intersections would be empty, and so not stored. It would result in exponential storage requirements in the number of rows per article, however, specifically 2^n - 1 rows per article (the number of nonzero bit patterns in n bits, if you like). For an article with 50 or even 20 categories this would obviously be ludicrous, so some compromise would be necessary. If you stored up to four or five, it would only be five or four joins for even a 20-way intersection, but I haven't calculated the storage requirements of that (got to go in a minute). Nor am I sure of the efficiency in other ways. It's not like fulltext is O(1) in the number of search terms, or the number of categories per page. Maybe I'm totally wrong. But I expect it to work better, is all. It will certainly handle subtractions, which are valuable and not conceivably possible to cover in your scheme, as far as I can tell. It's also a proven technique used by more than one popular software product for tag intersection, AFAIK. Well, I'm not going to tell you what to spend your time on. It's always good to have a plurality of ideas. It's not the approach I'd focus on first, but what do I know?

On Fri, Mar 7, 2008 at 12:15 PM, Ilya Haykinson <haykinson(a)gmail.com> wrote: We know. DPL is not suitable for use on large wikis. On Fri, Mar 7, 2008 at 12:17 PM, Jared Williams <jared.williams1(a)ntlworld.com> wrote: I'm not going to spend too much time parsing that, but it's an automatic filesort of the entire set included by the WHERE clause, i.e., the union of all the category intersections in question, since MySQL doesn't support loose index scans for WHERE x IN (...) GROUP BY y. Repeated join seems likely to be faster, although maybe not, I haven't benchmarked it or anything. It's not just unlikely, it's so unlikely as to be impossible to all intents and purposes, barring deliberately-constructed collisions (which are possible with MD5, although maybe not for such short strings, I forget). Worry about a meteor wiping out the data center before you worry about MD5 collisions by chance on sets with cardinality in the billions.

On Fri, Mar 7, 2008 at 2:56 PM, Jared Williams <jared.williams1(a)ntlworld.com> wrote: Well, no. There's a major difference between data that's stale and data that's totally wrong. Getting results that have, I dunno, [[Che Guevara]] in [[Category:Terrorists]] despite the fact that someone removed him ten seconds before is rather different from a [[Category:Terrorists]] that contains [[Heart of Atlanta Motel v. United States]].

On Fri, Mar 7, 2008 at 3:18 PM, Jared Williams <jared.williams1(a)ntlworld.com> wrote: It's still "right" technically. The results are accurately reflecting the actual contents of the database at a definite point in time. That's all integrity asks for. Returning results that were never correct just because of bad hashing algorithms is something completely different. It's the difference between your stock ticker being five minutes outdated, and generating entirely random numbers sometimes. To say there's no difference, or that the former makes the latter okay, is ridiculous.