Now, I’ve implemented a third option: progressive intersection.<\/p>\n\n\n\n
- \n
- Progressive Intersection<\/strong>. We’re going to implement the intersection as a progressive multi-way merge pulling in new document ids in chunks from the posting lists only as needed. If we reach the the retrieval quota, we stop without ever reading into memory the complete posting lists.<\/li>\n<\/ul>\n\n\n\n
Here’s the algorithm. We imagine having the posting list for each term in sorted ascending order (by local doc id) and we want to find documents that are common to all the posting lists.<\/p>\n\n\n\n
![\"\"](\"https:\/\/byte64.com\/wp-content\/uploads\/2026\/04\/Untitled-drawing-4.png\")
<\/figure>\n\n\n\nWe’re looking for the elements that are in common to all three. So, let’s make a max heap of the first elements. The largest element we find is 3. So we can discard anything lower than 3 from our posting lists:<\/p>\n\n\n\n
![\"\"](\"https:\/\/byte64.com\/wp-content\/uploads\/2026\/04\/Posting-list-progressive-retrieval.png\")
<\/figure>\n\n\n\nSince the first elements are not all 3, and 3 is the minimum of the first elements, we know we don’t have 3 in our intersection. Now we’ll simply repeat this process. The max of the first elements is now 5. Removing everything lower gives:<\/p>\n\n\n\n
![\"\"](\"https:\/\/byte64.com\/wp-content\/uploads\/2026\/04\/Posting-list-progressive-retrieval-1.png\")
<\/figure>\n\n\n\nNow since all first elements are the same, we’ve found that 5 is in the intersection. We continue this process:<\/p>\n\n\n\n
![\"\"](\"https:\/\/byte64.com\/wp-content\/uploads\/2026\/04\/Posting-list-progressive-retrieval-2-1.png\")
<\/figure>\n\n\n\nRemoving 5, our max is now 14, so we can remove anything lower:<\/p>\n\n\n\n
![\"\"](\"https:\/\/byte64.com\/wp-content\/uploads\/2026\/04\/Posting-list-progressive-retrieval-3.png\")
<\/figure>\n\n\n\nNow our max is 17 and we can remove anything lower:<\/p>\n\n\n\n
![\"\"](\"https:\/\/byte64.com\/wp-content\/uploads\/2026\/04\/Posting-list-progressive-retrieval-4.png\")
<\/figure>\n\n\n\nNow our max is 20 and we can remove anything lower:<\/p>\n\n\n\n
![\"\"](\"https:\/\/byte64.com\/wp-content\/uploads\/2026\/04\/Posting-list-progressive-retrieval-5.png\")
<\/figure>\n\n\n\nAnd that finds 20 is in the intersection. And, now I just noticed that poodle 30 should have been red and not poodle 35. Anyway, you get the point.<\/p>\n\n\n\n
The advantage of this progressive approach is two-fold:<\/p>\n\n\n\n
- \n
- We get to stop as soon as we fill our retrieval quota. For example, I’m using a retrieval quota of 10k documents. So, if there are more than 10k documents in the intersection, we’ll only take the first 10k with respect to the document order (pagerank).<\/li>\n\n\n\n
- We don’t need to read the entire PFOR from disk in order to compute the intersection. Since the PFOR is already in chunks of 128 document ids, I’ve setup buffers of 128 document ids for each term. We’ll read another 128 documents in for each term when the buffer runs out. This applies to both PFOR encoded and repeated varint encoded document ids.<\/li>\n<\/ul>\n\n\n\n
Likely there’s further optimizations that can be done here. I expect 128 documents to only take around 256 bytes and typically the operating system is reading from disk in 4KiB pages. So, perhaps I should figure out where the page boundaries are and use that to determine how much to buffer.<\/p>\n\n\n\n
Ignoring the page boundaries for now, I can count up the bytes I’m using and see what should lead to a difference in performance.<\/p>\n\n\n\n
Here’s the fancy new settings to choose the retrieval algorithm:<\/p>\n\n\n\n
![\"\"](\"https:\/\/byte64.com\/wp-content\/uploads\/2026\/04\/image-13-1024x515.png\")
<\/figure>\n\n\n\nAnd here’s the comparison:<\/p>\n\n\n\n
![\"\"](\"https:\/\/byte64.com\/wp-content\/uploads\/2026\/04\/comparison-1024x608.png\")
<\/figure>\n\n\n\nThe approximate total results clearly needs some work on the progressive algorithm. It thinks that if it continued it would find over a million results. But in terms of bytes read, we can see that we’ve done much better than the previous two algorithms. Again, this doesn’t take into account that we read pages. But some of the other statistics, like intersection retrieval time look improved. I’m looking into what keyword retrieval time means for the progressive algorithm. In the previous two, it was the time taken to read the PFOR. There seems to be a large swing in embedded retrieval time which could certainly account for the overall server time improvements. I don’t think these results should be entirely trusted until I can do some robust experimentation.<\/p>\n","protected":false},"excerpt":{"rendered":"
I’ve been making incremental progress on the retrieval algorithm and now have what I think of as a full complement of algorithms and settings. In terms of search index encoding, I started with the PFOR encoding of docids and then added repeated varint encodings of the docids to save space. (The PFOR blocks contain 128 […]<\/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":[19,33,32],"class_list":["post-141","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-search","tag-doc-ids","tag-pfor","tag-retrieval"],"_links":{"self":[{"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/posts\/141","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=141"}],"version-history":[{"count":3,"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/posts\/141\/revisions"}],"predecessor-version":[{"id":156,"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/posts\/141\/revisions\/156"}],"wp:attachment":[{"href":"https:\/\/byte64.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=141"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/byte64.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=141"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/byte64.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=141"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}