Look at blogger urls (the updated-max parameter; reddit does something similar as well) to see an efficient and bookmark-friendly implementation of pagination. I disagree that /page/4/ style urls are a product of database-driven design; that seems to be driven by url legibility, a book metaphor, and convention. Total counts and large offsets are bad for databases because they involve many rows rather than the minimum necessary local information.