Part 2 of 5
Three Hundred Files
The Search Engine Is a Table of Words
The community site in this series has its own search engine. Not a LIKE '%term%' query, and not MySQL full-text indexing, which existed and would have been the sensible choice. An inverted index, written as content is posted, stored in two tables.
It is about two hundred lines of PHP, and of everything in this codebase it is the part I would still defend.
Two Tables
The first table is the vocabulary. searchKeywords maps a word to a wordId, and the function that reads it is the whole of the interning strategy:
function wordId($word){
$word = mysql_real_escape_string($word);
$sql = "SELECT wordId FROM searchKeywords WHERE word = '$word' LIMIT 1";
$res = $GLOBALS['DB']->query($sql);
if(count($res) > 0){
$wordId = $res[0]['wordId'];
}
else{
$sql = "INSERT INTO searchKeywords SET word = '$word'";
if($GLOBALS['DB']->query($sql)){
$wordId = mysql_insert_id();
}
}
return $wordId;
}Look it up, insert it if it isn't there, return the id either way. Every distinct word on the site gets exactly one row, forever.
The escaping call on the first line stands out, because the previous post argued that escaping in this codebase is applied inconsistently. Here it is applied, and it has to be: this function is the one place where arbitrary text from a forum post reaches a query as a value rather than an id.
The second table is the postings list. searchIndex holds contentType, parentId, wordId, and count. One row per word per document, carrying how many times that word appears in that document. That is term frequency, stored, which is the thing that lets a result be ranked rather than merely matched.
Storing ids rather than strings in the postings table is the reason this works at all. A vocabulary grows logarithmically and a postings table grows with content, so the two diverge quickly, and an integer join against an integer column is a different cost from comparing text. The surviving searchIndex table is 12 MB across four integer columns.
The Document Is the Thread
The index structure is textbook. What the design gets right is what it treats as a document.
Indexing runs per content type, and there are five: forum, artwork, challenges, microblogs, tutorials. For a forum topic, the indexer takes the subject and the body, and then does this:
function indexCommentWords($parentId,$commentType,$words){
$sql = "SELECT commentId,text FROM comments WHERE parentId = '$parentId' AND commentType = '$commentType'";
$comments = $GLOBALS['DB']->query($sql);
if(count($comments) > 0){
foreach($comments as $comment){
$text = $comment['text'];
$textwords = str_word_count(strtolower($text),1,'0123456789');
if(count($textwords) > 0){
foreach($textwords as $textword){
$wordId = wordId($textword);
$words["$wordId"]++;
}
}
$words = indexCommentWords($comment['commentId'],99,$words);
}
}
return $words;
}It walks the replies, adds their words to the same bag, then recurses into replies of replies at any depth. The $words array is threaded through the recursion and comes back holding the whole conversation.
So a thread and its entire reply tree are one document with one set of term counts. Searching for a term that appears once in the original post and eleven times across the answers ranks that thread higher than one where it appears twice and is never picked up.
That is the right model for a forum and it is not the obvious one. Indexing each post separately is easier to write and gives worse results, because it returns the reply that happens to contain the word rather than the discussion the word belongs to. A question is only useful with its answers attached, and this index treats them as the same object.
It has a real cost. A thread cannot be indexed incrementally. One new reply means the whole tree is walked and every posting row for that thread is deleted and rewritten:
$sql = "DELETE FROM searchIndex WHERE contentType = '$contentType' AND parentId = '$parentId'";Delete then reinsert, per document, per run. For a thread with four hundred replies that is four hundred rows of text re-tokenized to add one post. The design chose result quality over update cost, which for a site where reading vastly outnumbers posting is the correct way round, but it is a choice and the code does not say so anywhere.
Indexing Happens on the Way In
The index is not built by a scan. It is written at the moment content is created, from four places: a new topic, a new image, a challenge entry, and a reply.
//index for search
searchIndex(1,$topComment->getParentId());That line is in comment-reply.php, and the argument is what makes it expensive. A reply does not index itself. It reindexes the thread it belongs to, by parent id, because the thread is the document. So posting a two-word reply to a four-hundred-post thread deletes four hundred posts' worth of postings rows and rebuilds them from re-tokenized text, synchronously, before the reply appears.
That is the price of the thread-as-document decision, and it is paid on the write path where a person is waiting. The read side gets a genuinely good index. The write side gets slower the more successful a thread becomes, which is exactly backwards from what a busy forum wants.
There is a fifth caller, and it is not a scheduled job despite the filename:
$contentType = $_GET['contentType'];
$parentId = $_GET['parentId'];
for($i=0;$i<75;$i++){
searchIndex($contentType,$parentId);
$parentId++;
}This is the manual backfill. Point a browser at it with a content type and a starting id, and it walks seventy-five documents from there. That is what the $_GET is for, and it is why there is no queue or dirty flag anywhere: nothing needs one, because the index is already current. This exists for the cases where it isn't, after a bulk import, a schema change, or a bug that left a range unindexed.
Seventy-five is a timeout number. Shared hosting killed long-running requests, and seventy-five documents was what fit in one. It is the sort of constant that records an operational limit without recording which limit, and the only way to rebuild a large range was to keep advancing the start id by hand.
What I'd Change
Index incrementally. Keep the thread as the document, because that part is right, but store per-post term counts and sum them at query time, or keep a running total and adjust it by the delta of the post that changed. Rebuilding the whole thread for one reply is the only genuinely wasteful thing in here, and it gets worse on precisely the threads that matter most.
Move it off the request. Write the thread id to a queue and let a worker drain it. Search results a few seconds stale are fine, and nobody posting a reply should be waiting on a re-tokenize of the entire conversation. This is the change that costs the least and buys the most, because the indexing code itself does not have to change at all.
Stop words and stemming, in that order. Every occurrence of "the" in every thread on the site has a row in the postings table. Dropping a few dozen words would remove a large fraction of it. Stemming matters less than it sounds for this content, because artists searching for a tool name want that tool name.
What Transfers
Decide what a document is before deciding how to index it. The structure here is textbook and the value is in the modelling. A thread is one thing to a reader, so it should be one thing to a search engine, and no amount of tuning on a per-post index recovers what that buys.
Interning strings buys more than it costs. A word table and integer postings is the difference between an index that fits in memory and one that does not, and the lookup-or-insert function that makes it work is sixteen lines.
A batch size is a fact about the environment. The 75 in the backfill loop is the only surviving record of what the host would tolerate. Write the reason next to the number, because the number outlives the host.
Next in the series: the live chat, which runs on a non-blocking socket server written in PHP, kept alive by cron, on a harness originally written for a softphone.