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"?

  • 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. – Robert Harvey Jun 22 '17 at 15:29
  • so basically they tried to avoid non sequential i/o ? – Nick Jun 22 '17 at 15:42
  • Of course. As is the goal of all indexing schemes, including binary search. – Robert Harvey Jun 22 '17 at 15:48
  • binary search have lots of non sequential i/o. – Nick Jun 22 '17 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. – Robert Harvey Jun 22 '17 at 20:42

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.

  • i am confused, how this answer the question? it only explains how the cache works? – Nick Jun 22 '17 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... – Daniel Jour Jun 22 '17 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 '17 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). – Daniel Jour Jun 22 '17 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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