Fwd: Search::GIN range queries

I hate gmail's defaults. *sigh*


---------- Forwarded message ----------
From: Yuval Kogman <[email protected]>
Date: 2009/8/16
Subject: Re: Search::GIN range queries
To: Ask Bj=C3=B8rn Hansen <[email protected]>


Sorry for taking so long to reply.

The short answer is no, Search::GIN does not yet know about the
ordinality of the keyspace, so specifying range queries is currently
impossible (there's no way to describe them to the query or to the
indexing).

But this is temporary (FSVO, e.g. heat death of the universe ;-).

The long term plan is multipronged.

A little background: Search::GIN is *extremely* under implemented for
its overall plans, the problem is that at work we generally don't have
heavy searching requirements so this half assed version is enough to
do everything we need. The long term plan for this addresses
specifying queries in a flexible way.

Furthermore, right now we have a fairly primitive API in
Data::Stream::Bulk that's designed to be at least somewhat extensible.
These streams will expose data about ordinality, cardinality etc in
the future, and support operations like sorting/slicing/seeking
through roles. The long term plan for this addresses using query
results in a flexible way.

Thirdly, DBIx::Class resultsets are going to be much better supported
for the DBI backend in the short term future.. Since it already
implements both of the things DSB and SG are trying to address, I'd
like to expose that functionality first, since it's a lower hanging
fruit.

This is how it's supposed to come together:

Search::GIN currently uses an adhoc model for key extraction and
indexing, but really what we need is a schema for multiple indices,
where the extractor can insert keys into any one of these.

Secondly, query specification should not need to worry about the
keyspace, but rather about an extraction space. Having an
extractor/query specifier pair for a certain data point does not
necessarily mean that this is indexed.

Thirdly, an extensible AST for a query language specifying predicates
will be added. This is the most lacking bit.

With absolutely no regard for the final sugar layer, the idea is to
have logic predicates much like a prolog program does, which produce a
set of objects in the end.

High level operations like set operations on the data results can be
expressed with this.

This is a loose and partial port of the PostgreSQL AST for queries
(the high level one).

The idea is to take this tree of operations and compile it down to a
low level representation, based on the backend.

SQL is the big winner here, almost every feature of Prolog can be
expressed with SQL pretty easily, especially with modern extensions
such as recursion. This means that the Search::GIN to SQL compiler
will be rather straight forward to implement.

BDB is a little more work. Initially a unification algorithm can
implement the queyr language but it will be very hard to make it scale
for large data sets. The plus side is that since the design has
already been worked out by PG we can do a fairly direct port of their
low level query algebra (including their very impressive query planner
and optimizer), and get something pretty decent based on BDB cursors.

Note that none of this has anything to do with KiokuDB so far, it's
supposed to be a library for specifying and executing queries on a
number of backends, from a verbose, OO query AST.

Finally, the $dir->search api is going to get an extension that allows
query preparation that returns an object similar to the searching half
of DBIx::Class::ReusltSet, making use of the fact that the GIN query
ASTs are in principle composable.

$dir->search is essentially $dir->execute_search(
$dir->prepare_search(@_) ) in the abstract.


Obviously this is all pretty far away from what we have right now, but
I wanted to share and document this roadmap.

The way I see range queries tying into Search::GIN sooner is by
starting to define the query AST and stubbing the query compiler with
something that can compile very primitive queries to SQL directly.

What I suggest doing now is playing around with the DBI searching,
keeping in mind that we'll have support for a hybrid DBIC/KiokuDB
schema pretty soon. If that addresses your needs then this is the best
plan of action.