Faster List Intersection Using Skip Pointers

As I mentioned in my previous post about array intersection, all the work we did was to enable us to experiment with skip pointers. You may remember me saying that list intersection was the most important operation when it comes to search engines. This is because in web search, most queries are implicitly intersections. Consider, when your query contains multiple words (e.g. "car repairs", "britney spears songs" etc.) the search engine will translate this into – ("car AND repairs", "britney AND spears AND songs"), which means it will be intersecting 2 or more postings lists in order to return a result. Because intersection is so crucial, search engines try to speed it up in any way possible. One such way is to use skip pointers.

What Are Skip Pointers

As you recall from my previous post if the sizes of our two posting lists are x and y, the intersection takes x+y operations. Skip pointers allow us to potentially complete the intersection in less than x+y operations. Here is how. At indexing time, we augment our posting lists of document identifiers with a set of "short cut" pointers that reference values further along in the list e.g.:

This way, if the situation allows, we can avoid processing parts of the list by following this pointer whenever this will have no impact on our intersection operation.

Here is an example, let us say we want to merge two posting lists for the words "car" and "repairs" which have been augmented with skip pointers like so:

We would start using our normal intersection algorithm. We continue advancing through both lists until we have matched 12 and advanced to the next item in each list. At this point the "car" list is sitting on 48 and the "repairs" list is on 13, but 13 has a skip pointer. We check the value our skip pointer is pointing at (i.e. 29) and if this value is less than the current value of the "car" list (which it is), we follow our skip pointer and jump to this value in the list. This allows us to skip 3 items in the "repairs" list since we know they weren't going to match anyway. Using this technique we can complete an intersection operation faster than we would have been able to otherwise.

We can immediately see a problem. If we augment our data with skip pointers there is now extra overhead for storing these as well as checking for their existence, as well as the overhead involved in actual skip pointer comparisons. This can negate any advantage we gain for our intersections. In practice you don't want to have too many skips for this very reason, but you also don't want to have too few as this defeats the purpose of having skips in the first place.

