[Caml-list] SQL engine in OCaml with client side cache

[Caml-list] SQL engine in OCaml with client side cache

[Diego Olivier Fernandez Pons]

[-- Attachment #1: Type: text/plain, Size: 1465 bytes --]

    Caml-list,

I need an SQL server that a web-client can query and send the results to
some JavaScript graphic package.
My problem is that the bandwidth and server power are limited and paid per
usage.

On the other hand, the data I am working with has good properties
- read only
- client always looking at the same subset of data from "different angles"
- easy to compute a subset of data the client will work on

For instance the database contains 5 years of sales of a company in all
their stores. Some clients will want to investigate all the products of a
given store, other will want to compare a single product on all the stores,
others the sales evolution per department per year, etc.

Therefore I thought I could add a "cache" on the client side, meaning an
in-memory SQL database that would receive a big block of data from the
server and work on it till the client writes a query that needs some data
that is not available locally in which case it would request it from the
server, etc.

I haven't found anything like that ready-to-use, so I was considering
reengineering existing OCaml code (database + web) and maybe compile it to
JavaScript. I have control on the client so I can afford installing an
OCaml runtime if needed albeit impractical though.

Does anyone has an SQL engine written in OCaml ? I can only find bindings.
Also, has anyone tested the OCaml -> JavaScript on projects with
significant computation work ?

        Diego Olivier

[-- Attachment #2: Type: text/html, Size: 1829 bytes --]

Re: [Caml-list] SQL engine in OCaml with client side cache

[Gerd Stolpmann]

Am Sonntag, den 29.01.2012, 10:56 +0100 schrieb Diego Olivier Fernandez
Pons:
> Caml-list,
> 
> I need an SQL server that a web-client can query and send the results to
> some JavaScript graphic package.
> My problem is that the bandwidth and server power are limited and paid per
> usage.
> 
> On the other hand, the data I am working with has good properties
> - read only
> - client always looking at the same subset of data from "different angles"
> - easy to compute a subset of data the client will work on
> 
> For instance the database contains 5 years of sales of a company in all
> their stores. Some clients will want to investigate all the products of a
> given store, other will want to compare a single product on all the stores,
> others the sales evolution per department per year, etc.
> 
> Therefore I thought I could add a "cache" on the client side, meaning an
> in-memory SQL database that would receive a big block of data from the
> server and work on it till the client writes a query that needs some data
> that is not available locally in which case it would request it from the
> server, etc.

I think this is not possible. SQL always needs access to the complete
table for executing queries (including the complete indexes). You would
have to restrict yourself to a subset of SQL where it is meaningful to
define caching. For example, a viable path would be to use
object-relational mappings (where range queries are usually not
possible). But this is not SQL anymore...

> I haven't found anything like that ready-to-use, so I was considering
> reengineering existing OCaml code (database + web) and maybe compile it to
> JavaScript. I have control on the client so I can afford installing an
> OCaml runtime if needed albeit impractical though.

As you are read-only: what about creating a dump of the whole SQL
tables, and to import it into a local SQL engine like sqlite? (There are
Ocaml bindings.) I don't know whether you can change the db schema, but
ideally it would support to make delta dumps (i.e. get all changes since
the last dump), for example by including time stamps in the rows.

Another option would be to use the replication feature of many SQL
servers. Basically, you would have to grab the logs (journals) of the
database, and to import them locally into an SQL server of the same
type. The keyword to look for is "log shipping". The nice thing is that
you automatically get a delta-based replication.

> Does anyone has an SQL engine written in OCaml ? I can only find bindings.

This is a lot of work. I have an on-disk btree implementation, if you
are interested (this is in the plasma download,
projects.camlcity.org/projects/plasma.html, look into src/pkv). It is
written for PlasmaFS, though, but a port to a local filesystem should
not be too difficult.

Gerd

> Also, has anyone tested the OCaml -> JavaScript on projects with
> significant computation work ?
> 
>         Diego Olivier
> 

Re: [Caml-list] SQL engine in OCaml with client side cache

[Diego Olivier Fernandez Pons]

    Caml-list,

[Gerd Stolpmann wrote]
> I think this is not possible. SQL always needs access to the complete
> table for executing queries (including the complete indexes).

I am surprised by your comments. Many systems have two-layer data
storage (massive but slow one, fast but limited one), and that doesn't
affect their semantics. Consider a compiler (heap/ registers), an
operating system (swap files, RAM) or even a typical SQL database that
keeps tables in memory for fast access.

This is the same but the hard drive is on the server side, the RAM on
the client side and they communicate by Internet.

I am not saying that implementing a generic cache / swapping system
for an SQL database is easy. That's why I added that for this specific
application I can easily compute a superset of the data the user will
need. Lets take an example : say my database contains sales history
data for a convenience store chain for all stores in France, all
products for last 5 years. If my user is the Coca-Cola replenishment
manager in Paris, he only needs sales of Coca-Cola products for the
last 5 similar days for each store in Paris. Thereafter I can generate
a query on the server that sends that superset of data to the client
and let the SQL client engine work on that.

I may have underestimated the amount of work to be done, because I
thought this would be on the easier side.
My idea was the following

Server side
- 3rd part SQL database
- OCaml bindings
- Web communication interface

Client side
- SQL parser written in OCaml + interpreter
- control system to guess superset of data and request from server
- Web communication interface
- output to JavaScript widget toolkit

I was expecting to find most of the pieces already done and only
having to glue them. I was actually more afraid of the JavaScript part
than the SQL one... You can even find SQL engines written in
JavaScript out there, to run in a web browser like Jade
http://jacwright.com/489/in-memory-javascript-database/ or JOrder
(JSON) https://github.com/danstocker/jorder

At the end that's nothing but arrays and for loops.

        Diego Olivier

Re: [Caml-list] SQL engine in OCaml with client side cache

[Gerd Stolpmann]

Am Sonntag, den 29.01.2012, 19:29 +0100 schrieb Diego Olivier Fernandez
Pons:
> Caml-list,
> 
> [Gerd Stolpmann wrote]
> > I think this is not possible. SQL always needs access to the complete
> > table for executing queries (including the complete indexes).

"Not possible" in the sense of: yielding a result with a performance
that is better than without cache. Also I was assuming the general case.

> I am surprised by your comments. Many systems have two-layer data
> storage (massive but slow one, fast but limited one), and that doesn't
> affect their semantics. 

The problem is to define locality here. Imagine you have a table with
two indexes, and the indexes are pretty independent of each other in
terms of locality (i.e. when y is the direct successor of x in one
index, the distance in the other index is large). How do you order the
rows of the table? For efficient caching it is essential that you can
guess which other data items will be accessed next. If you have
multi-dimensional locality as in this example, though, it will be
difficult to guess.

The SQL server "solves" this by deciding on a query strategy beforehand.
E.g. for an inner join involving two indexes it is usually possible to
iterate over one index, and then do lookups over the other one. This is
slow enough on a local disk - if you add more latency for the lookups on
the second index (because they are not in the cache), performance will
even be worse.

Note that there are also join algorithms that really need complete
tables, like sort-and-merge.

> Consider a compiler (heap/ registers), an
> operating system (swap files, RAM) or even a typical SQL database that
> keeps tables in memory for fast access.

This works on page level only (i.e. databases either rely on the page
cache of the OS, or implement their own page cache following a similar
design). So, it is pretty low-level.

If you try to have a cache on a higher level, you run into the problem
how to get the data via SQL statements. The following simple strategy
does not work: If the statement cannot be fully responded from the
cache, just send it to the server, and put the response rows into the
cache. Because: You don't know which rows have been omitted. You would
not be able to respond range queries from the cache.

So, to have a working cache you need quite direct access to the data,
e.g. like "retrieve all data from this position to that position", both
for tables and indexes. There are SQL cursors, but, so far I know, they
are not precise enough for this. I think this is probably solvable if
you know the data definition.

> This is the same but the hard drive is on the server side, the RAM on
> the client side and they communicate by Internet.
> 
> I am not saying that implementing a generic cache / swapping system
> for an SQL database is easy.

I think if you solved the generic case, you'd be a candidate for the
Turing award.

(Just as I side note: Missing scalability has always been a problem for
SQL databases. Currently, many companies go away from this technology
for their giant data warehouses just because of this. Of course, these
are not read-only, but read-write, but even having read-only scalability
would be a big achievement.)

>  That's why I added that for this specific
> application I can easily compute a superset of the data the user will
> need. Lets take an example : say my database contains sales history
> data for a convenience store chain for all stores in France, all
> products for last 5 years. If my user is the Coca-Cola replenishment
> manager in Paris, he only needs sales of Coca-Cola products for the
> last 5 similar days for each store in Paris. Thereafter I can generate
> a query on the server that sends that superset of data to the client
> and let the SQL client engine work on that.

This approach could in deed work. Basically, you define the locality
directly.

> I may have underestimated the amount of work to be done, because I
> thought this would be on the easier side.
> My idea was the following
> 
> Server side
> - 3rd part SQL database
> - OCaml bindings
> - Web communication interface
> 
> Client side
> - SQL parser written in OCaml + interpreter
> - control system to guess superset of data and request from server
> - Web communication interface
> - output to JavaScript widget toolkit
> 
> I was expecting to find most of the pieces already done and only
> having to glue them. I was actually more afraid of the JavaScript part
> than the SQL one... You can even find SQL engines written in
> JavaScript out there, to run in a web browser like Jade
> http://jacwright.com/489/in-memory-javascript-database/ or JOrder
> (JSON) https://github.com/danstocker/jorder
> 
> At the end that's nothing but arrays and for loops.

And an ugly parser :-(

If you can define the superset in a way so that it only depends on the
client but not on the client's queries, an option would be to use an
existing in-memory SQL database as cache. Sqlite has such a mode (use
":memory:" as filename), and AFAIK MySql, too.

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
Creator of GODI and camlcity.org.
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
------------------------------------------------------------

Re: [Caml-list] SQL engine in OCaml with client side cache

[Diego Olivier Fernandez Pons]

    Caml-list,

[Gerd Stolpmann wrote]
> The SQL server "solves" this by deciding on a query strategy beforehand.

What ??? I thought SQL servers shipped on-the-fly optimizing compilers
that would evaluate the query and use some heuristics (like table size
and density) to decide in which order to execute the loops + learning
on sequences of queries + on-the-fly reindexing.

[Gerd Stolpmann wrote]
> (Just as I side note: Missing scalability has always been a problem for
> SQL databases. Currently, many companies go away from this technology
> for their giant data warehouses just because of this. Of course, these
> are not read-only, but read-write, but even having read-only scalability
> would be a big achievement.)

Mmm... I thought relational databases were a universal object, in the
mathematical sense meaning any other object maps into them. What do
they use if not relational databases ?

> And an ugly parser :-(

You don't seem to like SQL much, which is surprising as it is kind of
isomorphic to comprehension of sets (of tuples). That's why F# added
first class SQL support with comprehension-like syntax
http://msdn.microsoft.com/en-us/library/hh225374(v=vs.110).aspx

The idea being probably that on top of a certified whole-program
optimizing compiler, pattern matching optimizer, multi-core capable
garbage collector and generalized lexing/parsing library, functional
language implementers will also have to write an optimizing SQL /
comprehension engine.

        Diego Olivier

Re: [Caml-list] SQL engine in OCaml with client side cache

[Gabriel Scherer]

> You don't seem to like SQL much, which is surprising as it is kind of
> isomorphic to comprehension of sets (of tuples). That's why F# added
> first class SQL support with comprehension-like syntax
>   http://msdn.microsoft.com/en-us/library/hh225374(v=vs.110).aspx

This may be a little off-topic (but who cares at this point?), but
I'll take the chance to do some self-advertising here.
We (Jerôme Vouillon and I) have done something related a few years
ago: Macaque, a DSL for writing typed and composable SQL queries in
OCaml, in a comprehension syntax.
  http://macaque.forge.ocamlcore.org/
  http://darcs.ocamlcore.org/repos/macaque/README

The comparison is that we also have something capable of typing SQL
queries as parts of OCaml programs. It more or less stops here, this
project is much less mature than the excellent LINQ work: it's mostly
a research prototype (with a very short development time: three
months) that hasn't been put to real use, mostly by lack of interested
users; it's understandable that the interest of the approach doesn't
compensate the cost of using a small, feature-restricted and
relatively arcane library when we have relatively solid SQL bindings.
By limitation of the implementation, it only supports PostgreSQL
(through the excellent PG'OCaml project, a pure-ocaml reimplementation
of the pgsql client protocol), and in retrospect the decision to use a
comprehension syntax instead of the real SQL syntax (that can be typed
all the same) is a bit unfortunate. But you may still be interested,
for example as inspiration if you decide to write some database stuff
in OCaml -- or, why not, as a user-developer.
  http://pgocaml.forge.ocamlcore.org/

For other SQL stuff in OCaml, see the Sqlite3 bindings, and possible
the "ocaml-orm-sqlite" project on top of it (whose approach is to use
code generation rather than a query DSL or combinator library; less
flexible, but result in simpler interfaces):
  http://www.ocaml.info/home/ocaml_sources.html
  https://github.com/avsm/ocaml-orm-sqlite


On Mon, Jan 30, 2012 at 12:26 AM, Diego Olivier Fernandez Pons
<dofp.ocaml@gmail.com> wrote:
>    Caml-list,
>
> [Gerd Stolpmann wrote]
>> The SQL server "solves" this by deciding on a query strategy beforehand.
>
> What ??? I thought SQL servers shipped on-the-fly optimizing compilers
> that would evaluate the query and use some heuristics (like table size
> and density) to decide in which order to execute the loops + learning
> on sequences of queries + on-the-fly reindexing.
>
> [Gerd Stolpmann wrote]
>> (Just as I side note: Missing scalability has always been a problem for
>> SQL databases. Currently, many companies go away from this technology
>> for their giant data warehouses just because of this. Of course, these
>> are not read-only, but read-write, but even having read-only scalability
>> would be a big achievement.)
>
> Mmm... I thought relational databases were a universal object, in the
> mathematical sense meaning any other object maps into them. What do
> they use if not relational databases ?
>
>> And an ugly parser :-(
>
> You don't seem to like SQL much, which is surprising as it is kind of
> isomorphic to comprehension of sets (of tuples). That's why F# added
> first class SQL support with comprehension-like syntax
> http://msdn.microsoft.com/en-us/library/hh225374(v=vs.110).aspx
>
> The idea being probably that on top of a certified whole-program
> optimizing compiler, pattern matching optimizer, multi-core capable
> garbage collector and generalized lexing/parsing library, functional
> language implementers will also have to write an optimizing SQL /
> comprehension engine.
>
>        Diego Olivier
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] SQL engine in OCaml with client side cache

[Gerd Stolpmann]

>     Caml-list,
>
> [Gerd Stolpmann wrote]
>> The SQL server "solves" this by deciding on a query strategy beforehand.
>
> What ??? I thought SQL servers shipped on-the-fly optimizing compilers
> that would evaluate the query and use some heuristics (like table size
> and density) to decide in which order to execute the loops + learning
> on sequences of queries + on-the-fly reindexing.

Yes, but this happens before the query is executed. Once the execution
starts, the plan is not changed anymore.

> [Gerd Stolpmann wrote]
>> (Just as I side note: Missing scalability has always been a problem for
>> SQL databases. Currently, many companies go away from this technology
>> for their giant data warehouses just because of this. Of course, these
>> are not read-only, but read-write, but even having read-only scalability
>> would be a big achievement.)
>
> Mmm... I thought relational databases were a universal object, in the
> mathematical sense meaning any other object maps into them. What do
> they use if not relational databases ?

Well, this is the NoSQL world (=not-only SQL). In short:

 - You accept that you store data in non-normal form. In SQL
   the preferred model is to store one information only once,
   and to do all joins at query time. In NoSQL it is usual to
   repeat information to avoid joins, even if this means that
   updates become more complicated.
 - On the technology side, you use alternate data stores like
   distributed key/value stores or column-based stores. At
   least at query time.
 - For preparing data, one of the new technologies is map/reduce.
   Basically it's a massively scalable form of sorting data.

Of course, this is all not as universal as the good old SQL world.
Especially it is a non-match for OLTP. But if you can separate data
preparation from data querying, it's an option that opens the door to
almost infinite scalability. It's what the web-2.0 companies use.

>> And an ugly parser :-(
>
> You don't seem to like SQL much, which is surprising as it is kind of
> isomorphic to comprehension of sets (of tuples). That's why F# added
> first class SQL support with comprehension-like syntax
> http://msdn.microsoft.com/en-us/library/hh225374(v=vs.110).aspx

I did not say that I dislike SQL. It's still the most important DB
technology, and often it is the only choice we have. And you are right, it
is about set operations. Nevertheless, the syntax has strange aspects
(e.g. no reserved words, or that you cannot nest SELECTs arbitrarily, e.g.
(SELECT ... UNION SELECT ...) INTERSECT SELECT ...). The best thing is
that it is standardized.

The F# syntax is interesting (I frequently thought about integrating SQL
as DSL into Ocaml best, and did not find any good solution).

> The idea being probably that on top of a certified whole-program
> optimizing compiler, pattern matching optimizer, multi-core capable
> garbage collector and generalized lexing/parsing library, functional
> language implementers will also have to write an optimizing SQL /
> comprehension engine.

Yeah, an attempt to raise the bar.

Gerd

>
>         Diego Olivier
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>
>


-- 
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
Creator of GODI and camlcity.org.
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
*** Searching for new projects! Need consulting for system
*** programming in Ocaml? Gerd Stolpmann can help you.

Re: [Caml-list] SQL engine in OCaml with client side cache

[Marc Weber]

Excerpts from Diego Olivier Fernandez Pons's message of Sun Jan 29 10:56:25 +0100 2012:
> On the other hand, the data I am working with has good properties
> - read only
Libraries like smarty (PHP caching framework) do it this way :

fun render_and_cache_id (id)
  let query_db_then_render = fun() -> build_html ( query_db ( id_of_thing .. ))
  return cache(id, timeout, render_html)
endf

id is the id identifying the database data. Thus for each id the
database is queried only once - and the data is only rendered once.

Obviously this only works great if you have readonly data - or if its ok
if your data is out of date. You can invalidate it using timeouts etc.

Marc Weber

Re: [Caml-list] SQL engine in OCaml with client side cache

[Daniel Bünzli]

Le dimanche, 29 janvier 2012 à 10:56, Diego Olivier Fernandez Pons a écrit :

> Therefore I thought I could add a "cache" on the client side, meaning an in-memory SQL database that would receive a big block of data from the server and work on it till the client writes a query that needs some data that is not available locally in which case it would request it from the server, etc.
>  
> I haven't found anything like that ready-to-use, so I was considering reengineering existing OCaml code (database + web) and maybe compile it to JavaScript. I have control on the client so I can afford installing an OCaml runtime if needed albeit impractical though.
If you can afford to install recent browsers, on the javascript side.

Webdatabase [1] would have made your day but the spec has been withdrawn. It seems work along these lines was pursued in IndexedDB [2] but it may be a little bit early to use it.

If the dataset is not too huge and your queries are simple enough you may be able to hack a thin layer on top of webstorage [3]. But beware that this gives you no more than a persisent hashtable and I have no indication of the kind of performance you'd get. The advantage is that this is a candidate recommandation.  

Note, I have used neither of those. Just know their existence.  

Best,

Daniel

[1]
http://www.w3.org/TR/webdatabase/
http://caniuse.com/#search=websql



[2]
http://www.w3.org/TR/IndexedDB/
http://caniuse.com/#search=indexed

[3]  
http://www.w3.org/TR/webstorage/ (http://www.w3.org/TR/webstorage/#storage)
http://caniuse.com/#search=webstorage