I am really interested in this argument, because I am currently converting a mysql based web search to use apache solr. I have been thinking about all the arguments about pagination a lot.
The thing I don't know about, though, is the "database is almost always the most constrained part of a solution". On this simple site search, we tend to notice the apaches taking a lot more cpu than the databases calls. I guess when our site gets bigger, you'd imagine it is easier to scale out the apaches than the database (with sharding), but we would still have a lot of room to improve the mysql layer anyway (memcached for example).
