Enabling folder references will build an index on the server

Failing that, you can do it non-indexed, and take the performance hit.

Seaching for the parent folder involves one or the other.

You could pull a database down to a local client or replicate it to another server and index folder references there. Again, this has distinct performance hits until the index is completed.

& Of course you could also put the doc in a folder if you like ... then it'll appear in that folder. But that's probably not what you're trying to do.