Building an embedded column store database with upscaledb - part 3 by Christoph Rupp

Posted on Feb 10, 20:12:32 CET 2016

---

In the first part of this series I have described the ideas behind "row oriented" and "column oriented" databases. The second part went into more depth. This part will introduce some code and implement the user database from part 1 of this blog series.

Implementing a user database

Imagine a web application where users can register; each user has a unique id, a name, a password and an email address. In addition we will store the birthday. This will be our scenario for this chapter.

We also need to specify the indexes. We want to have fast lookups by user id, obviously; also we will add indexes for the email address and a compound index of birthday and username.

Creating indexes

In upscaledb an index is actually called a "Database", and all Databases are stored in an "Environment". First step is therefore to create such an Environment.

The code samples here are written in C++ using the C API. upscaledb supports other APIs as well (Java, Python, .NET, Erlang...). All those APIs are modelled closely after the C API and their use is very similar. If there are problems or questions then just add a comment to this blog or send me an email.

The following code creates an Environment. I enabled Transactions in order to roll back insertions in case of an error.

static ups_env_t *
create_environment()
{
  ups_env_t *env;
  ups_status_t st = ups_env_create(&env, "tutorial.db",
                  UPS_ENABLE_TRANSACTIONS, 0664, 0);
  if (st != UPS_SUCCESS)
    handle_error("ups_env_create", st);
  return env;
}

As you can see, no surprises here. The Environment is created with the default settings (no flags or extra parameters) and is stored in a file called "tutorial.db" in the current working directory. See the API reference for more options, i.e. to enable transactions, recovery, increase the cache size or to run purely in memory.

Next we need a Database with the primary key (the user id) as the index, and the full row as the record. Our C structures would look like this:

struct UserInformation {
  char username[64];
  char password[64];
  char email[64];
  uint32 day_of_birth; // time_t: seconds since 1.1.1970
};

As mentioned in part 2 you should store the data as compact as possible. Here I am completely failing to follow my own advice: fixed length arrays are wasteful. A more efficient solution would be to use variable-length strings or zero-terminated C strings (const char *) which are then serialized into a byte array. For sake of brevity I have used the less efficient, but simpler representation.

One thing to keep in mind is that C and C++ compilers often add padding to the structures. When serializing a structure to disk then padding should be disabled. Check your compiler documentation how to do this.

Let's finally create a Database with the unique user id as a primary key. We use a 32bit "Record number" Database which automatically assigns the primary key, just like MySQL's AUTO_INCREMENT column. upscaledb identifies each Database with a numerical id (here: "1").

static ups_db_t *
create_primary_database(ups_env_t *env)
{
  ups_db_t *db;
  ups_status_t st = ups_env_create_db(env, &db, 1, UPS_RECORD_NUMBER32, 0);
  if (st != UPS_SUCCESS)
    handle_error("ups_env_create_db", st);
  return db;
}

Now we're done with the boilerplate code and we can finally insert a new record:

UserInformation ui = {0};
::strncpy(ui.username, username, sizeof(ui.username));
::strncpy(ui.password, password, sizeof(ui.password));
::strncpy(ui.email, email, sizeof(ui.email));
ui.day_of_birth = day_of_birth;

/* ommitted transaction-handling code for clarity */

ups_key_t key = {0};
ups_record_t record = ups_make_record(&ui, sizeof(ui));
st = ups_db_insert(db_primary, 0, &key, &record, 0);
if (st != UPS_SUCCESS) {
  ups_txn_abort(txn, 0);
  handle_error("ups_db_insert (primary)", st);
}

The use of ::strncpy() is unsafe because it might not write the terminating zero byte at the end of the buffer if the allowed size is overwritten. I have avoided all necessary sanity checks to keep the code snippets short.

So what's the user id of the new record? It can now be retrieved from the key structure:

uint32_t user_id = *(uint32_t *)key.data;

Voila, the first record is inserted. If we move all that code into a single function which returns the user id then we have successfully replaced an SQL statement like INSERT INTO users VALUES ('tom', 's3cr3t', 'batman@host.com')

It is important to always close the handles before the program is terminated; the corresponding calls are ups_db_close and ups_env_close Note that the C API has a flag UPS_AUTO_CLEANUP which automatically closes all open Databases, Cursors and other resources that are part of this Environment. Other APIs (Erlang, Python) do not have this flag and you need to close all resources manually.

st = ups_env_close(env, UPS_AUTO_CLEANUP);
if (st != UPS_SUCCESS)
  handle_error(st);

Creating unique indexes

We want to create an additional index for the username field. In SQL databases we would define this index as "unique", because each username should only exist once. In upscaledb, uniqueness is verified when inserting the value in a Database (with ups_db_insert as demonstrated above). By default, the insert operation will fail if the key already exist, which is exactly the behaviour that we require.

This Database will store the primary key as records; since the primary key is a 32bit number we can therefore set the record size to 4 (4 bytes = 32 bit).

static ups_db_t *
create_username_index(ups_env_t *env)
{
  ups_db_t *db;
  ups_parameter_t parameters[] = {
    {UPS_PARAM_KEY_SIZE, 64},
    {UPS_PARAM_RECORD_SIZE, 4},
    {0, 0}
  };
  ups_status_t st = ups_env_create_db(env, &db, 2, 0, &parameters[0]);
  if (st != UPS_SUCCESS)
    handle_error("ups_env_create_db", st);
  return db;
}

