Hi Martin,
I believe that you aren't looking for a solution way how this could be implemented in general but how to cope with these amounts of data. Just in case I'm wrong I attached an image showing how to implement something like this in general. The only difference to your case is, that I'm connecting only two tables. I selected in which fields the user can search and changed the picker search mode, other tab, to contains. At least this would be the option if you can access the data by SQL. Otherwise you would need to have some rest/soap method. If you are using these you shouldn't do the searching with BPS but send the picker value to the server itself.
Back to topic in case you can connect to the data using SQL:
One performance improvement would be to define a view in the database. Than the SQL Server can build up some plan to improve the performance. He can't do this if you define the SQL in BPS.
Than there are "indexed views" I haven't worked with these but they could improve the performance even more.
If you can't connect directly to the server one approach would be to created a connection between the SQL server hosting BPS and the customer database. Than you could create the view on the BPS Server, which references the linked server. This may be necessary if the source database has been setup to be case sensitiv. You could change the collation to case insensitive in the view and than the user can find the data written in upper and lower case.
Regards,
Daniel