Need help designing a search method for a database.

I have a large dataset stored in a spreadsheet that I want to be able to search on using multiple words and returning matches on every rows that contains ALL of the search words. Similar to using Google Image Search. How do to do this? My sheet has nearly 4000 rows in it and spans about 12 columns. I plan for the Search usage to be on a separate Sheet page. All suggestions welcome.