Document the schema format planned for version 1.0

The current plan for version 1.0 is to remove functionality that's outside the
short-term needs of dailygieselmann.com, and make sure the tools are close to
optimal for those needs.  This means limiting ourselves to summary tables,
inverted index tables and time series tables.  The query language will be
reduced and specialized, the LLVM dependency and transaction logic will go
away.

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
Document the desired procedure for building indexes

The documentation works as a design document in this case, since the described
procedure does not actually work yet.

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
README: Corrected grammar

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
Removed unused variable from ca_sql_ts_sample

The new time series representation, offset/score, implicitly stores length, so
we no longer need the "end" variable.

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
ca-load: Pointlessly initialize variable to satisfy compiler

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
Removed SELECT, UPDATE and transaction support.  Use plain-text schemas

The purpose of this commit is the remove features that will not be part of
version 1.0, but might be part of future versions.

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
ca-load: Avoid flushing between reads

By flushing after every read, we end up with duplicates in the output table.
Instead, we must flush after all input has been processed.

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
ca-load: Sort values by offset before flushing

This will simplify inverted index creation; the producer only needs to sort by
keyword before sending the data to us.

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
Added support for SAMPLE queries

A SAMPLE query will look for a given key in all time-series tables, and print
the first match.

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
Removed tests that are not relevant to version 1.0

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
Removed mentions of LLVM in build scripts

LLVM isn't used for anything in version 1.0.

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
ca-load: Added the ability to generate indexes

This means that the string in the second input column is looked up in the
summary table, and if one is found, it is translated to the offset of that
document.

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
Remove the ca-sort program, since we're relying on GNU sort now

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
Makefile.am: Add -lpthread for tests/fifo-00

When using binutils-gold, -lpthread is not automatically pulled in the
libca-table.so.

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
ca-load: Add support for summaries

With this in place, we should have the necessary tools to build and query an
inverted index.

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
tests/wo-sort-00: Replace assertion with error message

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
writeonce: Use hashing instead of binary search

So far we've been using binary search to look up items in writeonce tables.
However, some of the inverted index tables have tens of millions of rows,
resulting in more than 20 seeks per lookup.  This commit replaces the sorted
array of offsets with a hash table with a load factor of 50%.  Furthermore, we
allow offset values to be either 16, 32 or 64 bits.

We use thte X31 hash[1], an open addressing scheme and fibonacci chaining.

Also, lookups into summary tables have required an access to the sorted array
of offsets in order to find the size of the row.  After this change, row sizes
are store inline in the table, so that we can seek directly to the desired
position.

The one major optimization we can do beyond this commit, is storing inverted
index keys in hash order, so that colliding entries are guaranteed to be stored
physically adjacent, eliminating any extranous seeks during lookup.

1. https://mail.gnome.org/archives/gtk-devel-list/2000-February/msg00057.html

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
Get rid of the requirement to use absolute paths for schemas

Requiring absolute paths is not user-friendly, and does not accomplish
anything.  We chdir into the directory containing the schema definition in
order to survive lazy unmounts and directory renaming.

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
query-lexer: Re-add TIME which was accidentally removed earlier

This token is needed for SET TIME FORMAT.

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>
ca-load: Add virtual offset during index creation

This is a bugfix; without this patch, offsets stored in the index would not
match the virtual offsets given in the schema definition.

Signed-off-by: Morten Hustveit <morten.hustveit@gmail.com>