Re: cdb Fast Lookup

On Fri, 23 Aug 2002, Gustavo Vieira Gonçalves Coelho Rios wrote:

> 	Fast Lookup: A successful lookup in a large database normally takes
> just two disk accesses. An unsuccessful lookup takes only one.

No. He says <URL:http://cr.yp.to/cdb.html>:

Fast lookups: A successful lookup in a large database normally takes
just two disk accesses. An unsuccessful lookup takes only one.

Note the word "normally" in the statement. There is no guarantee for a
worst case. I would take his words to mean an "average case" but he
provides no proof (formal or otherwise) for the algorithm's expected
value.

If you read the cdb specification
<URL:http://cr.yp.to/cdb/cdb.txt>, you'll see that he uses a fixed hash
function. Clearly a worst case scenario is that all of your keys map to
a single hash value. You would:
  - look up (hash mod 256) in the table of tables; this can be read once
    per opening of the cdb, so no disk access
  - get a starting point in the table from (hash / 256 mod length(table));
    no disk access here
  - probe linearly in the table, starting at the previously computed
    point; this clearly involves a disk access
  - once you've found the pointer in the table, get the data; this
    clearly involves a disk access

Now the tricky part is exactly what constitutes a "disk access" in this
case. Because Dan is mmap()ing the file, my assumption is that reading a
particular page of data will constitute a disk access (that is, you will
fault a single page and the OS will read it from disk as a single
chunk). Let's assume a page size of 4096 bytes, since that seems to
prevail on 32-bit machines.

Each slot in the hash table specifies a hash and a byte position; each
are 4 bytes, for a total of 8 bytes. That gives us 512 records per page.
So if you have 1024 records with identical hashes, then you will
probably need two disk accesses.

However, the issue is still more complex than that. Imagine that you
start probing right at the end of a page boundary. In that case you end
up doing two disk accesses even if there are only two colliding values.
Furthermore, the OS may well be doing some sort of read-ahead caching.
It may actually request several sequential pages at once, dropping the
number of disk accesses. And of course, the page you're requesting may
already be in the cache.

Let me know if you think any of my analysis is wrong.

-Peff