RE: Join order and access path

Jeffrey Lichtman wrote:
> I would like to see hash tables that spill to disk. 
Ideally, the hash
> table
> should be an in-memory structure with a conglomerate as a 
backing store. I
> would want the backing store to be used only when 
necessary - that is,
> only
> when the hash table grows too big. The biggest problem with 
this idea is
> how to estimate the cost of building and maintaining the 
table. One
> approach could be to put a limit on the number of in-memory 
rows in the
> hash table and use a statistical formula for the cost of 
reading a row,
> using the number of in-memory rows versus the total number 
of rows to
> estimate the chances of finding a row in memory.
> 
> Another approach could be to use weak references in 
managing the hash
> table
> (a weak reference is a Java construct that allows the 
garbage collector to
> nominate an object for garbage collection even when it has 
a reference to
> it). Weak references are useful for memory caches that 
adjust themselves
> to
> the memory available to the JVM. One of our original ideas 
for Derby (nee
> Cloudscape) is that it should be a low-maintenance DBMS, 
with little
> intervention required to keep a working system running. A 
self-managing
> cache could help with this - it would adjust itself to 
environments with
> different amounts of memory (although small-memory 
environments could hurt
> performance). I don't know how the optimizer would estimate 
the cost for
> building and maintaining a hash table in this case.

This is over a year and a half old, but on the old ldapd 
project at source forge, we played with an adaptive cache, 
sort of a hybrid mix between DBL and FRC caches. Check out 
the doc. I believe the code implemented the S region, but not 
the P (phantom). Well, here's the link:

http://cvs.sourceforge.net/viewcvs.py/ldapd/sandbox0/cache/