Hash Index¶

This index is based on Hash Table with separate chaining. You can refer also for ISAM.

• Pros

  • Fast

• Cons

  • Records are not in order of insert / update / delete but in random like
  • Can be queried only for given key, or iterate over all keys

There are two major implementations

• UniqueHashIndex - should be used only for id index
• HashIndex - a general use Hash Index.

They differs in several places, for details you should read the code of them both.

conflict resolution

When using 0xfffff hash_lim after 1200 inserts there is 50% probability that conflict will occur (birthday problem). Conflicts are solved by separate chaining, so keys with the same hash function results are linked into list, then traversed when needed.

duplicate keys

For duplicate keys the same mechanism is used as for conflict resolution. All indexes different than id one can accept more than one record with the same key (get_many()).

class AIndex(HashIndex):

    def __init__(self, *args, **kwargs):
        kwargs['key_format'] = '?'
        kwargs['hash_lim'] = 2
        super(AIndex, self).__init__(*args, **kwargs)

    def make_key_value(self, data):
        val = data.get('a')
        if val is none:
            return None
        return val % 2, None

    def make_key(self, key):
        return key

[...]
number_of_zeros = db.count(db.get_many, 'a', 0)
number_of_ones = db.count(db.get_many, 'a', 1)
[...]

B Plus Tree Index¶

This index is based on B Plus Tree. Duplicate keys are stored inside Tree structure (on leafs/nodes).

• Pros

  • Can be queried for range queries
  • Records are in order (depends of your keys)

• Cons

  • Slower than Hash based indexes

duplicate keys

Duplicate keys are stored inside tree structure. So in worst case when you have more duplicate keys than node_size tree will became sub-optimal (a half of one node will be always empty)

class SimpleTreeIndex(TreeBasedIndex):

    def __init__(self, *args, **kwargs):
        kwargs['node_capacity'] = 13
        kwargs['key_format'] = 'I'
        super(SimpleTreeIndex, self).__init__(*args, **kwargs)

    def make_key_value(self, data):
        a_val = data.get('a')
        if a_val is not None:
            return a_val, None
        return None

    def make_key(self, key):
        return key

[...]
from_3_to_10 = db.get_many('tree', limit=-1, start=3, end=10, inclusive_start=True, inclusive_end=True)
[...]

Multikeys index¶

Multikeys indexes (aka Multiindex) are indexes where you can have more than one key per database data. They share the same properties as their bases (Hash Index and B Plus Tree Index).

Imagine something like infix search:

class TreeMultiTest(MultiTreeBasedIndex):

    custom_header = """from CodernityDB.tree_index import MultiTreeBasedIndex
from itertools import izip"""

    def __init__(self, *args, **kwargs):
        kwargs['key_format'] = '16s'
        super(TreeMultiTest, self).__init__(*args, **kwargs)
        self.__l = kwargs.get('w_len', 2)

    def make_key_value(self, data):
        name = data['w']
        l = self.__l
        max_l = len(name)
        out = set()
        for x in xrange(l - 1, max_l):
            m = (name, )
            for y in xrange(0, x):
                m += (name[y + 1:],)
            out.update(set(''.join(x).rjust(16, '_').lower() for x in izip(*m)))  #ignore import error
        return out, dict(w=name)

    def make_key(self, key):
        return key.rjust(16, '_').lower()

By using that index you will be able to perform infix search over all words in your database. Only one difference from non multi index is that make_key_value has to return iterable (the best will be set because it has unique values). Then you can easily run something like that:

db = Database('/tmp/multi')
db.create()
db.add_index(TreeMultiTest(db.path, "words"))

db.insert(dict(w='Codernity'))

print db.get('words', 'dern')['w']  # "Codernity"
print db.get('words', 'cod')['w']  # "Codernity"

As you can see implementing infix/suffix/prefix search mechanism in CodernityDB is very easy.

Obviously that’s not only one use case for that indexes, it’s just probably the most obvious usage example.

Currently both Hash and Tree indexes have multiindex implementations: MultiHashIndex and MultiTreeBasedIndex (yes they are just prefixed by word Multi).

