Several ways to SQL pagination, including performance charts
use-the-index-luke.com
use-the-index-luke.com
On the other hands, approach Google takes seems more sensible to me, if you have more that some maximum number of results, just refuse to paginate further. Instruct the user to narrow down his query criteria instead. What could be the use for "go to page 1235 / 5433" if not for some kind of crawling database content?
Supporting sites like this starves quality sites.
I really don't think it is an advertising ploy, just a logic way to display long, structured content.