6.830 Lab 1 notes
Dan Ports <drkp@mit.edu>

There isn't much exciting to say about this code, since most of it is
just straightforward implementation of the interfaces. I had hopes of
finding time to do something more interesting, but the impending NSDI
deadline shattered those dreams.

The eviction policy used by the buffer pool is a clock-based
psuedo-LRU algorithm. Specifically, each page in the buffer pool has a
recently-referenced bit, which is set whenever the page is accessed
(via BufferPool.getPage()). The buffer pool has a "clock hand" pointer
pointing to one of the pages in the pool. When it comes time to evict
a page, the hand sweeps around the list of page slots (wrapping around
when it reaches the end). If the recently-referenced bit is set for a
page, it is cleared; if it encounters a page whose recently-referenced
bit is not set, that page is evicted. This algorithm is a reasonable
approximation to the LRU algorithm that doesn't require actually
maintaining the (potentially expensive) list of pages ordered by
their access time.

The join algorithm is a simple nested-loops join.

I did not change many of the interfaces, mostly for fear of breaking
compatibility with the unit tests or any code that might be provided
in future labs. I did add a static Tuple.combine method that combines
two tuples as would be done in a join (much like TupleDesc.combine).

However, if I weren't worried about breaking compatibility (and had
more Copious Free Time), I might have changed a few things in the
interfaces:

  - Executing a query requires creating a SeqScan, which takes a
    tableid, and looks it up in the Catalog to find a DbFile to
    iterate over. That DbFile needs to call the BufferPool to load
    pages, and this requires the BufferPool to call back to the
    Catalog to find the necessary DbFile. This seems a little
    byzantine. I would have liked to make a PageId include a pointer
    to its DbFile object to eliminate the repeated catalog
    lookups.

  - Similarly, flushing a page requires the BufferPool to find the
    DbFile associated with a page by looking up the PageId's tableid
    in the Catalog. This also seems unnecessarily complex. It would be
    more elegant if a Page had a pointer to the associated DbFile, and
    provided a flush method to do this. This would also eliminate the
    need for the BufferPool to keep the PageId separately.

  - There are a number of different types of iterators, all of which
    are only slightly different: the DbIterator, the DbFileIterator,
    and the regular Java Iterator returned by Page.iterator(). Can't
    these be unified somehow?

This lab was completed in the span of one Boston to San Francisco
flight, minus time for dinner and a short nap. I guess that'd be four
hours or so.