Index functions¶

Quite important thing in CodernityDB are index functions. You can do with them anything you want they have access to database object, so they can perform operations on multiple indexes. If you want join like operation, you should write function. Then you will be able to run that function database side when using CodernityDB-HTTP. The only mandatory argument for that kind of function is db, the rest are function arguments.

Writing function is easy see an example there:

def run_timeline(self, db, user, limit):
    u = db.get('user', user)
    it = db.get_many(self.name, user, end=10 ** 11, limit=limit, with_doc=True)
    for curr in it:
        curr['username'] = user
        curr['email'] = u['email']
        curr['pub_date'] = curr['doc']['pub_date']
        curr['text'] = curr['doc']['text']
        del curr['doc']
        yield curr

That function performs simple JOIN operation (that JOIN known from SQL databases). As you can see it’s exactly the same as you would code in your code to archive that.

Function should start it’s name from run_ then you can call it:

gen = db.run("index", "timeline", "user_a", 10)

As mentioned before, while you work in embedded mode it makes no big difference, but when using CodernityDB-HTTP it makes huge.

Easier way of creating indexes¶

Do I really need to code indexes in Python, is there an easier way to create indexes?

You bet there is! We prepared special, simplified mode for creating indexes. That code will be translated to Python code, and then used exactly in the same way as the rest indexes (so that simple indexes are exactly the same fast as pure Python ones). They are just simple by name not by possibilities.

Usage of this mode is really basic, you just need to provide 2 (or optionally 3) things:

• properties of the index like this:

name = MyTestIndex
type = HashIndex
key_format = I
etc. etc. ...

• body for make_key_value containing our simplified syntax:

make_key_value:
a > 1: 1, None
a, None

• and optionally body for make_key (if you don’t provide it, it will be generated automatically and set to return key value as it is):

make_key:
key > 1: 1
key

Syntax of function body is really basic, every line preceded by a statement with colon at the end means that if conditions before colon are met, function will return everything that follows colon. If there is no colon, value will be always returned. Of course the order of lines actually matters, so if you provide body like that:

a > 1: 1, None
a > 2: 2, None

The second value will be never returned (because if a is less then 1 it’s for sure less than 2). Every name will be look for in dictionaries given to functions, so body like:

a > 1: a, None

will generate python code like that:

if data["a"] > 1:
    return data["a"], None

That’s everything you need to know to work with our simplified index creator, you just need to always provide name and type in index properties and provide body for make_key_value, which has to return always two values (the 2nd has to be a dictionary or None). Here you have some examples and their equivalents in python. Remember that this simplified creator doesn’t provide python power, so if you want to write more sophisticated index, you will have to learn python.

name = Test
type = HashIndex
key_format = 16s

make_key_value:
md5(a),None

make_key:
md5(key)

is an equivalent to:

class Test( HashIndex ):
    def __init__(self,*args,**kwargs):
        kwargs["key_format"] = '16s'
        super( Test ,self).__init__(*args,**kwargs)
    def make_key_value(self,data):
        return md5 ( data["a"] ) .digest() , None
    def make_key(self,key):
        return md5 ( key ) .digest()

Tables, collections...?¶

OK, I got it, but can I store more than one data type in Database. Is there something like table or collection ?

Sure! You can use Index mechanism do to it. As it has been mentioned before, Index mechanism in CodernityDB is like read only Table in SQL databases (see index design). So all you need is to define how your records will differ each other.

Let’s assume that you want to users and users and some data that belongs to user. You will probably want to be able to get all users, and all things that belongs to him, right? So.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class AllUsers(HashIndex):

    def __init__(self, *args, **kwargs):
        kwargs['key_format'] = '16s'
        super(AllUsers, self).__init__(*args, **kwargs)

    def make_key(self, key):
        return md5(key).digest()

    def make_key_value(self, data):
        if data.get('_t') == 'user':
            return md5(data.get('name')).digest(), None


