Magnus Manske wrote: A mysql integer is 32 *bits* while a md5 hash has 32 *characters* when expressed in hexadecimal (16 *bytes*). If you want a 4-byte hash, maybe you could use Crc32. What's its collision resistance without the NUL char? Other than that, it *could* work.

On Fri, Feb 29, 2008 at 5:28 AM, Magnus Manske &lt;magnusmanske(a)googlemail.com&gt; wrote: Actually, there are on average only 2 categories per page, it seems: 12,000,000 page rows and 25,000,000 category rows. Of course, that doesn't just count articles. You're double-counting. It's only 10 intersections: A|B is the same as B|A. (For the purposes of storage, of course, you'd want to consistently pick one of the two categories to go first in the hashed string, say the ASCIIbetically first. So you'd store B|A as A|B, since A < B. Or whatever.) It would be smaller, probably. Categorylinks is int, varchar(255), varchar(86), timestamp, which is 4 + ? + ? + 4 bytes, with the ?'s being pretty large. And that's duplicated a few times for various indexes. Even if you go for a 64-bit hash, your table data is still only 12 bytes per row, with the primary key (page_id, intersection_hash) taking no additional storage and a reverse key taking another 24 (or maybe 12? is it that smart?) bytes per row. For a point of comparison, on my old dump of simple-wiki, categorylinks has 39671, and the length is 3637248 for data and 4980736 for indexes. That makes 217 bytes per row average. The table you propose should be only 36 bytes per row, if I'm not wrong, plus I guess some percentage overhead for various things. I think the percentage will be pretty large: an InnoDB table I have that's just (int, int, int) is 53 bytes of data per row, not just 12. But still, your table should be considerably smaller per row than categorylinks. Of course, the number of rows used is not going to be proportional to the average number of rows per page, but the average of the square of the number of rows per page. Specifically it will be equal to the sum over all pages of n(n-1)/2 (where n is the number of categories on that page), so pages with one category contribute nothing, but those with 20 categories will give you an extra 190 entries. So whether it will be more or fewer than four times the rows depends on the distribution of categories. Still, it should be not much larger than categorylinks, at worst. The idea is interesting, and might have merit. Certainly simple lookups would be very fast, even lookups of three or perhaps four categories. It's not quite as flexible as fulltext search (where you can do arbitrarily large intersections, and subtractions too), but it could be that it's faster. I don't *see* any pitfalls.