Query Anything with SQLite

Virtual tables are the foundation of some of SQLite's larger features, including full text search.


November 06, 2007
URL:http://www.drdobbs.com/web-development/query-anything-with-sqlite/database/query-anything-with-sqlite/202802959

Michael is a programmer and the author of the Apress book The Definitive Guide to SQLite. He can be contacted at [email protected].


SQLite is an embedded relational database engine implemented in ANSI C. It supports a large subset of ANSI SQL and many other features common to relational databases such as triggers, indexes, and auto-increment primary keys. It is known for its small size (256 Kb), reliability, ease-of-use, and elegant design. Also, SQLite's code is public domain and can be used free of charge for any purpose. SQLite (www.sqlite.org) is used in a variety of software, such as Mozilla Firefox, PHP5, Google Gears, and Adobe AIR, as well as embedded devices such as cell phones using Symbian OS.

SQLite has a number of unique features, one of the most interesting of which is virtual tables. With virtual tables, you query not only what is in a database, but what is outside of it as well. For instance, with a little coding, you could use SQLite to search through your filesystem and issue queries such as:

create virtual table fs using filesystem;
SELECT 
  prot, uid, gid, size/(1024*1024)      as 'size (Mb)', 
  dev, path || '/' || name as file from fs 
WHERE 
  path = '/usr/lib'
  AND name like '%.so'"
  AND size > 1024*1024*4 
ORDER BY size desc;  

You could also write a virtual table to read your log files or filter SNMP data. Basically, anything your program can parse, read, or grab is fair game.

In this article, I present a virtual table that interfaces with the filesystem. It uses the Apache Portable Runtime, which enables it to work with multiple operating systems. Because SQLite is portable, it only makes sense to try to keep virtual tables portable as well, and the APR is helpful in this regard.

The API

You implement a virtual table using three structures. The first is the module structure, which is an array of function pointers. These are callbacks you implement to let SQLite operate on your table as if it were a native table. Some of these functions are mandatory, many are optional. For example, if you don't need to support transactions, you don't have to implement the related functions. You just set the respective callbacks to null.

Listing One is the callback structure for our virtual table. The other two structures are the vtable and cursor structures (Listing Two).

static sqlite3_module example_module = 
{
    0,              /* iVersion */
    vt_create,      /* xCreate       - create a vtable */
    vt_connect,     /* xConnect      - associate a vtable with a connection */
    vt_best_index,  /* xBestIndex    - best index */
    vt_disconnect,  /* xDisconnect   - disassociate a vtable with a connection */
    vt_destroy,     /* xDestroy      - destroy a vtable */
    vt_open,        /* xOpen         - open a cursor */
    vt_close,       /* xClose        - close a cursor */
    vt_filter,      /* xFilter       - configure scan constraints */
    vt_next,        /* xNext         - advance a cursor */
    vt_eof,         /* xEof          - indicate end of result set*/
    vt_column,      /* xColumn       - read data */
    vt_rowid,       /* xRowid        - read data */
    NULL,           /* xUpdate       - write data */
    NULL,           /* xBegin        - begin transaction */
    NULL,           /* xSync         - sync transaction */
    NULL,           /* xCommit       - commit transaction */
    NULL,           /* xRollback     - rollback transaction */
    NULL,           /* xFindFunction - function overloading */
};

Listing One

/* vtab: represents a virtual table. */
struct vtab
{
    sqlite3_vtab base;
    sqlite3 *db;
};
/* vtab: represents a singe cursor with which it iterate over the virtual table. */
struct vtab_cursor
{
    sqlite3_vtab_cursor base;
};

Listing Two

Because all of the callback functions use pointers to reference these structures, you are free to extend them. SQLite only needs the sqlite_vtab and sqlite3_vtab_cursor portions of the structures to operate.

Initialization

The first callback function to implement is xCreate(), which creates the virtual table. This is called once—specifically, when the first database connection declares the virtual table via the CREATE VIRTUAL TABLE statement.

xCreate()'s job is to set up the virtual table environment and initialize any necessary resources. The implementation (vt_create()) is in Listing Three. It allocates a vtab struct and passes it back to SQLite using the vtable pointer reference it passes in (pp_vt). SQLite also passes in a reference to the database connection, so you store a reference to it in your vtab structure. In so doing, SQLite has a reference to a new vtab struct, which in turn has a reference to the database connection.

In addition to allocating a vtab structure, vt_create() also declares the table using sqlite3_declare_table(), passing SQLite the SQL (DDL) defining the virtual table's schema. Here, the SQL is contained in the global variable DDL in Listing Four (available online; see www.ddj.com/code/).

The xDestroy() function is essentially the reverse of this xCreate() process, and is called to clean up the resources associated with the virtual table.

