I have been doing work on tables over 130000 rows in a share point list. Whilst I use the filter command and use the double pipe || to act as an OR command I have it filter across a number of columns.
Filter(
NEWVOID, StartsWith(PostCode,searchTerm)||
StartsWith(UnitID,searchTerm)||
StartsWith(AddressClean,searchTerm)||
StartsWith('Primary Customer',searchTerm)||
StartsWith(CRef,searchTerm)||
StartsWith(Mobile,searchTerm)
)
I would consider limiting the columns to filter but the key is as described above to stop the filter searching on each keystroke. So I have put a search button in tied to the gallery but make it wait for the press so that there is one call on a reduced dataset. UpdateContext({searchTerm: TextInput_Item.Text}).
Hope this helps.