One simple heuristic which has been shown to work well, is to have sqrt(n) evenly spaced skip pointers for a posting list of size n (this is decent but not the best as it doesn't take into account the distribution of your query terms). What we are going to try and do is test empirically whether or not skip pointers will allow us to improve the speed of an intersection operation.

The Test Data

The first thing to do is to generate some dummy posting lists. We use the following function:

def create_wrapped_mock_postings_list(min_postings, max_postings, corpus_size)
  postings_list = []
  num_postings = min_postings + rand(max_postings)
  num_postings.times do
    wrapped_id = OpenStruct.new
    wrapped_id.value = rand(corpus_size) + 1
    postings_list << wrapped_id
  end
  postings_list.sort{|x,y| x.value <=> y.value}.block_uniq{|item| item.value}
end

This generates a list of between min_postings and max_postings document ids each of which is a number between 1 and corpus_size. We also need to wrap each of our raw numbers in a container since we know we will be augmenting them with skip pointers.

Putting in the skips turned out to be reasonably complex, making sure they were evenly spaced according to our heuristic (sqrt(n)) as well as making sure everything was correctly handled when we got to the end of the list. The augment_wrapped_list_with_skips does a reasonable job, using two other helper functions. There is nothing really revolutionary about these, they were just extremely fiddly to write.

def calculate_skip_index_for(skip_number, values_to_skip)
  skip_index = skip_number * values_to_skip
  skip_index = skip_index - 1 if skip_index > 0
  skip_index
end
 
def build_skip_index_hash_for(list)
  skip_indexes = {}
  number_of_skips = Math.sqrt(list.size).to_i
  number_to_skip = (list.size/number_of_skips).to_i
  (0..number_of_skips - 1).each do |skip_number|
    skip_index = calculate_skip_index_for(skip_number, number_to_skip)
    skip_indexes[skip_index] = calculate_skip_index_for(skip_number + 1, number_to_skip)
  end
  skip_indexes
end
 
def augment_wrapped_list_with_skips(list)
  skip_indexes = build_skip_index_hash_for list
  list.each_with_index do |list_item, list_index|
    if skip_indexes.key? list_index
      list_item.skip_index = skip_indexes[list_index]
      list_item.skip_value = list[skip_indexes[list_index]].value
    end
  end
end

The New Intersection Function

Now that we're able to augment our lists with skips, all we need as an intersection function that will take advantage of this:

def rubyish_intersect_for_wrapped_with_skips(list1, list2)
  list3 = []
  skips = 0
  list1.each_with_skips do |item1, index1|
    next_index1 = nil
    list2.each_continued do |item2, index2|
      if item1.value == item2.value
        list3 << item2
        index2 + 1
      elsif item1.value < item2.value
        while !item1.skip_index.nil? && item1.skip_value <= item2.value
          next_index1 = item1.skip_index
          item1 = list1[next_index1]
          skips += 1
        end
        index2
      else
        next_index2 = nil
        while !item2.skip_index.nil? && item2.skip_value <= item1.value
          next_index2 = item2.skip_index
          item2 = list2[next_index2]
          next_index1 = index1
          skips += 1
        end
        next_index2
      end
    end
    next_index1
  end
  list3
end

As you can see it is quite a bit more complex than the previous intersection functions we have written. This does nothing more than what I described above:

• looks for a skip pointer
• if found, checks the value it is pointing at
• figures out if we're able to follow the skip by comparing the current value of the other list with the value the skip is pointing at
• follows the skip pointer if possible

It could certainly use a helper function or two, but I believe keeping it all in one place makes the algorithm a bit clearer. One thing to note is the fact that the outer each iterator is no longer just a standard one, we've had to open up our Array class and add the following:

class Array
  def each_with_skips
    current_index = 0
    while current_index < self.size
      next_index = yield(self[current_index], current_index)
      if next_index
        current_index = next_index
      else
        current_index += 1
      end
    end
  end
end

This essentially allows us to return a value from the block, which will be used as the index to continue the iteration from on the next pass, allowing us to "skip" a number of values when we're able to follow the skip pointers of the outer iterator. The inner iterator still uses the "each_continued" function that we wrote in the last post as it already had the ability to skip values when necessary. If you can re-write this intersection function to be tighter and more "ruby-ish", do share it, I'd be intersected to see what other people can come up with.

The Experiment

We're now ready to run our experiment to see if skip pointers can actually make a difference. All we need is a method to time the execution of our intersection functions. Fortunately I have written about timing Ruby code before (how lucky is that :)), so we'll just take the timing method from there:

def time_method(method=nil, *args)
  beginning_time = Time.now
  if block_given?
    yield
  else
    self.send(method, args)
  end
  end_time = Time.now
  puts "Time elapsed #{(end_time - beginning_time)*1000} milliseconds"
end

We want to compare three things:

• intersecting two lists of raw integers (not augmented by skip pointers and not wrapped by another object)
• intersecting two lists of "wrapped" integers (wrapped by another object to possibly contain more data) without using skip pointers
• intersecting two lists of "wrapped" integers (wrapped by another object to possibly contain more data, such as the skips) using skip pointers

Here is the code:

def create_raw_mock_postings_list(min_postings, max_postings, corpus_size)
  postings_list = []
  num_postings = min_postings + rand(max_postings)
  num_postings.times do
    postings_list << rand(corpus_size) + 1
  end
  postings_list.sort.uniq
end
 
def wrap_raw_list(list)
  wrapped_list = []
  list.each do |item|
    wrapped_item = OpenStruct.new
    wrapped_item.value = item
    wrapped_list << wrapped_item
  end
  wrapped_list.sort{|x,y| x.value <=> y.value}.block_uniq{|item| item.value}
end
 
CORPUS_SIZE = 100000000
 
raw_list1 = create_raw_mock_postings_list(100, 200, CORPUS_SIZE)
raw_list2 = create_raw_mock_postings_list(30000, 50000, CORPUS_SIZE)
 
wrapped_list1 = wrap_raw_list(raw_list1)
wrapped_list2 = wrap_raw_list(raw_list2)
 
wrapped_list1_with_skips = augment_wrapped_list_with_skips(wrapped_list1)
wrapped_list2_with_skips = augment_wrapped_list_with_skips(wrapped_list2)
 
puts ""
puts "RAW"
puts "---------------------------------------------------------"
time_method(:rubyish_intersect_for_raw, raw_list1, raw_list2)
puts ""
puts "WRAPPED"
puts "---------------------------------------------------------"
time_method(:rubyish_intersect_for_wrapped, wrapped_list1, wrapped_list2)
puts ""
puts "WRAPPED WITH SKIPS"
puts "---------------------------------------------------------"
wrapped_list1_with_skips.reset_current_index
wrapped_list2_with_skips.reset_current_index
time_method(:rubyish_intersect_for_wrapped_with_skips, wrapped_list1_with_skips, wrapped_list2_with_skips)

Running this, we get results similar to the following:

RAW
---------------------------------------------------------
Time elapsed 59.634 milliseconds

WRAPPED
---------------------------------------------------------
Time elapsed 265.142 milliseconds

WRAPPED WITH SKIPS
---------------------------------------------------------
Time elapsed 245.459 milliseconds

I won't bore you by running this dozens of times here, suffice to say I did run this lots and lots of times while tweaking the parameters :) (i.e. the sizes of the lists, the corpus size). Here is what I found.

No matter what you do, intersecting a "raw" (not wrapped in a decorator and no skip pointers) list is always significantly faster. This is to be expected, but ultimately means nothing since it is not possible to augment these raw values with skip pointers anyway. Regardless in a real search engine index, document ids in posting lists will often need to contain extra data in addition to skip pointers (e.g. positional information etc.) and so will almost never be raw numbers. What we're really interested in is comparing "wrapped" lists with and without skips. As you can see from the output above, skip pointers made the list intersection slightly faster, but this is not always the case. Here are some interesting facts that I have found:

• when both lists are sufficiently small, we never skip but the time difference is negligible due to the size of the lists
• for larger lists of similar size (i.e. both lists around 30000 values) skip pointers are followed rarely and are therefore actually detrimental to the performance of the intersection function (due to the overhead of checking the skip values but being unable to follow), with the times being 10% to 40% slower for lists with skips
• when posting list sizes are orders of magnitude different (i.e. list of size 200 vs list of size 20000 like the code above), skip pointers begin to come into their own since the larger list is able to skip a lot more often, the improvement is around 10% to 40% (10 is more likely than 40)

As you can see, skip pointers certainly can improve the speed of an intersection function, but only in certain situations. Of course there are a couple of things to be aware of. Firstly, random generation of posting lists data may not be representative of the distribution of the document ids, in a posting list, in a real search engine index. When randomly generated, document ids end up evenly distributed across the size of the corpus, in real life, this is likely not to be the case, which may allow us to skip a lot more often, improving performance. Secondly, we augmented our data with skip pointers in a somewhat naive fashion (sqrt(n)). If we can come up with another heuristic that will fit our data better (through data analysis), we may be able to improve performance even more. Well, there we go, some interesting code, a new concept and a modified intersection algorithm, don't forget to subscribe to my feed if you enjoyed it. As always, if you have something to add or have a question, I'd love to hear from you. 

Tagged as: list intersection, ruby, skip pointers