Блог

У меня есть индекс с несколькими ключами по полю, в котором хранится массив целых чисел. Как я могу реализовать разбивку на страницы на основе курсора, используя его?

В действительности, если кортеж имеет более одного значения в поле массива, он будет выбран #tuple[array_field_idx] несколько раз. Вчера я реализовал «отдельный» выбор (используя ffi для получения адреса указателя кортежа), но, похоже, он не будет работать с разбивкой на страницы.

Есть ли у вас какие-либо идеи, как это можно реализовать в Tarantool?

Чтобы реализовать разбивку на страницы для индекса с несколькими клавишами, вы должны кое-что знать о внутренностях Tarantool.

Я напишу код, который работает для Tarantool 2.3 (но в будущем он может быть поврежден). Пожалуйста, тщательно протестируйте их и обновите определение FFI в случае обновления версии Tarantool.

Итак, давайте начнем. Во-первых, вы должны знать, что Tarantool BTree хранит данные в специальной структуре memtx_tree_data, которая содержит указатель на ваш кортеж и hint . Это специальное число, которое позволяет ускорить сравнение между кортежами для простого индекса дерева, и это позиция индексируемого элемента в массиве.

Во-первых, мы должны понять, как извлечь подсказку кортежа с помощью кортежа. Это можно было бы сделать, используя некоторый фрагмент кода FFI и итератор дерева.

 local ffi = require('ffi')

ffi.cdef([[

typedef struct index_def;

typedef struct index;

typedef struct memtx_tree;

typedef struct mempool;

typedef uint64_t hint_t;

enum iterator_type {
    /* ITER_EQ must be the first member for request_create  */
    ITER_EQ               =  0, /* key == x ASC order                  */
    ITER_REQ              =  1, /* key == x DESC order                 */
    ITER_ALL              =  2, /* all tuples                          */
    ITER_LT               =  3, /* key <  x                            */
    ITER_LE               =  4, /* key <= x                            */
    ITER_GE               =  5, /* key >= x                            */
    ITER_GT               =  6, /* key >  x                            */
    ITER_BITS_ALL_SET     =  7, /* all bits from x are set in key      */
    ITER_BITS_ANY_SET     =  8, /* at least one x's bit is set         */
    ITER_BITS_ALL_NOT_SET =  9, /* all bits are not set                */
    ITER_OVERLAPS         = 10, /* key overlaps x                      */
    ITER_NEIGHBOR         = 11, /* tuples in distance ascending order from specified point */
    iterator_type_MAX
};


typedef struct iterator {
    /**
     * Iterate to the next tuple.
     * The tuple is returned in @ret (NULL if EOF).
     * Returns 0 on success, -1 on error.
     */
    int (*next)(struct iterator *it, struct tuple **ret);
    /** Destroy the iterator. */
    void (*free)(struct iterator *);
    /** Space cache version at the time of the last index lookup. */
    uint32_t space_cache_version;
    /** ID of the space the iterator is for. */
    uint32_t space_id;
    /** ID of the index the iterator is for. */
    uint32_t index_id;
    /**
     * Pointer to the index the iterator is for.
     * Guaranteed to be valid only if the schema
     * state has not changed since the last lookup.
     */
    struct index *index;
};


struct memtx_tree_key_data {
    /** Sequence of msgpacked search fields. */
    const char *key;
    /** Number of msgpacked search fields. */
    uint32_t part_count;
    /** Comparison hint, see tuple_hint(). */
    hint_t hint;
};

struct memtx_tree_data {
    /* Tuple that this node is represents. */
    struct tuple *tuple;
    /** Comparison hint, see key_hint(). */
    hint_t hint;
};

typedef int16_t bps_tree_pos_t;
typedef uint32_t bps_tree_block_id_t;

typedef uint32_t matras_id_t;

struct matras_view {
    /* root extent of the view */
    void *root;
    /* block count in the view */
    matras_id_t block_count;
    /* all views are linked into doubly linked list */
    struct matras_view *prev_view, *next_view;
};

struct memtx_tree_iterator {
    /* ID of a block, containing element. -1 for an invalid iterator */
    bps_tree_block_id_t block_id;
    /* Position of an element in the block. Could be -1 for last in block*/
    bps_tree_pos_t pos;
    /* Version of matras memory for MVCC */
    struct matras_view view;
};

typedef struct tree_iterator {
    struct iterator base;
    struct memtx_tree_iterator tree_iterator;
    enum iterator_type type;
    struct memtx_tree_key_data key_data;
    struct memtx_tree_data current;
    /** Memory pool the iterator was allocated from. */
    struct mempool *pool;
};

]])


