It's Not Just the Data Model...

[Mike Malone]

Hey folks,

I've been following the spec and have put together an implementation of the select-stmt production for a database system we've developed internally where I work. So far things are working just fine, but I do have some concerns. In particular, I'm wondering how much work you intend to do to define semantics in certain troublesome areas where "NoSQL" (and SQL) database systems tend to disagree.

Let me start with an example from the spec website (the "UPSERT" example):

    UPDATE abc SET abc.n=abc.n+1 WHERE abc.page=="/page/one"
        ELSE INSERT {page:"/page/one", n: 1, create_time: 1234567};

Already, the semantics of this operation make some tacit assumptions about the isolation level and the consistency model of the database system. And already, the syntax is not expressive enough to provide all of the necessary information for systems like Cassandra that rely on client-provided logical clocks and operation idempotence as part of their consistency model.  

I'd be happy to go into more detail, but first I was wondering whether you _care_ to define this sort of thing. Ultimately, I think something will have to bridge this gap for a universal query mechanism to be useful. But it doesn't seem to be an easily solvable problem. Meijer's work with LINQ may provide a starting point for bridging the data models, but it does not address the distinctions between consensus protocols, global serialization (or lack thereof), consistency model, isolation model, etc.

Anyways, my biggest concern is that these issues are ignored completely. If they're explicitly left ambiguous and implementation defined that's fine (I guess), but it would be a shame if UnQL painted implementations into a corner conceptually by making the same sorts of subtle assumptions that SQL does about these issues.

Mike

[Richard Hipp]

On Wed, Aug 10, 2011 at 1:53 PM, Mike Malone <mi...@simplegeo.com> wrote:

I'd be happy to go into more detail, but first I was wondering whether you _care_...

I care.  What are your concerns?

--
D. Richard Hipp
d...@sqlite.org

[Mike Malone]

On Wed, Aug 10, 2011 at 11:21 AM, Richard Hipp <d...@sqlite.org> wrote:

On Wed, Aug 10, 2011 at 1:53 PM, Mike Malone <mi...@simplegeo.com> wrote:

I'd be happy to go into more detail, but first I was wondering whether you _care_...

I care.  What are your concerns?

Based on my interpretation of the UnQL semantics, in the "UPSERT" example the increment operation is not idempotent. If the operation is applied twice, abc.n would have the wrong value. This is a problem for any distributed system that relies on at-least-once messaging for inter-entity (inter-node) communication (as Cassandra and Riak do for replication, for instance). Since a message might be replayed, an operation might be applied twice.

This problem is not insurmountable, I suppose. Incoming messages could be tagged with a UUID, and operations could fake idempotence by remembering that they've been applied to an entity within the entity's transactional scope (e.g. by writing metadata to the entity). But that's not a very appealing solution in general, and not one that's presently implemented by these systems.

Indexes pose a bigger problem. In an imaginary "infinite-scale" system it's very difficult (impossible?) to keep alternate indexes transactionally consistent. That's fine sometimes, but not all the time. Ideally, a query language would provide some mechanism for clients to tell the system how to balance query optimizations with consistency and isolation. To allow for this the query language would need to define universal isolation and consistency levels. I'm not sure if that's even possible (though SQL has certainly tried). These issues come up again when performing joins. Without global serialization it's impossible to perform a consistent join across entities.

Another subtle problem is introduced simply by distinguishing between updates and inserts. A database that uses log-structured merge (LSM) for durable storage and logical clocks for conflict resolution doesn't typically do a read-before-write. But, in order to enforce (what I assume are) the semantics of insert/update (insert fails if the data already exists, update fails if it doesn't), you're forced to check the existing data before responding to the client, and give up a lot of what you gain from LSM.

This is just off the top of my head, so I'm sure more will come up. Regardless, I'm guessing that having a standard data manipulation language will prove valuable even if the semantics aren't identical across every implementation. That said, it'd sure be nice if the semantics _could_ be identical across every implementation without forcing ugly kludges and compromises.

Mike

[p...@pi.net]

Mike,

I share many of your concerns, although coming from the opposite side.
The SQL isolation levels were defined trying to create a framework
around then current implementations (i.e. lock based, and totally
missing mvcc) and I fear we may repeat the same mistake. That being
said: if this area is left vague, then conforming implementations will
be subtly incompatible and moving applications from one UnQL back-end
to another becomes just as hard as porting from say DB2 to Oracle.

However, in my view the power of a 'post-modern db', to borrow the
phrase, is in that it handles the hard parts, not in shifting the hard
parts to the application. In a SQL system it is not handy for the
application to do transactions itself -- although MySQL for a while
advocated that, and sure it is possible.

It may turn out to be necessary, but I think that the application
doing loop joins (because the backend refuses to do joins), or the
application handling lamport clocks (because the backend refuses to do
so) is wrong. Note: I'm not trying to pick on Cassandra or Riak here,
I'm trying to make a general point. It is better to have a more
complicated backend that solves these issues in a sound way than to
have many application devs developing possibly poor implementations
for the same.

Perhaps part of the problem is that distributed transactional systems
are not well enough understood as yet; when compared to SQL we live in
1980 so to speak. One topic that has my interest is the meaning of
consistent (i.e. acid) in CAP. If the C must hold for the entire
system, the CAP theorem applies, but if the C must hold only when
viewed through the lens of individual transactions it may not. One can
think of this in the following way: in a single node database snapshot
isolation eases serializable by using parallel versions and imposing a
total order on transaction begin times; in a distributed system this
could be further relaxed to imposing only a partial (causal) order on
transaction begin times.

I do not pretend to have it all figured out, quite the opposite. I
simply agree with you that this area of the spec needs to be
thoroughly discussed and understood before final decisions are being
made.