Storing Search Histories - Remove Duplication Without Affecting Performance

In our product we show search histories on the UI, means what ever user searches we make a history for that search in the database and show it on the UI.

At present we show duplicate histories also. for ex- if a user do a search with some criteria (say, abc), now if the user do search again with same criteria (abc), we show it twice on our history page.

What we need to do -

we need to remove the duplication, and only to show the search histories once if they have same criteria. also we need to save it only once in the database. means we neither display the same search histories nor store them in the database. ofcourse if we store it only once, it will be displayed only once. so we need logic in our storing part here.

Approaches we are trying -

Approach 1 - We thought to remove duplicate search histories by comparing their criteria's, but here the problem is that single search history itself can have so many criteria's and we store around 30 search histories in the database, so if we compare criteria of all of them one by one. we will loose the performance. so we dropped this approach.

Approach 2 - The second approach we are thinking is, at the time of creation of search histories, we will generate checksum based on their criteria, so if the criteria is same for two search histories the checksum generated would be same, and before creating (storing into database) the search history we first check if the checksum is already exist in the search history table for any search history or not, if it is already there, don't create the search history, as it is already there.

The problems with this approach is -

First Problem - we will need to create one more column in the Table which will impact our upgrade process, and we don't want to have an upgrade impact.

Second Problem - if user changed the sequence of criteria of search, for e.g. name criteria first and then number criteria but the values are same. and in the another search number criteria first then name criteria and values are same as first search, here the search results would be same as the criteria are same but only the sequence is different, so in this case two histories will get created (as we generate checksum based on criteria so if sequence gets changed checksum would also be different), however we want only one search history in this situation. we don't want to consider the sequence.

We store the search histories in XML format and we convert this xml to blob to store it into database, i thought to first sort them then generate checksum, but as they are in xml format, so i can't even sort them because the tags are similar to all the criteria's.