Tag Archives: search

Inverted search in MySQL database: check if keywords in field match some text

Usually, “searching a database” means looking for rows that contain a “document” in a field that matches a certain keywords set (mostly using the MATCH AGAINST construct); let’s say you want to do the opposite instead, that is finding those rows that have a field containing keywords, or a phrase, that matches to a text you already know. This is what I call an inverted search, or reverse search.

Real-life scenario: you build a website for job offers, candidates come in searching for listings that suit them, but find none, or find just a few that are not satisfactory. Either they keep coming to the website doing a search (let’s say they use the keywords “veterinar* cat” because they want to take care of animals, and like cats above all), or they subscribe to the RSS feed for that search (if your site offers one)… or they “save” this preference, and have the site send them an email as soon as a new offer pops up that matches their search, and this is where this article comes in.

Now, it’s easy to save the keywords for each user in a MySQL table, but how easy is it to check if the text of new messages matches said keywords? In PHP, you would go about building an array of keywords, and using strpos() on each of them to see if they are all contained in the text.

In MySQL you have the INSTR() which is the equivalent of PHP’s strpos(), but you cannot store arrays in a field (I mean real arrays, not serialized ones), and storing as many rows as the keywords are is going to be troublesome, as normalization isn’t needed: a “set of keywords” is mostly unique to each user subscribing to a search, so it makes sense to store them in a text field in the form of “keyword1,keyword2,keyword3,…”; again, if you were in PHP, you would do a explode(“,”,$keywords) to obtain the array of keywords, but in MySQL there is no such function, so you pretty much have to create one.

Ideally, you need a function where you pass the known document/text to match against (the concatenated subject and the body of the job offer, in this example), the string in the form “keyword1,…,keywordN“, and a parameter which tells the function that the delimiter (“glue” in PHP’s explode/implode) is a comma, so:

somefunction(document, keywords, delimiter)

This function would then return a positive integer if all of the keywords are present in the text, or 0 otherwise.

The function I put together by scraping info around was:

DELIMITER ;;

DROP FUNCTION IF EXISTS `matchkwdarray`;;
CREATE FUNCTION `matchkwdarray`(`str` text, `arr` text, `delimit` tinytext) RETURNS char(1) CHARSET utf8
 DETERMINISTIC
BEGIN
 DECLARE i INT DEFAULT 1;
 DECLARE matches INT DEFAULT 1;
 DECLARE token TINYTEXT;
 label:WHILE(matches>0) DO
 SET token=replace(substring(substring_index(arr, delimit, i), length(substring_index(arr, delimit, i - 1)) + 1), delimit, '');
 IF token='' THEN LEAVE label; END IF;

 SET matches=INSTR(str, token);
 SET i=i+1;
 END WHILE;
 RETURN matches;
END;;

DELIMITER ;

To add this to your MySQL database, you can either connect via CLI, or, as most people with a website on a shared hosting, not having command-line access, using a database frontend; phpMyAdmin, bloated as it is, doesn’t support functions/routines, so you need another one, and I found Adminer to be a massively better alternative, performance and flexibility-wise, and it’s only a 150kb-something single PHP file, which makes it all the better.

So, when you test the function, you have the following:

SELECT matchkwdarray('this is just a very simple test', 'just,test', ',')
Returns: 2

SELECT matchkwdarray('this is just a very simple test', 'some,stuff', ',')
Returns: 0

SELECT matchkwdarray('this is just a very simple test', 'this,very,stuff', ',')
Returns: 0

The function is resource efficient: as soon as a keyword is not in the text, it stops processing the keywords array. Surely, if you don’t want a 100% match but are fine with lower than that, you can easily modify the function to “stream” the whole keywords array, even removing the last character off each keywords to allow some variations, and return a percentage match which you can then evaluate later on.

PHP search string functions performance is “needle” dependent

I was playing with some templating benchmarks in my post before this one, and bumped into an interesting find regarding the way strpos works, and consequently all similar “search (and replace)” functions like str_replace, strrpos, stripos, str_ireplace, substr_replace, even preg_match and preg_replace (I tested only str_replace and preg_match out of these, but I assume they will all bear the same results).

  1. From here on  am using the php.net convention, and will call “needle” the string you’re searching for, and “haystack” the string inside of which you’re executing the search.
  2. Knowing these results will only be useful if you can choose which “needles” to put in the “haystack” to be searched for in a later time, hence only if you’re building a template.
  3. I serched if someone else found this already, but this doesn’t appear to be the case, so if I am selling for new already known things just don’t bash me.

So let’s say you’re creating a template scheme, where you insert several tags that need to be replaced by the dynamically generated content of your website. You can call them whatever you want as long as they are unique strings inside the template, so for example %tag% or {tag} or <!–tag–> or ~tag~ (or just whatever). Maybe you think that choosing which delimiting chars to use for the tag name is only up to your personal tastes, and I did too before discovering this by accident, but I am going to guess that if the template contains well formed HTML code, then using ~tag~ is going to be much faster than using <!–tag–>.

The general principle is, searching for a needle beginning with a “rare” character is much faster than searching for a needle starting with a commonly used character inside the haystack.

For example, if your haystack is an excerpt from an ebook, searching for “%hello” (if present) will be way faster than searching for “hello”. The reason for this? The function in C that searches for the string, starts by searching for its first character, if found checks if the following one matches, and so on; so if you’re searching for “hello” the function will pause at every “h” to see if after that there’s an “e”, and if yes then checks if there’s and “l” and then another “l”, yet if the word is “hellish”, the function will not find the ending “o”, and will have to discard the work and time spent and go on with the search. The “%” character on the other hand is pretty rare inside of a “normal text”, if not unique, so the function will have to “pause” way less times before hitting a full match.

Let’s put it to the test, this is the routine:

$creationstart=strtok(microtime()," ")+strtok(" ");
for ($i=0;$i<100000;$i++) $testpos=strpos($test,"malesuarda");
$creationend=strtok(microtime()," ")+strtok(" ");
$creationtime=number_format($creationend-$creationstart,4);
echo "malesuarda $testpos: ".$creationtime."<br />";

$creationstart=strtok(microtime()," ")+strtok(" ");
for ($i=0;$i<100000;$i++) $testpos=strpos($test,"%malesuada");
$creationend=strtok(microtime()," ")+strtok(" ");
$creationtime=number_format($creationend-$creationstart,4);
echo "%malesuada $testpos: ".$creationtime."<br />";

Let’s do some explaining: $test is a fairly long string that I previously defined inside the code (it is made of a lorem ipsum kind of text, several paragraphs amounting to almost 13kb), inside of which I took a random word, “malesuada“, which is repeated several times, and I made two occurrences of this word slightly different, to render them unique; they were both towards the end of the string, I changed one into malesuarda adding a”r”, and another one (further away in the string) into %malesuada, then just loaded the PHP script; I echoed the value of $testpos as well, to confirm that the strings were actually found.

As expected, here are the results:

malesuarda 10970: 3.5609
%malesuada 11514: 0.7632

Replacing strpos with any other functions listed at the beginning of this article will deal similar results.