We can now use this Database to verify that a username is unique by performing a simple lookup:

static bool
is_username_unique(const char *username)
{
  char keyname[64] = {0};
  ::strncpy(keyname, username, sizeof(keyname));

  ups_key_t key = ups_make_key(keyname, sizeof(keyname));
  ups_record_t record = {0};
  ups_status_t st = ups_db_find(dbi_username, 0, &key, &record, 0);
  if (st == UPS_SUCCESS)
    return false;
  if (st != UPS_KEY_NOT_FOUND)
    handle_error("ups_db_find", st);
  return true;
}

Whenever a new user signs up, this index has to be updated. This is handled by the following code:

ups_key_t kusername = ups_make_key(ui.username, sizeof(ui.username));
ups_record_t rusername = ups_make_record(&user_id, sizeof(user_id));
st = ups_db_insert(dbi_username, 0, &kusername, &rusername, 0);
if (st != UPS_SUCCESS) {
  ups_txn_abort(txn, 0);
  handle_error("ups_db_insert (username index)", st);
}

Creating numeric indexes

Our webpage should reward users which log in on their birthday (or maybe some parts of the webpage are restricted for minors?) and an index is required to get a list of users sorted by birthday.

The upscaledb database for this index therefore stores the birth date (with 32bit keys), and again it has the 4 byte primary key as record. Also we need to allow duplicate keys here, because several users could be born on the same day. The flag UPS_ENABLE_DUPLICATES will do the trick.

static ups_db_t *
create_dayofbirth_index(ups_env_t *env)
{
  ups_db_t *db;
  ups_parameter_t parameters[] = {
    {UPS_PARAM_KEY_TYPE, UPS_TYPE_UINT32},
    {UPS_PARAM_RECORD_SIZE, 4},
    {0, 0}
  };
  ups_status_t st = ups_env_create_db(env, &db, 3, UPS_ENABLE_DUPLICATES,
                  &parameters[0]);
  if (st != UPS_SUCCESS)
    handle_error("ups_env_create_db", st);
  return db;
}

Inserting values into this database is analog to the previous insert statements, just with a difference: the call will never fail if the key already exists, because duplicate keys are now allowed.

Creating compound indexes

After a few months our database grows and grows, and for additional functionality we want to run queries that retrieve an alphabetical list of user names grouped by their birthday. In other words: retrieve all users whose birthday is on 10.10.1977, and sort the result alphabetically.

Such a query can be implemented with nested loops. We could use our "day of birth" index to retrieve all user ids whose birthday is on 10.10.1977. Then we could retrieve the names of those users and sort the list. This would work fine, but it might become a bottleneck if the number of users keeps growing.

A much better solution would be to create a compound index, one which combines several attributes. In our case we combine the username and the birthday.

Such a compound index is possible with upscaledb, but unlike the previous indexes we now have to provide additional information regarding the sort order. For custom sort orders a new key type UPS_TYPE_CUSTOM and a compare function must be specified. Since our key size is always static, we also specify the key size.

This structure will be used for the keys (again take care of padding issues, as mentioned earlier):

struct CompoundIndex {
  uint32 day_of_birth; // time_t: seconds since 1.1.1970
  char username[64];
};

If we would store the 32bit user id instead of the user name, our key size would shrink dramatically. But we would lose the ability to retrieve the user names in alphabetically sorted order, which was our requirement (see above).

A callback function will sort the CompoundIndex structures first by day_of_birth, then alphabetically by username. It returns -1 if the first element (lhs - "left hand side") is smaller, or +1 if it's larger than the second element (rhs - "right hand side"), and 0 if both are equal:

static int
compare_compound_index(ups_db_t *db,
                const uint8_t *lhs_data, uint32_t lhs_size,
                const uint8_t *rhs_data, uint32_t rhs_size)
{
  assert(lhs_size == sizeof(CompoundIndex));
  assert(rhs_size == sizeof(CompoundIndex));
  const CompoundIndex *lhs = (const CompoundIndex *)lhs_data;
  const CompoundIndex *rhs = (const CompoundIndex *)rhs_data;
  if (lhs->day_of_birth < rhs->day_of_birth)
    return -1;
  if (lhs->day_of_birth > rhs->day_of_birth)
    return +1;
  // both are equal - compare usernames
  return ::strncmp(lhs->username, rhs->username, sizeof(lhs->username));
}

static ups_db_t *
create_compound_index(ups_env_t *env)
{
  ups_db_t *db;
  ups_parameter_t parameters[] = {
    {UPS_PARAM_KEY_TYPE, UPS_TYPE_CUSTOM},
    {UPS_PARAM_KEY_SIZE, sizeof(CompoundIndex)},
    {UPS_PARAM_CUSTOM_COMPARE_NAME, (uint64_t)"CompoundIndex-compare"},
    {UPS_PARAM_RECORD_SIZE, 4},
    {0, 0}
  };

  /* register the compare function */
  ups_status_t st = ups_register_compare("CompoundIndex-compare",
                  compare_compound_index);
  if (st != UPS_SUCCESS)
    handle_error("ups_register_compare", st);

  st = ups_env_create_db(env, &db, 4, 0, &parameters[0]);
  if (st != UPS_SUCCESS)
    handle_error("ups_env_create_db", st);
  return db;
}

Inserting and looking up values is nearly identical to the code for the other indexes, but the CompoundStructure key must be initialized properly. In the next part we will then see how to perform range queries on those indexes.

Download the code.

---