class AllItems(HashIndex):

    def __init__(self, *args, **kwargs):
        kwargs['key_format'] = '16s'
        super(AllItems, self).__init__(*args, **kwargs)

    def make_key(self, key):
        return md5(key).digest()

    def make_key_value(self, data):
        if data.get('_t') == 'item':
            return md5(data.get('owner')).digest(), None

Having that indexes in your database will allow you to query for single user and for items of that user. Isn’t it simple? As you can see, index in CodernityDB is not an index that you probably get used to. It’s much more.

How an index code is processed by CodernityDB?¶

When you provide CodernityDB with an index, it uses getsource function from inspect module to get index code. This means, that after you call add_index function, it will look for the index class in current scope, take the whole class code as it is (including intends) and place it inside it’s own code. Hence there are few cons you have to bear in mind:

• You can not generate class code on the fly inside, let’s say, a function, like that:

def create_index(self,a):
    class MyIndex(HashIndex):
        def __init__(self, *args, **kwargs):
            kwargs['key_format'] = 'I'
            super(MyIndex, self).__init__(*args, **kwargs)
        def make_key_value(self,data):
            if data['a'] == a:
                return data['b'], None
        def make_key(self,key):
            return key
    return MyIndex

Despite of code being correct in python terms, it will produce an error in CodernityDB, since class isn’t defined in proper scope.

• You can not provide index class code with a variable defined outside this class:

a = 5
class MyIndex(HashIndex):
    def __init__(self, *args, **kwargs):
        kwargs['key_format'] = 'I'
        super(MyIndex, self).__init__(*args, **kwargs)
    def make_key_value(self,data):
        if data['a'] == a:
            return data['b'], None
    def make_key(self,key):
            return key

Even if now class is in proper scope, the example won’t work, because variable a isn’t known to CodernityDB.

Sharding in indexes¶

For advanced users we have sharded indexes.

All you need to do if you want to use Sharded indexes is just:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

from CodernityDB.database import Database
from CodernityDB.sharded_hash import ShardedUniqueHashIndex, ShardedHashIndex
from CodernityDB.hash_index import HashIndex

import random


class CustomIdSharded(ShardedUniqueHashIndex):

    custom_header = 'from CodernityDB.sharded_hash import ShardedUniqueHashIndex'

    def __init__(self, *args, **kwargs):
        kwargs['sh_nums'] = 10
        super(CustomIdSharded, self).__init__(*args, **kwargs)


class MySharded(ShardedHashIndex):

    custom_header = 'from CodernityDB.sharded_hash import ShardedHashIndex'

    def __init__(self, *args, **kwargs):
        kwargs['sh_nums'] = 10
        kwargs['key_format'] = 'I'
        kwargs['use_make_keys'] = True
        super(MySharded, self).__init__(*args, **kwargs)

    def make_key_value(self, data):
        return data['x'], None

    def calculate_shard(self, key):
        return key % self.sh_nums


y = 1500 * 'y'

db = Database('/tmp/shard')

db.create(with_id_index=False)
db.add_index(CustomIdSharded(db.path, 'id'))
db.add_index(MySharded(db.path, 'x'))


# it makes non sense to use sharding with such small number of records
for x in xrange(10 ** 4):
    db.insert({'x': x, 'y': y})


print db.get('x', random.randint(0, 10 ** 4))['_id']

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#!/usr/bin/env python

from CodernityDB.database import Database

from CodernityDB.sharded_hash import ShardedUniqueHashIndex, ShardedHashIndex

import shutil
import sys
import time

try:
    shutil.rmtree('/tmp/shard')
except:
    pass

NUM = int(sys.argv[1])

db = Database('/tmp/shard')

if sys.argv[2] == 'sh':
    class MyShard(ShardedUniqueHashIndex):
        custom_header = 'from CodernityDB.sharded_hash import ShardedUniqueHashIndex'

        def __init__(self, *args, **kwargs):
            kwargs['sh_nums'] = 10
            super(MyShard, self).__init__(*args, **kwargs)

    db.create(with_id_index=False)
    db.add_index(MyShard(db.path, 'id'))
else:
    db.create()


st = time.time()

for x in xrange(NUM):
    db.insert({'x': 1})

end = time.time()

print end - st