Thanks @mflorea for your answer. Very useful.
So for the usage I have in mind (it’s a wiki where all pages have UUID-generated names), any solution that doesn’t filter/order based on the title is not going to cut it. Thus I’d like to estimate the cost of implementing a title cache.
I’ve started a thread to brainstorm about it at Title Cache Design