Evan Martin wrote:
Why not cache prerendered versions of all pages?
As Brion already mentioned, we're already doing this, but even more:
One tricky part is that writes to page B can affect page A if page A has a link to B. A reverse index of links would solve this, though I don't know how bit it'd be.
We have a table, 'links' I think, which stores all links between pages. The 'from' of each link is the numerical page ID (so we don't need to update it when the page is moved), and the 'to' is the namespace and title (so we don't need to update it either when a page is moved because we really do want the link to continue to go to the old title). The only overhead incurred is that when saving an edit, we need to update this table with the links that were added or removed from the article, and when an article gets deleted links to the deleted page may need to be moved to 'brokenlinks' (another table; its purpose should be obvious now) and links from that deleted page need to be deleted.
So yeah, we already have a reverse index of links, and we already use it in a lot of places (the most user-visible one being [[Special:Whatlinkshere]]).
There are separate tables for 'categorylinks', 'imagelinks' and others that I can't think of now.
Timwi