Indexes and Cursors in C

As explained in the Indexes and Cursors page, eXtremeDB supports a variety of index types. The following sections give C API implementation details for managing each of these index types: B-Tree, Patricia, R-Tree, KD-Tree, HNSW, Hash, OID, Autoid, User-defined.

An eXtremeDB class cannot be accessed without an index, so a class must have at least one index. If no index is explicitly defined, and the class has no dynamic-size fields (such as strings, vectors, optional structs, etc.), then a list index will be created for this class using the fixedrec allocator. Via the fixedrec allocator, the location of all the database object instances is well known, which permits access to these objects through a chain of objects instead of a B-tree for this list index implementation. This index implementation has a minimal performance cost compared to a normal B-tree index.

However, note that the implicit creation of a list index happens only for classes with fixed size. If the class contains one or more dynamic fields, the fixedrec allocator cannot be used to generate the "chain of objects". So when dynamic field(s) are present, the application must explicitly define a list or some other type of index.

C-Specific Features

C applications can optimize B-Tree index performance using the inclusive declaration. (Please refer to the Optimizing Tree Indexes section below.)

Another additional feature available to C applications is the ability to use the voluntary qualifier in schema definitions for an index to indicate that the index can be created or dropped at runtime. In other words, voluntary indexes are not built until the application explicitly calls the generated function <classname_indexname>_create(). In the same fashion, the application can remove a voluntary index by calling the generated function <classname_indexname>_drop().

Also, the eXtremeDB specialized Object ID (oid) index is possible in C applications. (Please refer to the OID Indexes section below.)

Another significant feature available for C developers is the ability to define custom indexes. (Please refer to the User-defined Indexes section below.)

Persistent Databases

For persistent databases there are optimization features that pertain particularly to B-Tree indexes. Please refer to the Persistent Database Index Optimization in C page for further details.

B-Tree Indexes

As explained in the B-Tree Indexes page, tree indexes can be used for ordered (sorted) retrieval, range retrieval and pattern matching. A B-Tree index is specified in the schema file with the tree declaration and optional modifiers unique or nonunique. If no modifier is specified, the default is nonunique.

For example:

    class anObject
    {
        uint4 value;

        tree<value> Idx;
    };

The mcocomp schema compiler generates cursor functions and search functions for tree indexes.

To obtain a cursor for a tree index:

    MCO_RET classname_indexname_index_cursor(/*IN*/ mco_trans_h t, /*OUT*/ mco_cursor_h c);

