How to design a database for search history with multiple facets?
What you store should mimic what the user sees in the UI.  That way you can present it in a format that is familiar to him.

This format may, or may not, be anything close to the SQL that has ANDs and ORs.