Normally, if you are entering search criteria in only 4 fields, the presence or absence of other fields in the same record should not affect the search speed.
How many records are in the table of the layout where you perform your search?
What type of criteria, typically, do you use in the search?
Do you see a progress bar when you perform the search and it's slow? How is the progress bar labeled?
Is the server on you local network or do you connect to it via the internet or VPN?