1

As long as I remember at least in older versions of Cassandra database, search was implemented in following way -

During startup several samples are collected from sorted table and when data is needed the samples are considered. Then the data is search sequentially relative to the location of the sample.

Note I am ignoring the bloom filter there.

Question is - Isn't it better / faster to binary search to be used instead?

The most common "hot spots" such middle element will be cached from the OS and looking them up will be for free.

What are the benefits of "search with samples"?

5
  • 1
    Unless the amount of data being searched is enormous, this simple "index card" approach might already suffice. It has less overhead, and I've seen it work quite satisfactorily, even for large data sets. Jun 22, 2017 at 15:29
  • so basically they tried to avoid non sequential i/o ?
    – Nick
    Jun 22, 2017 at 15:42
  • Of course. As is the goal of all indexing schemes, including binary search. Jun 22, 2017 at 15:48
  • binary search have lots of non sequential i/o.
    – Nick
    Jun 22, 2017 at 16:31
  • 1
    Oh, I thought you meant sequential I/O. The whole point of binary search is to do non-sequential I/O efficiently. Jun 22, 2017 at 20:42

1 Answer 1

1

The most common "hot spots" such middle element will be cached from the OS and looking them up will be for free.

The issue here is that not only those "hot spots" will be cached, but also those elements directly before and after, which are rather unlikely to be hot spots. Thus you're wasting (limited!) cache space.

Caches are mostly block oriented, that is you cannot just load a small part into them, but whole blocks at once.

Consider this example:

x x x x x x x x x x x x x x x x

That's your large sorted array, each x an element of it. Your cache has two "blocks", each of size 2 elements. You can only load/unload a whole block, and only from even addresses (element 0 and 1 can be loaded as one block, 1 and 2 not). Cached elements are marked as c in the following, least recently used is used as block replacement strategy. ^ marks the element we're currently looking at.

Now let's do a binary search for the first element:

  1. Take (upper) mid element:

    x x x x x x x x c c x x x x x x
                    ^
    
  2. Greater, recurse left:

    x x x x c c x x c c x x x x x x
            ^
    
  3. Greater, recurse left:

    x x c c c c x x x x x x x x x x
        ^
    
  4. Greater, recurse left:

    c c c c x x x x x x x x x x x x
      ^
    
  5. Greater, recurse left, single matching element found (no changes to cache).

We loaded a total of 8 elements (4 blocks) into the cache. 3 of them were not even looked at, but were loaded because they happened to be next to an element we looked at.

Now assume we had beforehand sampled the mid element and the mid elements of the left and right half:

x x x x x x x x x x x x x x x x
        \       |       /       

              \ | /
              s s s

We ignore the cache activity of this operation because it's only done once. Thus its costs will be amortized over many searches.

Now we again do a binary search for the first element, but this time start one on those samples:

  1. We look at the mid element, which loads the first in the cache, too, and recurse left.

    c c s
    
  2. We look at the first element, which is greater than the searched one, and thus we know that we need to search in the marked region of the whole array:

     x x x x x x x x x x x x x x x x
    |       |
    
  3. We do a binary search in the marked region, starting with its mid element, and recurse left:

     x x c c x x x x x x x x x x x x
    |    ^  |
    
  4. We look at the marked element, and need once more recurse left to find the element, though this won't lead to new cache loads:

     c c c c x x x x x x x x x x x x
    |  ^    |
    

We loaded a total of 6 elements (3 blocks), of which only a single one wasn't looked at.

4
  • i am confused, how this answer the question? it only explains how the cache works?
    – Nick
    Jun 22, 2017 at 18:11
  • 1
    By using a sample you reduce cache misses because you no longer load (extremely) irrelevant elements into your cache. Will revise answer later, this and answer is written on a mobile... Jun 22, 2017 at 18:14
  • but by using samples, you hit different spots all the time. so you do not benefit from the cache thatmuch.
    – Nick
    Jun 22, 2017 at 18:20
  • 1
    The samples are copied such that they form a sequential array, so that the cache will get filled with sampled elements only (at least until the region possibly containing the searched for element is determined). Jun 22, 2017 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.