Re: Caching in the dynamic database

On 13/02/2014, at 6:22 PM, Michael Ben Yosef wrote:

> Hi Richard,
> 
>> Before trying anything exotic, is there any possible
>> refactoring of the existing data to take less memory to
>> start with?
> 
> I must confess I don't have any existing data in mind. I was
> considering it as a purely intellectual exercise. That is, suppose we
> are working with some data that is definitely larger than memory.
> Let's say that it's in the form of an external relational database.

Hold it right there.

The following observation has nothing to do with Prolog,
and everything to do with relational databases and what
the *point* of a relational database is.

If you are interfacing to a database from *any* language
and you do your own caching and the database engine does
not know about the caching you are doing and has no way
to invalidate your cache, then you *WILL* lose the ACID
guarantees and eventually you *WILL* get inconsistent
results.

You can get away with your own caching if (and I would like
to say only if):
 - nobody at all is changing the data, or
 - you are changing the data and nobody else is looking at it, or
 - you keep the database engine fully informed of what you are
   up to and give it the power to invalidate your cache.

> Every time we read from or write to the database we do I/O, possibly
> over a network.

That need not be true.  SQLite famously works in-memory.
FireBird (www.firebird.org) is a long-established full-featured
SQL database comes in that four versions, one of them "embedded",
http://www.firebirdsql.org/manual/fbmetasecur-embedded.html

What happens with that is that you link the database engine
as part of your program and you talk to it directly.  The
cost of a call to the database is pretty light, and the
huge thing here is that

	THE DATA BASE DOES THE CACHING

so you are not losing any of the benefits of using a
relational data base.

> For many common access patterns it would be much
> faster to cache as much as possible of this external database as facts
> in Prolog's dynamic database.

It is or can be orders of magnitude faster to use Prolog
*instead of* a relational database.  But looking at a system
as a whole, the setup you describe has caching done *twice*.
(Prolog caching stuff and the database caching the same stuff.)
That's going to make *less* memory available overall.
But the worst of it is that there's no cache coherence protocol
to keep the two caches consistent.  Using Firebird embedded
you do still have to pay the price of converting data between
Prolog format and database format, BUT you get *SAFE* caching.

> What I was asking was, "How much is as much as possible?".

The answer depends on what _else_ is happening on the same
machine.  

> For example, if every time I read a row from from
> the database I assert a fact for it, how do I know when I'm starting
> to fill up memory and I should retract a few lesser used facts before
> asserting any new ones?

Let's return to my question.
>> 
>> Before trying anything exotic, is there any possible
>> refactoring of the existing data to take less memory to
>> start with?

The very fact that you speak of "read(ing) a row" suggests to
me that you might not be used to thinking in terms of column-
oriented databases like InfoBright or Monet or C-Store.  These
are SQL databases just like traditional row-oriented databases,
but they fetch from disc just the columns that are relevant to
your query.  (Apparently DB2 and SQL Server can be configured
to do this too, but I don't know the details.)  Bringing less
data from disc into the DB engine and importing less data from
the DB engine into Prolog is the first thing to try before any
fancy dialect-specific hacking on the guts of the Prolog clause
store.

I'd like to point out also that the Prolog clause store has always
been designed for *procedures*; clauses that might do serious
pattern matching and are likely to have significant bodies.
It is likely that a specialised storage system for predicates
containing only ground unit clauses could
 - take less space
 - make richer/better indexing straightforward
 - be cheaper to modify
I think if you want to cache (views of) relational data inside
Prolog, _this_ is the place to start, not the existing clause
store.