Wednesday, August 4, 2010

Doing star schemas in MySQL...

One big problem in MySQL is that it can't do a native "star transformation" query. In practice, this means that only one index can be used for a given table in a search.

So, to do a star transformation, you have to jump through some hoops. These hoops may look silly, but they do work well, particularly for large tables (ie, more than 100M recs or so).

The problem is if you have a table that is to be searched in a relatively ad-hoc fashion, particularly if searched columns are ANDed together.

Let's say you have a table like

(id, searchcol1, searchcol2, searchcol3, ... searchcolN, datacol1, datacol2, ... datacolM) primary key (id);

A typical approach would be to create indexes on all the search cols and enumerate searches in the whereclause. The MySQL query optimizer will pick an index for one of them and do simple qualifications on the rest of the searches. This means that you have to hope that your most selective search column gets picked, and that it doesn't visit many rows or your search performance will suck.

An alternate approach is to use "helper tables". These tables are standalone tables with (ID, searchcol[i], ), and use carefully constructed multi-value primary keys with searchcol as the first key column, your other standard searches as the other key components, and the ID as the last key component to guarantee uniqueness.

With helper tables, you do your individual searches into TEMPORARY tables containing only IDs, use "SQL INTERSECT" to implement AND logic and "SQL UNION ALL" to implement OR logic, and put the final result set into a final TEMPORARY table. After this, you can do the lookup on the big table to fetch the final answer.

In practice, this means you're using all indexed searches to "vector in" to the final result set. We've been able to get good "sort of" ad-hoc search performance with up to 500M records with the above approach.

Wednesday, July 21, 2010

Templates and canonical columns

An idea I'm playing with is having "template types" or "base types", which basically allow structured documents to have many types of records, but which have a few columns in common, using a mechanism which would look something like inheritance. This would allow all the records in structured documents to be globally query-able on common columns. This actually makes more sense in structured docs than it does in general relational tables (as POSTGRES tried to use this idea) since the query is still well-defined and bounded in scope to a particular structured document.

An obvious use for this would be a timestamp column, so you could fetch all of today's records for a given person, etc. I'd probably use a syntax similar to the "star" traversal notation used in POSTQUEL for this sort of thing.

Thursday, July 8, 2010

Indexes on Structured Documents

While structured documents aren't intended for massive "galactic" searches across the document universe, docs will need to be at least somewhat galactically searchable. To support this, one can create indexes on the document universe, on "scalar" columns in records (ie, you can't index a column of record type). These indexes will be "sparse" in that if no records of the indexed type exist in a document, it won't have an entry in the index.

Within documents, pre-defined dynamic indexes are built when the doc is initially loaded. These indexes are, as above, on "scalar" columns, not

Initially, we'll support in-memory "equality-only" indexes will be of the "indexed hash" type, meaning a hash value is stored in the index itself, and only if the hash matches will the value itself be fetched and checked for equality. This will be a fairly expensive operation so we'll allow longish hash values.

Characters and Character Handling

There will be three character representations: VARCHAR, which is an 8 bit representation, NVARCHAR, which is a 16 bit character representation (with an internal compression used for all-ASCII strings), and NVARCHAR4, which is a 32 bit (4 byte) representation. Query text will be done in NVARCHAR4, although all query keywords and identifiers will be C locale alphanumerics and representable in 7 bits. BINARY will also be available.

In addition to the above, there'll be a couple compact representations available: RCHAR4 (4 bits per character for an enumerated set of 16 characters), and RCHAR6 (6 bits per character for an enumerated set of 64 characters). The specific characters used for an enumeration will be done by the creation of a TYPE, ie

CREATE CHARACTER TYPE HEXSTR USING RCHAR4 VALUES ('0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F');


Note that HEXSTR may be a "builtin".

Sorting and Ordering

ORDER for ORDER BY and indexes will be done using native byte ordering unless an ORDER BY function is used, either in the query or in the CREATE INDEX definition for ordered indexes. (What exactly ORDER BY functions mean will be discussed later after I think about them a bit more...)

Also note that BINARY cannot be interpreted as a character set and only supports single-byte native ordering.

Wednesday, July 7, 2010

Idea: polymorphic column types

One thing I've always thought would be useful is polymorphic column types, to reduce the need in "generic" records of having stuff like

create table foo (id int, b varchar (list of typenames), c1 type1, c2 type2, c3 type3, ...);

A polymorphic column type would be a column that can take on a type specified in another column, so the above would be replaced by