static int vt_create( sqlite3 *db, void *pAux, int argc, const char *const*argv,
                      sqlite3_vtab **pp_vt, char **pzErr )
{
    int rc = SQLITE_OK;
    vtab* p_vt;
    /* Allocate the sqlite3_vtab/vtab structure itself */
    p_vt = (vtab*)sqlite3_malloc(sizeof(*p_vt));

    if(p_vt == NULL) {
        return SQLITE_NOMEM;
    }
    p_vt->db = db;
    apr_pool_create(&p_vt->pool, NULL);
    /* Declare the vtable's structure */
    rc = sqlite3_declare_vtab(db, ddl);
    /* Success. Set *pp_vt and return */
    *pp_vt = &p_vt->base;
    return SQLITE_OK;
}
Listing Three

The xConnect() and xDisconnect() functions are similar to xCreate()/xDestroy() with one exception. xCreate() and xDestroy() are designed to do one-time initialization/destruction of the virtual table, while xConnect() and xDisconnect() are intended to connect/disconnect a database with an existing virtual table. The distinction only matters if you have shared resource(s) associated with the virtual table that must be available to all database connections. If you don't have any, then these functions are essentially identical.

Querying

xOpen() is called when SQLite opens a cursor on a virtual table and prepares to iterate over it. xOpen() more or less just allocates a cursor object and passes it back. Similarly, when SQLite is done iterating over the table, it uses xClose() to clean up the cursor.

All of this so far is intuitive. The query process, however, is more involved.

SQLite's query process consists of three phases: compilation, execution, and finalization. The virtual table module interface addresses all three.

In compilation (when you call sqlite3_prepare()), SQLite calls xBestIndex(). This is where you can, to a degree, tell SQLite about certain optimizations that can be made to narrow the size of the result set.

In execution, SQLite calls xFilter() to initiate the search, followed by xNext() to iterate over each row of the result set. xNext() is called as a result of calling sqlite3_step(). xColumn() provides the values of each column of the current row. xColumn() is called as a result of calling one of the sqlite3_column_xxx() functions. SQLite uses xRowid() to obtain the primary key value for any given row, and xEof() to tell whether it has reached the end of the result set.

Using Indexes

Without xBestIndex(), the query process is really just a glorified for loop that iterates over the same set of data each time. In this case, it would just be a matter of starting at the root filesystem and recursively descending into each directory until you reach the end.

In this case, however, it would be horrible performance-wise to have to search the entire filesystem every time you did a query. What if you only wanted to search your home directory? It would be a complete waste of time for the virtual table to search every other directory outside of it as part of the search. This is where xBestIndex() comes in.

In some ways, xBestIndex() may be the most important part of the virtual table implementation. It is the only place where you can really dramatically reduce the size of your search path. And it may strongly influence the rest of your implementation, such as the contents of your vtab and cursor structures. Therefore, this is the area where we want to concentrate.

xBestIndex() and xFilter() work together, implementing a specific protocol whereby a set of columns can be identified as indexes. xBestIndex() works at query compile time and identifies the columns to be used as indexes. xFilter() works at runtime and obtains the constraint values for those columns.

To start, the xBestIndex() implementation is given by vt_best_index(), whose declaration is:

static int vt_best_index(sqlite3_vtab 
                         *tab, sqlite3_index_info *p_info)

SQLite passes xBestIndex() a reference to a sqlite3_index_info structure (p_info), which contains extensive information on the compiled query. This structure is organized into input and output sections. The input is an array of sqlite3_index_constraint pointers (Listing Five, available online). The output is an array of sqlite3_index_constraint_usage pointers (Listing Six, available online).

The aConstraint and aConstraintUsage contain the same number of elements, and each of their elements corresponds to the other. That is, aConstraintUseage[i] and aConstraint[i] both refer to the same column.

Consider the query:

SELECT * from fs WHERE name=   'foo' AND path='/var/log'

The constraint name='foo' AND path='/var/log' would be represented in xBestIndex() as:

p_info->aConstraint[0].iColumn = 0
p_info->aConstraint[0].op      =    SQLITE_INDEX_CONSTRAINT_EQ

p_info->aConstraint[1].iColumn = 1
p_info->aConstraint[1].op      =    SQLITE_INDEX_CONSTRAINT_EQ

In this case, the name column is referenced in aConstraint[0]. We know it is the name column because its ordinal is 0 (given by aConstraint[0].iColumn), and according to our table schema, column ordinal 0 corresponds to name. The same follows for path. Furthermore, we are given the relational operator used in the expression as well. These operators are:

#define SQLITE_INDEX_CONSTRAINT_EQ    2
#define SQLITE_INDEX_CONSTRAINT_GT    4
#define SQLITE_INDEX_CONSTRAINT_LE    8
#define SQLITE_INDEX_CONSTRAINT_LT    16
#define SQLITE_INDEX_CONSTRAINT_GE    32
#define SQLITE_INDEX_CONSTRAINT_MATCH 64

Thus, we have the flexibility of choosing not only the column of interest, but the equality conditions under which it is being used.

Here, xBestIndex() reads through the inputs (p_info->aConstraint[]) and specifies which columns it wants to use in the output (p_info->aConstraintUsage[]). To use both columns as indexes in xFilter(), you would do this in xBestIndex():

