For the record, I just tested the actual load time and data transfer out of the mysql database using such a setup.
Setup
GC: Enterprise 2.4.0
Hardware: Virtual machines running on amazon mysql aurora database t2.small (2GB ram) and amazon linux instance on a t2.micro (1GB ram).
Crud: List a single record in a table with setRelation against a large database of about 90.000 records.
Cache: Off
Environment: Development
Results
Time to load List/Edit/Add view: 10-20 seconds
Data transfer out of database: ~20MB for every request to see one of the views List/Edit/Add
This is similar to what I have previously seen and in the range of nasir123's observations.
I believe the best way to deal with this would be to add some functionality to the core. There could be a setRelationDB or even an automatic detection if we could live with a extra query.
Anyway, in any form dealing with this in the List view would probably be the easiest part, since we only need to prevent the data fetching of the whole corresponding relational table and replacing the dropdown menu with the already implemented Quick Search box (I have already unsuccessfully tried to do this with the api tools).
Dealing with this in the Add and Edit view is another story. One way could be to add dummy field with search functionality, using a tool like Select2 or similar, passing data to the raw ID of the collumn you would normally set relation to. Such solution would however require an endpoint where the searchbox would fetch data from.