I’ve still been hard at work trying to bring the Byte64 search engine to its first release. I’ve been focused on online indexing which has a host of complexities. I don’t think it’s lent itself to blog posts because it’s a complicated system and there doesn’t appear to be one clear right way to do it. Once it settles down, I’ll come back an describe it all. <\/p>\n\n\n\n
For now, as I make the system more generic, I’m pulling out anything specific to wikipedia and making the system configurable. So, I want to talk a bit about documents, sections, posting lists and queries. My ultimate goal is to talk about how queries are planned and executed in a mixed environment of semantic and keyword sections.<\/p>\n\n\n\n
Let’s start with the structure of a document. We separate various types of information about a document into sections — like title, body, etc. These sections may have different parsing types. Typically we break the section text into words, but we can also break it into lines (e.g. for categories which are phrases like “19th Century Scientists”) or we can extract prefixes for a suggestion lookup. Once each section is parsed into a list of strings, those strings typically form the keys of a search index to look up documents. Sections can also be embedded and put into a vector retrieval database, typically by some kind of chunking. For the wikipedia body section, we want both keyword and vector lookups.<\/p>\n\n\n\n
For each corpus we set the default sections that we want to search over and we can assign them weights. For wikipedia, I’m searching over the title and body sections giving title weight 2. There is another section in our wikipedia corpus, called category, but it’s not search by default.<\/p>\n\n\n\n
Let’s consider the query: “quantum physics category:science”. Here perhaps we’re filtering out any fiction by only looking for documents in the science category, or rather, that have science in their category section.<\/p>\n\n\n\n
How do we plan this query? By default, we connect words with an AND to cause an intersection. We also apply default sections to each term without an explicit section prefix. So we get:<\/p>\n\n\n\n
(title:quantum OR body:quantum) AND (title:physics OR body:physics) AND category:science<\/p>\n\n\n\n
Since we’ve made a vector embedding of the body section, we also need to be able to embed phrases and find their nearest neighbours. I’ve chosen to treat any implicit ANDs also as phrases for the semantic search. So, our query becomes:<\/p>\n\n\n\n
((title:quantum OR body:quantum) AND (title:physics OR body:physics) OR body_semantic:”quantum physics”) AND category:science<\/p>\n\n\n\n
This structure unions the quantum physics keyword and semantic results together befor intersecting it with science from the category section. This looks like it might be a sufficient query execution plan, but semantic retrieval is very different from keyword retrieval. <\/p>\n\n\n\n
If every term in the query is uniformly coming from keyword retrieval, we can turn each term into an iterator and produce the results in a streaming fashion. We expect each iterator can contain many element and we can terminate early when we find enough results. This limits how much we read the disk.<\/p>\n\n\n\n
Our nearest neighbors retrieval, on the otherhand, is a black box returning a small number of semanticly relevant results. It doesn’t return them in the document order (lexicographic, pagerank, etc). It returns them in order of semantic similarity. As a result, you’d have to execute the query above in three stages: <\/p>\n\n\n\n
If you parallelize 1 and 2, then you’ve got to hold the results of 1 in memory. Otherwise, you have to wait for 2 to complete before processing all three, delaying when you start accessing disk for 1. That’s not a great plan.<\/p>\n\n\n\n
Alternatively, you can denormalize the query with the knowledge that semantic search is different. If we separate the purely keyword part from the semantic part (as much as possible) we get the union of:<\/p>\n\n\n\n
It remains to be tested, but I think this is a better query plan. We have one purely keyword part which requires a lot of disk access, and we have a semantic\/keyword intersection in part 2. Part 2 needs to wait for the nearest neighbors before starting, but once those are available, we keep those few results in memory and run down the category:science posting list looking for matches.<\/p>\n\n\n\n
How do we minimize disk access? In the denormalized query, we’re accessing the posting list for category:science twice. I’m testing out a mechanism where we read the posting list once from disk, provide two (or multiple) iterators, and only store in memory the information between the fastest and slower iterator. The iterator for the keyword part gets a head start, so it’ll be pulling the posting list into memory from disk a chunk at a time. We’ll keep it around until nearest neighbours gives its result and we start going down the posting list with the second iterator. Who knows? That second iterator may even catch up since it has less work to do.<\/p>\n","protected":false},"excerpt":{"rendered":"
I’ve still been hard at work trying to bring the Byte64 search engine to its first release. I’ve been focused on online indexing which has a host of complexities. I don’t think it’s lent itself to blog posts because it’s a complicated system and there doesn’t appear to be one clear right way to do […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[30,18],"tags":[40,38,32,39],"class_list":["post-191","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-search","tag-posting-lists","tag-query-planning","tag-retrieval","tag-sections"],"_links":{"self":[{"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/posts\/191","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/byte64.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=191"}],"version-history":[{"count":1,"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/posts\/191\/revisions"}],"predecessor-version":[{"id":192,"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/posts\/191\/revisions\/192"}],"wp:attachment":[{"href":"https:\/\/byte64.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=191"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/byte64.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=191"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/byte64.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=191"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}