p_info->aConstraintUsage[0] = 1
p_info->aConstraintUsage[1] = 2

The values assigned to the aConstraintUsage[] elements are significant. They specify the order in which they are passed to xFilter(). In the example, this says "pass xFilter() the name column first, then the path column."

To understand how this works, you need to know a little about xFilter(). The declaration of xFilter() is as follows:

  static int vt_filter     ( sqlite3_vtab_cursor *p_vtc,
int idxNum, const char *idxSint    argc, sqlite3_value **argv );

The values from xBestIndex() are passed via the argc and argv arguments. argc contains the size of argv, and argv values themselves. The order of the values in argv follows the order specified in p_info->aConstraintUsage in xBestIndex(). So, in our example above, argc will be 2 and argv will be as follows:

argv[0] = 'foo'
argv[1] = '/var/log'

Now that xFilter() has this information, its job is to set up the cursor object so it can iterate through a specific set of data. In this case, we know that since path='/var/log', we will be limiting our search to just that directory (and not searching the whole filesystem). From that point forward, the cursor basically holds the state and iterates through all the files and directories in /var/log. The implementation is straightforward—it's just a standard recursive directory search using the APR library.

The match() Function

Here's where things get tricky. Consider the query:

SELECT * FROM fs WHERE    path='/var/log' OR      path='/usr/lib';


What happens here? Well, you might think that you simply intercept the path column in xBestIndex() and pass it on to xFilter(), but as it turns out SQLite never calls xBestIndex() here.

Why? Because xBestIndex() is subject to SQLite's index conditions just like any other query. There are times when SQLite will use indexes, and times when it will use sequential scans. When you use OR for multiple constraints on a given column, SQLite uses a sequential scan. That puts us right back into the situation where we have to search the whole filesystem again, instead of just two directories.

Fortunately, there is a way around this—the match() function. If you notice , one of the defined relational operators is SQLITE_INDEX_CONSTRAINT_MATCH. So for example, if we recast the aforementioned query to

SELECT * from fs WHERE path    match('/var/log', '/usr/lib');

then SQLite calls xBestIndex() with the path column, and specifies that the SQLITE_INDEX_CONSTRAINT_MATCH operator was used. This is our solution.

To do this, however, you must register a function to handle the match() SQL function. By default it is unimplemented and will trigger an error if you try to use it. To register it, we use the xFindFunction() callback, which we implement as vt_find_function() (Listing Seven, also available online).

When a SQL function uses a column from a virtual table, SQLite calls xFindFunction() to give the virtual table an opportunity to overload the function. The first three parameters are inputs: the virtual table, the number of arguments to the function, and the name of the function. To overload the function, xFindFunction() passes a function pointer back via *pxFunc (and any user data via *ppArg) and returns 1. If it doesn't want to overload it, then xFindFunction() simply returns 0.

In this case, you just want SQLite to see match() as a valid function so it will use xBestIndex(). You don't really care what match() does. In fact, our implementation of match always returns true (meaning everything matches no matter what). What matters here is that you get the values of match() into xFilter() so you can narrow your search path. So what you look for in xBestIndex() is any column whose ordinal is 1 (p_info->aConstraint[x].iColumn == 1) and whose relational operators are equality (SQLITE_INDEX_CONSTRAINT_EQ) or match (SQLITE_INDEX_CONSTRAINT_MATCH). If you see that, then you pass that column on to xFilter().

So xFilter() simply looks for a string containing one or more paths in argv. In the example, argc is 1 and argv will be:

argv[0] = "'/var/log','/usr/lib'"

It is your responsibility to interpret the argument passed to match(). Thus, you have to parse the string looking for paths. In this implementation, I use the convention that paths are separated by commas. I parse everything between commas and build a list of directories to search. This is then stored in the cursor structure. The search works just as before, except instead of recursively searching one directory, I search multiple directories. The search logic is the same, I just repeat it for every directory passed into match().

Again, for each row in the result set, SQLite calls xColumn() to get at the values for each row in the result set. It passes xColumn() the ordinal of the column whose value is to return. To fulfill the request, you just implement a switch statement covering all ordinals in our virtual table, passing back the appropriate value for each column. This works similar to SQLite's user-defined function interface.

This then is the basic workings of an optimized virtual table. The full implementation is given in the file fs.c (available online; see www.ddj.com/code/). Additionally, there is a stripped down, bare-bones virtual table that does nothing in the file example.c.

Conclusion

While powerful in themselves, virtual tables are the foundation of some of SQLite's larger features, such as full text search (FTS). Even more powerful is the idea that you can join virtual tables like any other tables, thus cross referencing disparate information. Also, you can use virtual tables as a way to aggregate information. You could, for example, use the filesystem table to generate a reference list of all files in the filesystem, and then issue queries each day to scan for changes. The possibilities abound. With virtual tables, the world is your database.

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.