The _search() functions generated for all tree indexes are of the following form:

    MCO_RET classname_indexname_search(
                    /*IN*/ mco_trans_h trans,
                    /*INOUT*/ mco_cursor_h cursor,
                    /*IN*/ MCO_OPCODE op,
                    /*IN*/ [const] <type> [*]param1,
                    [[/*IN*/ uint2 len1,]
                    [/*IN*/ [const] <type> [*]param2,
                    [/*IN*/ uint2 len2,] …]);

Here MCO_OPCODE represents a compare operation as defined in cursor operator codes.

To obtain the object handle from the current cursor position:

    MCO_RET classname_from_cursor(
                    /*IN*/ mco_trans_h t,
                    /*IN*/ mco_cursor_h c,
                    /*OUT*/ classname *object);

Note that the cursor must be properly initialized with a cursor positioning function (see the following section) to retrieve a valid database object handle.

The _locate() function is used to position a tree index cursor based on an object reference. The cursor must have been previously instantiated using the _index_cursor() function. (Note that the _locate() function applies only to tree-based cursors, not to list or hash cursors):

    MCO_RET classname_indexname_locate(
                    /*IN*/ mco_trans_h t,
                    /*INOUT*/ mco_cursor_h c,
                    /*IN*/ classname *handle);

Cursors and Searches

The standard cursor positioning functions mco_cursor_first(), mco_cursor_last(), mco_cursor_next() and mco_cursor_prev() are used to initialize the cursor to the first or last and iterate through the result sets of searches.

Searches are performed using the generated _search() function. Please refer to the Searches page for implementation details. Also, as explained in the Searches page, tree indexes can be used for pattern matching, range retrieval and ordered (sorted) retrieval.

Optimizing Tree Indexes

Normally, the B-Tree implementation doesn't store key values in the index. However, for in-memory databases, sometimes it is beneficial to keep the key value on the index pages.

As explained in the Inclusive and Covering Indexes page, B-Tree index performance can be optimized by declaring the index inclusive.

A "key-value-inclusive" index for a class is defined in a C API schema through the inclusive keyword, for example:

    class Tab
    {
        string name;
        int4   code;
        string body;

        inclusive tree<name,code> pk;
    };

If it is desired to make all B-Tree indexes for transient classes "key-value-inclusive", the MCO_DB_INCLUSIVE_BTREE option can be specified in the db_params argument to C API mco_db_open_dev(), for example:

    MCO_RET            rc;
    mco_db_h           db = 0;
    mco_device_t       dev[N_DEVICES];
    mco_db_params_t    db_params;
    ...
    db_params.mode_mask |= MCO_DB_INCLUSIVE_BTREE;
    ...
    rc = mco_db_open_dev(db_name, mydb_get_dictionary(), dev, N_DEVICES, &db_params);

In addition, a "covering" index (which contains all of the fields of interest in a class) can be also declared inclusive to leverage CPU cache usage, for example:

    class Tab
    {
        string name;
        int4   code;
        string body;

        inclusive tree<*> pk;
    };

(Note that a "key-value-inclusive" or "covering" index can only be a B-Tree index, so the inclusive declaration can only precede the tree keyword.)

Patricia Trie Indexes

As explained in the Patricia Indexes page, the eXtremeDBpatricia index is particularly useful for network and telecommunications applications. A patricia index can be declared over scalar and boolean data types as well as arrays and vectors of those types. In fact, the boolean data type allows bit arrays to be used to store IP addresses. A patricia index can also be declared unique; in the absence of the unique keyword it defaults to allowing duplicates. Unlike other eXtremeDB indexes, the patricia index cannot be compound; it is always declared for a single field.

The following schema illustrates some possible declarations:

    class xyz
    {
        boolean         b1[32];
        vector<boolean> b2;
        uint4           b3;
        char<10>        b4[10];
        vector<string>  b5;

        patricia <b1>   Ib1;
        patricia <b2>   Ib2;
        patricia <b3>   Ib3;
        patricia <b4>   Ib4;
        patricia <b5>   Ib5;
        unique patricia <b1>  Ib1U;
        unique patricia <b2>  Ib2U;
        unique patricia <b3>  Ib3U;
        unique patricia <b4>  Ib4U;
        unique patricia <b5>  Ib5U;
    }

Note that boolean fields b1, b2 are used as bit arrays for patricia indexes Ib1U and Ib2U. The boolean data type is treated in a special way by the mcocomp schema compiler and requires some explanation in the following section. Also, in addition to the standard tree index generated functions, the following section discusses functions that are generated for each patricia index.

Boolean Data Type

The boolean data type can be used to define a single bit field, a fixed size array of bits, or a variable length array of bits. The only index type possible for the boolean data type is the patricia index. A single-bit field cannot be indexed, nor is it advisable to index a short array of bits.

For example:

    class xyz
    {
        boolean b1;         // a bit field
        boolean b2[32];     // fixed-size array of 32 bits

        vector<boolean> b3; // variable-length bit array
    };

For C applications, the following functions are generated for fields of type boolean:

    classname_fieldname_get(classname *handle, /*OUT*/ uint1 *result);
    classname_fieldname_put(classname *handle, uint1 value);

For a fixed-size bit array the following interfaces are also generated:

    // Reads the specified bit out of the array.
    // Note: It's OK to read one bit, but in order
    // to read several bits it's better to read the
    // entire array and mask it.
    classname_fieldname_at(classname* handle, uint2 index, /*OUT*/ uint1 *result);

    // Read range of bits.
    // Note: the start_index bit number must be a power of 8
    classname_fieldname_get_range(classname* handle, uint2 start_index, uint2 num,
                        /*OUT*/ uint1 *dest);

    // Again, the bit-by-bit _put is not the most effective
    // way of writing the array. Better to mask the entire
    // array and use _put_range
    classname_fieldname_put(classname* handle, uint2 index, uint1 value);

    // Write range of bits.
    // Note: the start_index bit number must be a power of 8
    classname_fieldname_put_range(classname* handle, uint2 start_index,
                        uint2 num, const uint1 *src);

    // Read the entire field
    classname_fieldname_get(classname *handle, /*OUT*/ uint1 *result);

For variable-size arrays (vectors), the following interfaces are also generated:

    // Vector size (in bits)
    classname_fieldname_size(classname* handle, /*OUT*/ uint2 *result);

    // Allocate a vector (size in bits)
    classname_fieldname_alloc(classname* handle, uint2 size);

    // Read an element at a specified position
    classname_fieldname_at(classname* handle, uint2 index,
                        /*OUT*/ uint1 *result);

    // Read range of bits.
    // Note: the start_index bit number must be a power of 8
    classname_fieldname_get_range(classname* handle, uint2 start_index,
                        uint2 num, /*OUT*/ uint1 *dest);

    // Write range of bits.
    // Note: the start_index bit number must be a power of 8
    classname_fieldname_put_range(classname* handle, uint2 start_index,
                        uint2 num, const uint1 *src);

    // Write an element (not very efficient)
    classname_fieldname_put(classname* handle, uint2 index, uint1 value);

Generated Functions for Patricia Indexes

The generated functions applicable only to patricia indexes are _longest_match(), _exact_match(), _prefix_match() and _next_match(). These will have slightly different forms depending on the type of field being indexed.

A patricia index created over a scalar field will cause the following functions to be generated:

    classname_indexname_next_match(mco_trans_h t, /*INOUT*/ mco_cursor_h c,
                        type mask, int number_of_bits);

    classname_indexname_prefix_match(mco_trans_h t, /*INOUT*/ mco_cursor_h c,
                        type mask, int number_of_bits);

    classname_indexname_longest_match(mco_trans_h t, /*INOUT*/ mco_cursor_h c,
                        type mask, int number_of_bits);

    classname_indexname_exact_match(mco_trans_h t, /*INOUT*/ mco_cursor_h c,
                        type mask, int number_of_bits);

The type argument is the scalar type (for example uint4) and mask is the key value to match. If the indexed field is a fixed-length array or a vector of scalars these functions will be of the form:

    classname_indexname_next_match(mco_trans_h t, /*INOUT*/ mco_cursor_h c,
                        type *mask, int number_of_bits);

    classname_indexname_prefix_match(mco_trans_h t, /*INOUT*/ mco_cursor_h c,
                        type *mask, int number_of_bits);

    classname_indexname_longest_match(mco_trans_h t, /*INOUT*/ mco_cursor_h c,
                        type *mask, int number_of_bits);

    classname_indexname_exact_match(mco_trans_h t, /*INOUT*/ mco_cursor_h c,
                        type *mask, int number_of_bits);

Here type is the type of each element of the array or vector (for example uint4) and mask is the key value to match. If the indexed field is an array of boolean these functions will be of the form:

    classname_indexname_next_match(mco_trans_h t, /*INOUT*/ mco_cursor_h c,
                        char* mask, int number_of_bits);

    classname_indexname_prefix_match(mco_trans_h t, /*INOUT*/ mco_cursor_h c,
                        char* mask, int number_of_bits);

    classname_indexname_longest_match(mco_trans_h t, /*INOUT*/ mco_cursor_h c,
                        char* mask, int number_of_bits);

    classname_indexname_exact_match(mco_trans_h t, /*INOUT*/ mco_cursor_h c,
                        char* mask, int number_of_bits);

Here mask is a key value that is a packed bit array (each byte contains 8 bits).

Cursors and Searches

The standard cursor positioning functions mco_cursor_first(), mco_cursor_last(), mco_cursor_next() and mco_cursor_prev() are used to iterate through the result sets of patricia index searches. But instead of a _search() function, searches are performed using one of the generated _match() functions. Initially a cursor's position is not defined and needs to be set with a lookup or a call of mco_cursor_first() or mco_cursor_last().

Please refer to the Searches page for implementation details.

R-Tree Indexes

As explained in the R-Tree Index page, an rtree index is commonly used to speed spatial searches. An rtree index is typically defined for an array field containing the number of coordinates required to describe a "rectangle". For example:

    class rtree_class
    {
        int2 square[4];

        rtree <square> ridx;
    };

The rtree index-related functions generated for this class will be as follows:

    MCO_RET rtree_class_ridx_index_cursor(
                        mco_trans_h t,
                        /*OUT*/ mco_cursor_h c);

    MCO_RET rtree_class_ridx_search(
                        mco_trans_h t_,
                        /*IN*/ MCO_OPCODE op_,
                        /*INOUT*/ mco_cursor_h c_,
                        const int2* square);

Cursors and Searches

As explained in the R-Tree Index page, rtree searches are performed using the generated _search() function with one of the four search operation opcodes: MCO_EQUAL, MCO_CONTAIN, MCO_OVERLAP or MCO_NEIGHBORHOOD. Please refer to the Searches page for implementation details.

KD-Tree Indexes

As explained in the KD-Tree Index page, kdtree indexes are ideal for multi-dimensional key value searches. The kdtree index is defined in the schema using the kdtree declaration. For example:

    class Car
    {
        string vendor;
        string model;
        string color;
        uint4 year;
        uint4 mileage;
        boolean automatic;
        boolean ac;
        uint4 price;
        char<3> state;
        string description;

        kdtree <year, mileage, color, model, vendor, automatic, ac, price> index;
    };

The kdtree index-related functions generated for this class will be as follows:

    MCO_RET Car_index_index_cursor(
                        mco_trans_h t,
                        /*OUT*/ mco_cursor_h c);

    MCO_RET Car_index_search(
                        mco_trans_h t,
                        /*INOUT*/ mco_cursor_h c,
                        /*IN*/ Car *range_start,
                        /*IN*/ Car *range_end);

    MCO_RET Car_index_locate(
                        mco_trans_h t,
                        /*OUT*/ mco_cursor_h c,
                        Car *handle);

Cursors and Searches

As explained in the KD-Tree Index page, searches with kdtree indexes are performed using the Query-By-Example approach. Once a selection of database objects are found by the search operation, the standard cursor positioning functions mco_cursor_first(), mco_cursor_last(), mco_cursor_next() and mco_cursor_prev() are used to iterate through the result sets. Please refer to the Searches page for implementation details.

Trigram Indexes

As explained in the Trigram Index page, trigram indexes are ideal for text searches when the exact spelling of the target object is not precisely known. The trigram index is defined in the schema using the trigram declaration. For example:

    class anObject
    {
        uint4 id;
        string text;

        trigram<text> trigramIdx;
    };

The trigram index-related functions generated for this class will be as follows:

    MCO_RET anObject_trigramIdx_index_cursor(
                        mco_trans_h t,
                        /*OUT*/ mco_cursor_h c);

    MCO_RET anObject_trigramIdx_search(
                        mco_trans_h t,
                        /*INOUT*/ mco_cursor_h c,
                        MCO_OPCODE op_,
                        const char *text_key_,
                        uint2 sizeof_text_key_);

    MCO_RET anObject_trigramIdx_locate(
                        mco_trans_h t,
                        /*OUT*/ mco_cursor_h c,
                        anObject *handle);

Cursors and Searches

As explained in the Trigram Index page, searches with trigram indexes are performed using the generated _search() function. Once a selection of database objects are found by the search operation, the standard cursor positioning functions mco_cursor_first(), mco_cursor_last(), mco_cursor_next() and mco_cursor_prev() are used to iterate through the result sets. Please refer to the Searches page for implementation details.

HNSW Indexes

As explained in the HNSW Indexes page, hnsw indexes are ideal for fast approximate nearest neighbor search.

The hnsw index is defined in the schema using the hnsw declaration. For example:

    #define key_t   unsigned<4>
    #define coord_t float
    #define DIM     3

    declare database  hnswdb;

    class Embeddings
    {
        key_t   pk;
        coord_t coord[DIM];

        tree<pk> pk_idx;
        hnsw<coord> hnsw_idx[16];
    };

The DIM parameter specifies the vector dimensionality and must strictly match the input data, as it directly determines the memory footprint for coordinate storage and the computational cost of distance calculations. The value in square brackets "[16]" corresponds to the M parameter, which defines the maximum number of connections per node at each graph level: higher values improve search accuracy and routing robustness but increase memory usage and indexing time, while lower values produce a more compact index at the potential cost of recall.

Additional parameters, including ef_search, ef_construction, the distance function, and an override for M, can be configured after runtime initialization as follows:

    const int ef_construction = 100;
    const int ef_search = 100;
    const int M = 10;
    int dist_func;
    ...
    CHECK(mco_runtime_start());
    ...
    mco_runtime_setoption(MCO_RT_OPTION_HNSW_EF_SEARCH, ef_search);
    mco_runtime_setoption(MCO_RT_OPTION_HNSW_EF_CONSTRUCTION, ef_construction);
    mco_runtime_setoption(MCO_RT_OPTION_HNSW_M, M);
    dist_func = DIST_COSINE;
    mco_runtime_setoption(MCO_RT_OPTION_HNSW_DIST_FUNC, dist_func);

The available distance metrics are defined in the mco.h header file as follows:

    typedef enum {
        DIST_L2,
        DIST_COSINE,
        DIST_IP,
        DIST_MANHATTAN
    } mco_hnsw_dist_func_t;

By default, these parameters are initialized to:

Cursors and Searches

Search operations on this index are performed using the generated _search function. Please refer to the Searches page for implementation details.

Note: Cursor-based search returns up to N neighboring nodes, where N cannot exceed the total number of embeddings in the collection. Due to the approximate nature of the algorithm, the results do not guarantee strictly monotonically increasing distances between consecutive items, which is expected behavior for ANN search.

The following example demonstrates a typical usage scenario:

    #define DIM 3
    typedef float coord_t;

    static coord_t embeddings[][DIM] =
    {
        {0,0,0},
        {1,2,3},
        {1,1,1},
        {1,2,4}
    };
    ...
    void fill_database(mco_db_h db)
    {
        MCO_RET rc;
        mco_trans_h t;
        Embeddings e;
        mco_uint4 i;

        /* Store embeddings */
        printf("\n\tFilling database with embeddings...\n" );
        for (i = 0; i < sizeof(embeddings) / sizeof(embeddings[0]); ++i) {
            rc = mco_trans_start(db, MCO_READ_WRITE, MCO_TRANS_FOREGROUND, &t);
            if ( MCO_S_OK == rc ) {
            CHECK(Embeddings_new(t, &e));
            CHECK(Embeddings_pk_put(&e, i));
            CHECK(Embeddings_coord_put_range(&e,0, DIM, embeddings[i]));
            rc = mco_trans_commit(t);
            ...
        }
        ...
    }
    ...
    /* Search for nearest neighbors */
    printf("\n\tSearching for nearest neighbors...\n" );

    mco_trans_h t;
    mco_cursor_t cursor;
    MCO_RET rc;
    rc = mco_trans_start(db, MCO_READ_WRITE, MCO_TRANS_FOREGROUND, &t);
    if (MCO_S_OK == rc) {
        const coord_t pattern[DIM] = { 3, 3, 3 };
        CHECK(Embeddings_hnsw_idx_index_cursor(t, &cursor));
        for (rc = Embeddings_hnsw_idx_search(t, &cursor, pattern);
            rc == MCO_S_OK;
            rc = mco_cursor_next(t, &cursor))
        {
            Embeddings e;
            mco_uint4 pk;
            coord_t coord[DIM];

            CHECK(Embeddings_from_cursor(t, &cursor, &e));
            CHECK(Embeddings_pk_get(&e, &pk));
            CHECK(Embeddings_coord_get_range(&e, 0, DIM, coord));
            printf("Embeddings %d [%f,%f,%f]\n", pk, coord[0], coord[1], coord[2]);
        }
        CHECK(mco_cursor_close(t, &cursor));
        CHECK(mco_trans_rollback(t));
    }
    ...

Vamana(DiskANN) Indexes

Due to its architectural similarity to HNSW, the Vamana index follows the same creation and initialization workflow. The only distinction is the ALPHA parameter: assigning it any non-zero value enables the Vamana variant in place of the standard HNSW algorithm. The following code snippet demonstrates its usage:

    const int ALPHA = 10; /* 10 = 0.10, 100 = 1.00, etc. */
    ...
    mco_runtime_setoption(MCO_RT_OPTION_VAMANA_BUILD_METHOD, VAMANA_BUILD_INCREMENTAL); 
    mco_runtime_setoption(MCO_RT_OPTION_VAMANA_ALPHA, ALPHA);

Note: In the Vamana algorithm implementation, the ALPHA parameter is specified as an integer value representing hundredths of the actual floating-point value used internally. For example:

The optimal ALPHA value is not fixed and should be tuned based on your dataset and the desired trade-off between recall (search accuracy) and query latency (search speed). Higher values generally improve recall at the cost of increased search time.

The MCO_RT_OPTION_VAMANA_BUILD_METHOD option controls how the starting point (root) is chosen during Vamana graph construction. The following values are defined in the mco.h header file:

    typedef enum {
        VAMANA_BUILD_INCREMENTAL,
        VAMANA_BUILD_MEDOID,
        VAMANA_BUILD_CENTROID
    } mco_vamana_build_method_t;

Hash Indexes

As explained in the Hash and Autoid Indexes page, hash indexes are ideal for quick lookup of individual database objects. Hash indexes require an extra parameter, expected-number-of-entries, following the index name. It is an integer number that the runtime uses to allocate the initial hash table for the index. It must be specified but is not required to be exact. For example:

    class Record
    {
        uint4 iIdx;      /* Index */
        uint4 iSeries;   /* Series of measurement */

        hash <iIdx> I_Index[10000];
        nonunique hash <iSeries> I_Series[10000];
    };

Note that the [10000] specification for indexes I_Index and I_Series cause the runtime to allocate initial hash tables with space for 10000 key values.

The index-related functions generated for the (unique) hash I_Index in this class will be as follows:

    MCO_RET Record_I_Index_index_cursor(
                        mco_trans_h t,
                        /*OUT*/ mco_cursor_h c);

    MCO_RET Record_I_Index_compare(
                        mco_trans_h t,
                        mco_cursor_h c,
                        uint4 iIdx_key_,
                        /*OUT*/ int *result_);

    MCO_RET Record_I_Index_find(
                        mco_trans_h t,
                        uint4 iIdx_key_,
                        /*OUT*/ Record *handle_);

The index-related functions generated for the nonunique hash I_Series in this class will be as follows:

    MCO_RET Record_I_Series_index_cursor(
                        mco_trans_h t,
                        /*OUT*/ mco_cursor_h c);

    MCO_RET Record_I_Series_compare(
                        mco_trans_h t,
                        mco_cursor_h c,
                        uint4 iSeries_key_,
                        /*OUT*/ int *result_);

    MCO_RET Record_I_Series_search(
                        mco_trans_h t,
                        /*INOUT*/ mco_cursor_h c,
                        uint4 iSeries_key_);

Note that for unique hash indexes the exact match _find() function is generated, but for nonunique hash indexes the _search() function is generated.

Dynamic Hash Table Allocation

An eXtremeDB C API feature called dynamic hash can be enabled to automatically re-allocate the hash table as needed. This will avoid (a) long collision chains if the estimated number of objects is too small, or (b) wasting memory in the case of an overly cautious large estimate.

Note that when dynamic hash is enabled it applies to all hash indexes in the database as well as to the hash table maintained for oid and autoid indexes.

The dynamic_hash parameter (a boolean value) passed to mco_db_open_dev() in the mco_db_params_t structure determines if dynamic hash table extending is enabled or not (it is enabled by default). The initial hash table is allocated using two values: the estimated number of objects specified for this class in the database schema, and the hash_load_factor parameter (a percentage value, 100% by default), also part of the mco_db_params_t structure. The initial hash table is estimated number of objects * 100 / hash_load_factor. (The value of zero for hash_load_factor signifies the default value of 100%.)

So if hash_load_factor is 100 (i.e., 100%), then the initial size of the hash table is the specified estimated number of objects. If hash_load_factor is 50, then initial size of hash table is twice the estimated number of objects. And if hash_load_factor is 200, then the initial size of the hash table is half of the estimated number of objects.

When dynamic hash is enabled the hash_load_factor parameter is used to determine when to extend (reallocate) the hash table. For example, if the initial hash table size is 1000 and the hash_load_factor is 50, then the hash table will be extended when the 501st object is inserted; if the hash_load_factor is 150, then the hash table will be extended when the 1501st object is inserted.

If it is important to impose a definite limit on the size of the hash table, the application can disable dynamic hash by setting the dynamic_hash parameter to false. This will have the consequence that more hash conflicts can occur, so the application must be willing to pay that performance cost.

Cursors and Searches

As explained in the Hash and Autoid Indexes page, "exact match" searches with unique hash indexes are performed using the _find() function. For nonunique hash indexes the _search() function is used and once a selection of database objects are found by the search operation, the standard cursor positioning functions mco_cursor_first(), mco_cursor_last(), mco_cursor_next() and mco_cursor_prev() are used to iterate through the result sets. Please refer to the Searches page for implementation details.

OID Indexes

Whether an oid is provided by an external source or retrieved with an object as a reference to another object in the database, in C applications, an oid can be used to quickly retrieve the object it identifies. Uniqueness is enforced during object creation by the eXtremeDB runtime and an oid index can be used to establish relationships between classes in the database.

For example, to establish a relationship between an Order and Execution using oids, consider the following schema:

    struct OrderId
    {
        uint4 Id;
    };

    declare oid OrderId[1000]; // 1000 is the number of expected values (database-wide)

    class Order
    {
        ...
        vector <ref> Executions;
        ...
    };

    class Execution
    {
        float quantity;
        oid;
        ...
    };

Note that the declare statement is used to identify a unique object identifier with the expected number of objects that will be stored with an oid. The expected-number-of-entries is used by the runtime to calculate the initial hash table size for the index. (See the Hash Indexes section for an explanation of how to specify static and dynamic hash tables and how they are managed by the eXtremeDB runtime.)

Once the oid structure is declared, classes with this unique identifier can then be declared (as in the Execution class above). The runtime maintains an internal index referencing all objects of such classes. Objects can reference each other by oid using the ref data type (as in the Order class above).

The oid must be a user-defined structure, even if the oid has a single field. Each oid value must be unique for the entire database and only one oid declaration is allowed within a database schema. And only one oid statement is allowed per class. Oids must be assigned a value that is unique in the entire database (not just in the class, as is the case for hash and unique tree indexes).

In this example, the class Order contains a variable length array (a vector) Executions of references to oids of the class Execution. Each element of the vector is the oid of an instance of the class Execution and can be used to quickly reference (locate) the associated Execution object.

(For another example of creating oid references please refer to the Class Relationships page.)

OID Structures and Functions

If an oid is declared for the database, the mcocomp schema compiler generates a C structure corresponding to the structure defining the oid. For instance, for a schema containing an oid declaration like the following:

    declare database my_db;

    struct structname
    {
        uint4 num_in;
    };

    declare oid structname[10000];

the following definitions and functions will be generated:

    typedef struct my_db_oid__
    {
        uint4 num_in;
    } my_db_oid;

    static const uint2 my_db_oid_size = sizeof(my_db_oid);

    MCO_RET my_db_delete_object(
                    /*IN*/ mco_trans_h t,
                    /*IN*/ const my_db_oid *oid);

    MCO_RET my_db_get_class_code(
                    /*IN*/ mco_trans_h t,
                    /*IN*/ const my_db_oid *oid,
                    /*OUT*/ uint2 *classcode);

Note the prepended "my_db" in these definitions. This evidences the fact that only one oid can be defined for a given database and uniqueness for all values of that oid will be enforced by the eXtremeDB runtime. The _delete_object() function deletes an object based on its oid. The _get_class_code() function returns an integer that identifies the class of the object referenced by a specified oid value.

For classes containing an oid, the following functions are generated to create an object, locate an object based on its oid and to extract the oid of an object:

    MCO_RET classname_new(
                    /*IN*/ mco_trans_h t,
                    /*IN*/ const my_db_oid *id,
                    /*OUT*/ classname *handle);

    MCO_RET classname_oid_find(
                    /*IN*/ mco_trans_h t,
                    /*IN*/ const my_db_oid *id,
                    /*OUT*/ classname *handle);

    MCO_RET classname_oid_get(
                    /*IN*/ classname *handle,
                    /*OUT*/ my_db_oid *id);

Cursors and Searches

Only "exact match" searches are possible for oid which are performed using the _oid_find() function. Please refer to the Searches page for implementation details.

Autoid Indexes

The autoid is a guaranteed unique value generated by the eXtremeDB runtime. For C applications, the autoid is declared within the DDL class definition with a specified number of estimated objects of that class. An autoid index can be used to establish relationships between classes in the database. (For an example of creating autoid references please refer to the Class Relationships page.)

When a class is declared to have an autoid, the schema compiler will generate the following two functions for the class:

    MCO_RET classname_autoid_find(
                    /*IN*/ mco_trans_h t,
                    /*IN*/ autoid_t id,
                    /*OUT*/ classname *handle);

    MCO_RET classname_autoid_get(
                    /*IN*/ classname *handle,
                    /*OUT*/ autoid_t *id);

When an object of a class with an autoid is created, the runtime generates and inserts a unique autoid value for the object into an internally maintained hash index. This value can be retrieved with the generated _autoid_get() function for the given class. An autoid value, whether stored in a program variable or a field of another database object as a reference, can be used in the _autoid_find() function to locate the referenced object as demonstrated in the following code snippet:

    Schema snippet:

    class referenced
    {
        ...
        autoid[4000];
        ...
    };

    class referencing
    {
        ...
        autoid_t refd_object;
        ...
    };


    Application code snippets:

    autoid_t id;

    mco_trans_start(db, MCO_READ_WRITE, MCO_TRANS_FOREGROUND, &t);

    // Create new object, autoid assigned by system
    referenced_new(t, &refd_obj);

    // Get the autoid value
    referenced_autoid_get(&refd_obj, &id);
    rc = referencing_new(t, &refg_obj); // Create new object

    // Store ref'd autoid in it
    referencing_refd_object_put(&refg_obj, id);
    rc = mco_trans_commit(t);

    /* Object retrieval */
    rc = mco_trans_start(db, MCO_READ_ONLY, MCO_TRANS_FOREGROUND, &t);

    /* First locate a 'referencing' object by some method (not shown) */
    // Get the autoid of the referenced obj
    referencing_refd_object_get(&refg_obj, &id);

    // Locate the referenced object
    rc = referenced_autoid_find(t, id, &refd_obj);
    rc = mco_trans_commit(t);

This snippet shows the process of creating a new object of a class that has an autoid defined, retrieving the system-assigned autoid value, and storing that value in a field of an object of the class that references it. Later, the autoid value is extracted from the referencing object and used to locate the referenced object through its _autoid_find() function.

Note that the internal nature of the autoid value is not defined. The only defined property of an autoid is that it has size of 8 bytes and it is unique. An application should not rely on or expect numeric values of the autoid field.

Cursors and Searches

Only "exact match" searches are possible for autoid which are performed using the _autoid_find() function. Please refer to the Searches page for implementation details.

User-defined Indexes

For C applications, tree and hash indexes can be declared in the schema definition as userdef, in which case the application must provide custom compare functions that are used by the database runtime when building the index and during lookup. In addition, for hash indexes, the application must provide the custom hash functions. For example, consider the following sample schema:

    declare database mydb;

    class Obj
    {
        unsigned<4> first_part1;
        unsigned<2> first_part2;
        unsigned<4> second_part1;
        signed<2>   second_part2;
        string      data;

        userdef hash <first_part1, first_part2> first[1000];
        userdef tree <second_part1, second_part2> second;
    };

The following index-related functions are generated for userdef hash index first:

    MCO_RET Obj_first_index_cursor(
                    mco_trans_h t,
                    /*OUT*/ mco_cursor_h c);

    MCO_RET Obj_first_compare(
                    mco_trans_h t,
                    mco_cursor_h c,
                    uint4 first_part1_key_,
                    uint2 first_part2_key_,
                    /*OUT*/ int *result_);

    MCO_RET Obj_first_find(
                    mco_trans_h t,
                    uint4 first_part1_key_,
                    uint2 first_part2_key_,
                    /*OUT*/ Obj *handle_);

And for userdef tree index second:

    MCO_RET Obj_second_index_cursor(
                    mco_trans_h t,
                    /*OUT*/ mco_cursor_h c);

    MCO_RET Obj_second_search(
                    mco_trans_h t,
                    /*INOUT*/ mco_cursor_h c,
                    MCO_OPCODE op_,
                    uint4 second_part1_key_,
                    int2 second_part2_key_);

    MCO_RET Obj_second_compare(
                    mco_trans_h t,
                    mco_cursor_h c,
                    uint4 second_part1_key_,
                    int2 second_part2_key_,
                    /*OUT*/ int *result_);

    MCO_RET Obj_second_locate(
                    mco_trans_h t,
                    /*OUT*/ mco_cursor_h c,
                    Obj *handle);

For the tree index second it is necessary to implement two functions: the object-to-object and object-to-key compare functions. These functions return a negative, zero or a positive value depending on whether the first parameter is less than, equal to, or greater than the second parameter. For hash indexes, it is necessary to implement <classname_indexname>_hash_obj() and <classname_indexname>_hash_ext() functions in addition to the compare functions, which in this case return zero if the first and the second parameters are equal and non-zero otherwise. The function prototypes are generated by the schema compiler and are placed into a file named dbname_udf.c (where dbname is the database name in the declare database statement).

For example, for the above sample schema the following mydb_udf.c file would be generated:

    #include "mydb.h"
    #include "mcowrap.h"

    /*
    * API for the user-defined index "first"
    */
    /* object-to-object user-defined compare function */
    int2 Obj_first_compare_obj(Obj *handle1, Obj *handle2)
    {
        /* TODO: add your implementation here */
        return 0;
    }

    /* object-to-key user-defined compare function */
    int2 Obj_first_compare_ext(Obj *handle, void **key)
    {
        /* TODO: add your implementation here */
        return 0;
    }

    /* user-defined object hash function */
    uint4 Obj_first_hash_obj(Obj *handle)
    {
        /* TODO: add your implementation here */
        return 0;
    }

    /* user-defined key hash function */
    uint4 Obj_first_hash_ext(void **key)
    {
        /* TODO: add your implementation here */
        return 0;
    }

    /*
    * API for the user-defined index "second"
    */
    /* object-to-object user-defined compare function */
    int2 Obj_second_compare_obj(Obj *handle1, Obj *handle2)
    {
        /* TODO: add your implementation here */
        return 0;
    }

    /* object-to-key user-defined compare function */
    int2 Obj_second_compare_ext(Obj *handle, void **key)
    {
        /* TODO: add your implementation here */
        return 0;
    }

If a file dbname_udf.c already exists (for example if the schema was previously compiled, then modified and compiled again), the DDL compiler will generate a file dbname_udf.c.new and display a warning. In this case, it is the responsibility of the programmer to decide which file should be included in the project. If the user-defined indexes have been changed, then the .new file should be renamed to the .c file.

The custom user-defined compare functions are always called within the context of a transaction. So it is okay to access the object fields using the generated _get() functions. To access key fields within the index structure, supplementary macro definitions are generated in the dbname.h file. For the example schema above these would be as follows:

    #define Obj_first_extkey_first_part1(k)
    #define Obj_first_extkey_first_part2(k)
    #define Obj_second_extkey_second_part1(ek)
    #define Obj_second_extkey_second_part2(ek)

A sample implementation for the custom compare and hash functions could be as follows:

    /* object-to-object user-defined compare function */
    int2 Obj_first_compare_obj(Obj *handle1, Obj *handle2)
    {
        uint4 o1_first_part1, o2_first_part1;
        uint2 o1_first_part2, o2_first_part2;

        Obj_first_part1_get(handle1, &o1_first_part1);
        Obj_first_part1_get(handle2, &o2_first_part1);
        if (o1_first_part1 != o2_first_part1)
            return 1;

        Obj_first_part2_get(handle1, &o1_first_part2);
        Obj_first_part2_get(handle2, &o2_first_part2);
        if (o1_first_part2 != o2_first_part2)
            return 1;

        return 0;
    }

    /* object-to-key user-defined compare function */
    int2 Obj_first_compare_ext(Obj *handle, void **key)
    {
        uint4 o_first_part1;
        uint2 o_first_part2;

        Obj_first_part1_get(handle, &o_first_part1);
        if (o_first_part1 != Obj_first_extkey_first_part1(key))
            return 1;

        Obj_first_part2_get(handle, &o_first_part2);
        if (o_first_part2 != Obj_first_extkey_first_part2(key))
            return 1;

        return 0;
    }

    /* user-defined object hash function */
    uint4 Obj_first_hash_obj(Obj *handle)
    {
        uint4 o_first_part1;
        uint2 o_first_part2;
        uint4 hash;

        Obj_first_part1_get(handle, &o_first_part1);
        Obj_first_part2_get(handle, &o_first_part2);
        hash = (o_first_part1*1000+o_first_part2) / 1000;
        return hash;
    }

    /* user-defined key hash function */
    uint4 Obj_first_hash_ext(void **key)
    {
        uint4 hash;

        hash = (Obj_first_extkey_first_part1(key)*1000 +
            Obj_first_extkey_first_part2(key)) / 1000;
        return hash;
    }

    /*
    * API for the user-defined index "second"
    */
    /* object-to-object user-defined compare function */
    int2 Obj_second_compare_obj(Obj *handle1, Obj *handle2)
    {
        uint4 o1_second_part1, o2_second_part1;
        uint2 o1_second_part2, o2_second_part2;

        Obj_second_part1_get(handle1, &o1_second_part1);
        Obj_second_part1_get(handle2, &o2_second_part1);

        Obj_second_part2_get(handle1, &o1_second_part2);
        Obj_second_part2_get(handle2, &o2_second_part2);

        if (o1_second_part1 < o2_second_part1)
            return -1;

        if (o1_second_part1 > o2_second_part1)
            return 1;

        if (o1_second_part2 < o2_second_part2)
            return -1;

        if (o1_second_part2 > o2_second_part2)
            return 1;

        return 0;
    }

    /* object-to-key user-defined compare function */
    int2 Obj_second_compare_ext(Obj *handle, void **key)
    {
        uint4 o_second_part1;
        uint2 o_second_part2;

        Obj_second_part1_get(handle, &o_second_part1);
        Obj_second_part2_get(handle, &o_second_part2);

        if (o_second_part1 < Obj_second_extkey_second_part1(key))
            return -1;

        if (o_second_part1 > Obj_second_extkey_second_part1(key))
            return 1;

        if (o_second_part2 < Obj_second_extkey_second_part2(key))
            return -1;

        if (o_second_part2 > Obj_second_extkey_second_part2(key))
            return 1;

        return 0;
    }

Cursors and Searches

As seen above, for userdef hash indexes, only a _find() function is generated. But for tree indexes, both a _find() and a _search() function are generated.

The standard cursor positioning functions mco_cursor_first(), mco_cursor_last(), mco_cursor_next() and mco_cursor_prev() are used to iterate through the result sets. Please refer to the Searches page for implementation details.

Send feedback on this topic to McObject.Download documentation.© 2001-2026 McObject LLC. All rights reserved.