local function get_tree_comparison_hint(box_iterator_state)
    if box_iterator_state == nil then
        return nil
    end

    local casted = ffi.cast("struct tree_iterator*", box_iterator_state)
    --
    -- IMPORTANT: hint is zero-based (as arrays in C)
    -- Lua arrays is one-based.
    --
    return casted.current.hint
end

return {
    get_tree_comparison_hint = get_tree_comparison_hint,
}

  

Затем рассмотрим следующий пример:

 local box_iterator = require('common.box_iterator')

box.cfg{}

local space = box.schema.create_space('dict', {
    format = {
        {name = 'id', type = 'number'},
        {name = 'bundles', type = 'array'}
    },
    if_not_exists = true,
})

space:create_index('pk', {
    unique = true,
    parts = {
        {field = 1, type = 'number'}
    },
    if_not_exists = true,
})

space:create_index('multikey', {
    unique = false,
    parts = {
        {field = 2, type = 'string', path = '[*]'},
        -- Note: I intentionally add primary index parts here
        {field = 1, type = 'number'}
    },
    if_not_exists = true,
})

space:replace({1, {'a', 'b', 'c', 'd'}})
space:replace({2, {'b', 'c'}})
space:replace({3, {'a', 'd'}})
space:replace({4, {'c', 'd'}})

for iter_state, tuple in space.index.multikey:pairs({'a'}, {iterator = 'GE'}) do
    local position = box_iterator.get_tree_comparison_hint(iter_state)   1
    print(
        string.ljust(tostring(tuple), 30),
        position,
        tuple[2][tonumber(position)]
    )
end

os.exit()
  

Вывод:

 # Tuple                         Hint   Indexed element
[1, ['a', 'b', 'c', 'd']]       1ULL    a
[3, ['a', 'd']]                 1ULL    a
[1, ['a', 'b', 'c', 'd']]       2ULL    b
[2, ['b', 'c']]                 1ULL    b
[1, ['a', 'b', 'c', 'd']]       3ULL    c
[2, ['b', 'c']]                 2ULL    c
[4, ['c', 'd']]                 1ULL    c
[1, ['a', 'b', 'c', 'd']]       4ULL    d
[3, ['a', 'd']]                 2ULL    d
[4, ['c', 'd']]                 2ULL    d
  

Как вы видите, порядок строго определен.
Tarantool возвращает мне кортежи в порядке, который определяется с помощью (a) индексированного значения — кортежа [path_to_array][подсказка 1] и первичного ключа.
Второе условие является общим для всех вторичных неуникальных индексов Tarantool.
Tarantool внутренне объединяет первичный ключ с каждым неуникальным индексом.
Все, что вам нужно, это явно указать это в вашей схеме.

Итак, следующий термин cursor . Курсор позволяет продолжить итерацию с того места, где вы ранее остановились. Для уникальных индексов курсор — это поля этих индексов, для неуникального индекса — это поля этих индексов с первичным ключом слияния (подробнее см. Функцию key_def.merge, в настоящее время она не поддерживает индексы с несколькими ключами, но это полезно, если вам нужно понять, как работать с объединением частей индекса). Следующая комбинация ( merge(secondary_index_parts, primary_index_parts) ) всегда является уникальным значением, что позволяет продолжить итерацию со строго определенного места.

Давайте вернемся к моему примеру. Например. Я остановился на строке [1, ['a', 'b', 'c', 'd']] 3ULL c . Мой курсор {'c', 1} .

Ну, теперь я мог бы продолжить с этого момента:

 -- "GE" is changed to "GT" to skip already scanned tuple: [1, ['a', 'b', 'c', 'd']]
for iter_state, tuple in space.index.multikey:pairs({'c', 1}, {iterator = 'GT'}) do
    local position = box_iterator.get_tree_comparison_hint(iter_state)   1
    print(
        string.ljust(tostring(tuple), 30),
        position,
        tuple[2][tonumber(position)]
    )
end
--[[
Result:
[2, ['b', 'c']]                 2ULL    c
[4, ['c', 'd']]                 1ULL    c
[1, ['a', 'b', 'c', 'd']]       4ULL    d
[3, ['a', 'd']]                 2ULL    d
[4, ['c', 'd']]                 2ULL    d
--]]
  

Вы можете сравнить с предыдущим фрагментом и понять, что я продолжаю сканирование с необходимого значения, не сканирую избыточные значения и ничего не теряю.

Такой подход не совсем понятен и не совсем удобен. Вам нужно извлечь какое-то магическое значение из внутренних компонентов Tarantool, сохранить их где угодно. Но мы используем такой подход в наших проектах, потому что у нас пока нет альтернатив 🙂