create table foo (id int, b typename, c typespec(b));

where column "b" specifies a type, and "typename" is a special pseudo-type that would contain names like "int", "varchar(10)", etc.

Polymorphic column types would behave like variable-length columns for storage purposes, and would probably only be retrievable as opposed to searchable, although we could allow them to be searchable if we insist that the search operator/function be type-compatible with the row and evaluate to NULL if it isn't.

The client-side row fetch API would need to be somewhat clever to handle this, but since the type of a given row is well-defined, this shouldn't be all that hard to implement.

Tuesday, July 6, 2010

Proposal for an open-source database

While there are numerous open-source databases out there, there isn't one that specializes in the areas I'm most interested in exploring, or the areas I see the biggest weaknesses in as far as database usage is concerned.

I. Some ideas I'd like to explore:

1. A "not only SQL" database, but one which still allows full access via a query language.

2. A hybrid of relational table structures and "structured document" access and storage. I'll define "structured documents" shortly, but in general they are largish objects with key-value-pair behavior, but - unlike databases like Berkeley DB - they have engine-visible internal structure beyond the key and can be queried and internally manipulated using the query language.

3. A notion of transactional "ACID-ity", allowing for more interesting low-level storage approaches. A well-defined notion of transaction with predictable semantics and meaningful locking, visibility, and crash recovery is required for any database that will be used for anything resembling mission-critical data, but I want to have the freedom to implement the "structured documents" in such a way that they aren't overly limited by the need for "global COMMIT".

4. As mentioned above, there'll be a query language. It will even resemble SQL in many ways, although it won't attempt to be compatible, except in areas where SQL syntax makes as much sense as any other.

5. I haven't yet decided whether it'll start out fully client-server, or whether I'll implement it as a application-resident C library in the same fashion as SQLite and "server-ize" it later.

II. My "Design Aesthetic"

1. The "embedded" approach

Embedded or small-device databases is where I've spent most of my recent career, so the "embedded aesthetic" of favoring efficiency and control over lots of abstraction and heavy use of third-party tools will be a design principle. But I'm hoping that the database can be used for larger systems as well.

2. Few abstractions, but "good" ones.

Database engines lend themselves well to some obvious abstractions and layering, while being extremely unforgiving to "whiteboardist" approaches.

III. What the heck is a "structured document"?

A structured document is a fancy name for a blobby name-value pair thing, in which the "value" has internal structure that is visible to the database engine. The structure will be in the form of "records" that can be inserted to, deleted from, or queried in the document. Also, the document will have dynamic indexes that will be built when the doc is loaded into memory so it can be searched efficiently - and directly, without needing a join. The entire contents of a structured document can also be fetched into the application so it can be loaded quickly and conveniently for apps interested in doing so. Also, as mentioned above, there'll be a simple relational capability, so that rows in a structured doc *can* be joined against relational table data, etc.

IV. The type system

This database will support the standard SQL datatypes, as well as user-defined "record" types. Nested and ordered records *may* be allowed (not sure yet).

V. Other ideas

1. Internal hierarchies in structured documents

Structured docs won't have syntax-level support for hierarchical representations, but there will be enough infrastructure so that apps can implement hierarchical structures - such as XML docs - if they so desire. I'm still thinking about this one though - supporting nested records does imply support for hierarchies. Note that if I do full nesting and hierarchies, all record contents - including nested contents - will be stored contiguously in the doc as link-chasing is Evil, both semantically and in terms of implementation.

2. Documents will be relatively free-form.

Documents will be members of a query-able set, and all documents in a set must have a similarly-structured key, as well as a small set of other records that all documents are "required" to have, but, beyond that, docs can have records of a particular type added without needing to change the definition of all records. The query language will be sufficiently permissive to allow traversal even if not all docs have a particular type of record.

3. At the storage level, database pages are "owned" by documents, so the design expectation is that they're relatively large (ie, >4K per document). Also, the storage system will attempt to store pages belonging to particular documents contiguously, and there'll be a way for the application to declare how much space to initially assign to a particular doc (or doc-set) in advance when a new doc is created so the trade-off between space efficiency and contiguous storage can be managed by the app developer.

VI. It's still rather half-baked, ain't it?

Yes, it is. As I think about this more, I'll obviously have to rigorize the above very loosey-goosey descriptions into something resembling a spec before I start coding.

Heck, I haven't even named the thing yet! Any help here is appreciated...