A file search is going to be atrociously slow no matter what you do. On the upside, it is recursive.
A Calibre metadata search *might* be faster (especially subsequent searches), or it might murder your RAM and crash on a Library of that size ^^.
(That's the "Find a book in calibre catalog" entry just above file search. It's extremely badly worded, as it has nothing to do with catalogs, and everything to do with the calibre metadata flat db that everyone gets as long as you use "Send to Device".
Remind me to reword it.).