21875500784

Committed 10 Feb 2026 05:29PM UTC coverage: 88.313% (-0.04%) from 88.351%

Build # 21875500784

Build Type

Pull #491

github

Committed by

vakhov

Commit Message

fix(select): use native after option for pagination on Tarantool 2.10+

Optimize crud.select() and crud.pairs() pagination with after cursor
by using native after option on Tarantool 2.10+ for O(1) cursor
positioning instead of O(N) scroll_to_after_tuple.

The optimization applies to all iterators (GT/GE/LT/LE/EQ/REQ).
For EQ/REQ iterators, native after is used only when after_tuple
key matches scan_value to avoid 'Iterator position is invalid' error.

Readview operations use native after only on Tarantool 3.x, since
the after option for read_view:pairs() is not available in 2.x.

Closes #488

Pull Request Pull Request #491: fix(select): use native after option for pagination on Tarantool 2.10+

Run Details

14 of 18 new or added lines in 2 files covered. (77.78%)

1 existing line in 1 file now uncovered.

5252 of 5947 relevant lines covered (88.31%)

12432.2 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

84.35

/crud/select/executor.lua

local errors = require('errors')
local fiber = require('fiber')
local fun = require('fun')

local dev_checks = require('crud.common.dev_checks')
local select_comparators = require('crud.compare.comparators')
local compat = require('crud.common.compat')
local has_keydef = compat.exists('tuple.keydef', 'key_def')

local keydef_lib
if has_keydef then
    keydef_lib = compat.require('tuple.keydef', 'key_def')
end

local utils = require('crud.common.utils')

local ExecuteSelectError = errors.new_class('ExecuteSelectError')

local executor = {}

local function scroll_to_after_tuple(gen, space, scan_index, tarantool_iter, after_tuple, yield_every)
    local primary_index = space.index[0]

    local scroll_key_parts = utils.merge_primary_key_parts(scan_index.parts, primary_index.parts)

    local cmp_operator = select_comparators.get_cmp_operator(tarantool_iter)
    local scroll_comparator = select_comparators.gen_tuples_comparator(cmp_operator, scroll_key_parts)

    local looked_up_tuples = 0
    while true do
        local tuple
        gen.state, tuple = gen(gen.param, gen.state)
        looked_up_tuples = looked_up_tuples + 1

        if yield_every ~= nil and looked_up_tuples % yield_every == 0 then
            fiber.yield()
        end

        if tuple == nil then
            return nil
        end

        if scroll_comparator(tuple, after_tuple) then
            return tuple
        end
    end
end

local generate_value

if has_keydef then
    generate_value = function(after_tuple, scan_value, index_parts, tarantool_iter)
        local key_def = keydef_lib.new(index_parts)
        if #scan_value == 0 and after_tuple ~= nil then
            return key_def:extract_key(after_tuple)
        end
        local cmp_operator = select_comparators.get_cmp_operator(tarantool_iter)
        local cmp = key_def:compare_with_key(after_tuple, scan_value)
        if (cmp_operator == '<' and cmp < 0) or (cmp_operator == '>' and cmp > 0) then
            return key_def:extract_key(after_tuple)
        end
    end
else
    generate_value = function(after_tuple, scan_value, index_parts, tarantool_iter)
        local after_tuple_key = utils.extract_key(after_tuple, index_parts)
        if #scan_value == 0 and after_tuple ~= nil then
            return after_tuple_key
        end
        local cmp_operator = select_comparators.get_cmp_operator(tarantool_iter)
        local scan_comparator = select_comparators.gen_tuples_comparator(cmp_operator, index_parts)
        if scan_comparator(after_tuple_key, scan_value) then
            return after_tuple_key
        end
    end
end

function executor.execute(space, index, filter_func, opts)
    dev_checks('table', 'table', 'function', {
        scan_value = 'table|cdata',
        after_tuple = '?table|cdata',
        tarantool_iter = 'number',
        limit = '?number',
        yield_every = '?number',
        readview = '?boolean',
        readview_index = '?table'
    })

    opts = opts or {}

    local resp = { tuples_fetched = 0, tuples_lookup = 0, tuples = {} }

    if opts.limit == 0 then
        return resp
    end

    local value = opts.scan_value
    local use_native_after = false

    if opts.after_tuple ~= nil then
        local iter = opts.tarantool_iter
        if iter == box.index.EQ or iter == box.index.REQ then
            -- we need to make sure that the keys are equal
            -- the code is correct even if value is a partial key
            local parts = {}
            for i, _ in ipairs(value) do
                -- the code required for tarantool 1.10.6 at least
                table.insert(parts, index.parts[i])
            end

            local is_eq = iter == box.index.EQ
            local is_after_bigger
            local is_keys_equal
            if has_keydef then
                local key_def = keydef_lib.new(parts)
                local cmp = key_def:compare_with_key(opts.after_tuple, value)
                is_after_bigger = (is_eq and cmp > 0) or (not is_eq and cmp < 0)
                is_keys_equal = (cmp == 0)
            else
                local comparator
                if is_eq then
                    comparator = select_comparators.gen_func('<=', parts)
                else
                    comparator = select_comparators.gen_func('>=', parts)
                end
                local after_key = utils.extract_key(opts.after_tuple, parts)
                is_after_bigger = not comparator(after_key, value)
                -- check equality for native after support
                local eq_comparator = select_comparators.gen_func('==', parts)
                is_keys_equal = eq_comparator(after_key, value)
            end
            if is_after_bigger then
                -- it makes no sence to continue
                return resp
            end
            -- native after requires after_tuple to match scan_value for EQ/REQ
            if is_keys_equal and utils.tarantool_supports_index_pairs_after() then
                use_native_after = true
            end
        else
            local new_value = generate_value(opts.after_tuple, value, index.parts, iter)
            if new_value ~= nil then
                value = new_value
                -- use native after for O(1) positioning (Tarantool 2.10+)
                if utils.tarantool_supports_index_pairs_after() then
                    use_native_after = true
                end
            end
        end
    end

    local tuple
    local raw_gen, param, state
    local pairs_opts = { iterator = opts.tarantool_iter }

    -- Disable native after for readview on Tarantool < 3.x
    if opts.readview and not utils.is_tarantool_3() then
        use_native_after = false
    end

    if use_native_after then
        pairs_opts.after = opts.after_tuple
    end

    if opts.readview then
        raw_gen, param, state = opts.readview_index:pairs(value, pairs_opts)
    else
        raw_gen, param, state = index:pairs(value, pairs_opts)
    end
    local gen = fun.wrap(function(param, state)
        local next_state, var = raw_gen(param, state)

        if var ~= nil then
            resp.tuples_lookup = resp.tuples_lookup + 1
        end

        return next_state, var
    end, param, state)

    if opts.after_tuple ~= nil and not use_native_after then
        local err
        tuple, err = scroll_to_after_tuple(gen, space, index, opts.tarantool_iter, opts.after_tuple, opts.yield_every)
        if err ~= nil then
            return nil, ExecuteSelectError:new("Failed to scroll to the after_tuple: %s", err)
        end

        if tuple == nil then
            return resp
        end
    end

    if tuple == nil then
        gen.state, tuple = gen(gen.param, gen.state)
    end

    local looked_up_tuples = 0
    while true do
        if tuple == nil then
            break
        end

        local matched, early_exit = filter_func(tuple)

        if matched then
            table.insert(resp.tuples, tuple)
            resp.tuples_fetched = resp.tuples_fetched + 1

            if opts.limit ~= nil and resp.tuples_fetched >= opts.limit then
                break
            end
        elseif early_exit then
            break
        end

        gen.state, tuple = gen(gen.param, gen.state)
        looked_up_tuples = looked_up_tuples + 1

        if opts.yield_every ~= nil and looked_up_tuples % opts.yield_every == 0 then
            fiber.yield()
        end
    end

    return resp
end

return executor

1	local errors = require('errors')	633✔
2	local fiber = require('fiber')	633✔
3	local fun = require('fun')	633✔
4
5	local dev_checks = require('crud.common.dev_checks')	633✔
6	local select_comparators = require('crud.compare.comparators')	633✔
7	local compat = require('crud.common.compat')	633✔
8	local has_keydef = compat.exists('tuple.keydef', 'key_def')	633✔
9
10	local keydef_lib
11	if has_keydef then	633✔
12	keydef_lib = compat.require('tuple.keydef', 'key_def')	1,266✔
13	end
14
15	local utils = require('crud.common.utils')	633✔
16
17	local ExecuteSelectError = errors.new_class('ExecuteSelectError')	633✔
18
19	local executor = {}	633✔
20
21	local function scroll_to_after_tuple(gen, space, scan_index, tarantool_iter, after_tuple, yield_every)
22	local primary_index = space.index[0]	123✔
23
24	local scroll_key_parts = utils.merge_primary_key_parts(scan_index.parts, primary_index.parts)	123✔
25
26	local cmp_operator = select_comparators.get_cmp_operator(tarantool_iter)	123✔
27	local scroll_comparator = select_comparators.gen_tuples_comparator(cmp_operator, scroll_key_parts)	123✔
28
29	local looked_up_tuples = 0	123✔
30	while true do
31	local tuple
32	gen.state, tuple = gen(gen.param, gen.state)	346✔
33	looked_up_tuples = looked_up_tuples + 1	173✔
34
35	if yield_every ~= nil and looked_up_tuples % yield_every == 0 then	173✔
36	fiber.yield()	×
37	end
38
39	if tuple == nil then	173✔
40	return nil	34✔
41	end
42
43	if scroll_comparator(tuple, after_tuple) then	278✔
44	return tuple	89✔
45	end
46	end
47	end
48
49	local generate_value
50
51	if has_keydef then	633✔
52	generate_value = function(after_tuple, scan_value, index_parts, tarantool_iter)
53	local key_def = keydef_lib.new(index_parts)	1,383✔
54	if #scan_value == 0 and after_tuple ~= nil then	1,383✔
55	return key_def:extract_key(after_tuple)	168✔
56	end
57	local cmp_operator = select_comparators.get_cmp_operator(tarantool_iter)	1,299✔
58	local cmp = key_def:compare_with_key(after_tuple, scan_value)	2,598✔
59	if (cmp_operator == '<' and cmp < 0) or (cmp_operator == '>' and cmp > 0) then	1,299✔
60	return key_def:extract_key(after_tuple)	2,370✔
61	end
62	end
63	else
64	generate_value = function(after_tuple, scan_value, index_parts, tarantool_iter)
65	local after_tuple_key = utils.extract_key(after_tuple, index_parts)	×
66	if #scan_value == 0 and after_tuple ~= nil then	×
67	return after_tuple_key	×
68	end
69	local cmp_operator = select_comparators.get_cmp_operator(tarantool_iter)	×
70	local scan_comparator = select_comparators.gen_tuples_comparator(cmp_operator, index_parts)	×
71	if scan_comparator(after_tuple_key, scan_value) then	×
72	return after_tuple_key	×
73	end
74	end
75	end
76
77	function executor.execute(space, index, filter_func, opts)	633✔
78	dev_checks('table', 'table', 'function', {	12,225✔
79	scan_value = 'table\|cdata',
80	after_tuple = '?table\|cdata',
81	tarantool_iter = 'number',
82	limit = '?number',
83	yield_every = '?number',
84	readview = '?boolean',
85	readview_index = '?table'
86	})
87
88	opts = opts or {}	12,225✔
89
90	local resp = { tuples_fetched = 0, tuples_lookup = 0, tuples = {} }	12,225✔
91
92	if opts.limit == 0 then	12,225✔
93	return resp	5✔
94	end
95
96	local value = opts.scan_value	12,220✔
97	local use_native_after = false	12,220✔
98
99	if opts.after_tuple ~= nil then	12,220✔
100	local iter = opts.tarantool_iter	3,430✔
101	if iter == box.index.EQ or iter == box.index.REQ then	3,430✔
102	-- we need to make sure that the keys are equal
103	-- the code is correct even if value is a partial key
104	local parts = {}	2,047✔
105	for i, _ in ipairs(value) do	4,104✔
106	-- the code required for tarantool 1.10.6 at least
107	table.insert(parts, index.parts[i])	2,057✔
108	end
109
110	local is_eq = iter == box.index.EQ	2,047✔
111	local is_after_bigger
112	local is_keys_equal
113	if has_keydef then	2,047✔
114	local key_def = keydef_lib.new(parts)	2,047✔
115	local cmp = key_def:compare_with_key(opts.after_tuple, value)	4,094✔
116	is_after_bigger = (is_eq and cmp > 0) or (not is_eq and cmp < 0)	2,047✔
117	is_keys_equal = (cmp == 0)	2,047✔
118	else
119	local comparator
120	if is_eq then	×
121	comparator = select_comparators.gen_func('<=', parts)	×
122	else
123	comparator = select_comparators.gen_func('>=', parts)	×
124	end
125	local after_key = utils.extract_key(opts.after_tuple, parts)	×
126	is_after_bigger = not comparator(after_key, value)	×
127	-- check equality for native after support
NEW 128	local eq_comparator = select_comparators.gen_func('==', parts)	×
NEW 129	is_keys_equal = eq_comparator(after_key, value)	×
130	end
131	if is_after_bigger then	2,047✔
132	-- it makes no sence to continue
133	return resp	8✔
134	end
135	-- native after requires after_tuple to match scan_value for EQ/REQ
136	if is_keys_equal and utils.tarantool_supports_index_pairs_after() then	4,069✔
137	use_native_after = true	2,030✔
138	end
139	else
140	local new_value = generate_value(opts.after_tuple, value, index.parts, iter)	1,383✔
141	if new_value ~= nil then	1,383✔
142	value = new_value	1,269✔
143	-- use native after for O(1) positioning (Tarantool 2.10+)
144	if utils.tarantool_supports_index_pairs_after() then	2,538✔
145	use_native_after = true	1,269✔
146	end
147	end
148	end
149	end
150
151	local tuple
152	local raw_gen, param, state
153	local pairs_opts = { iterator = opts.tarantool_iter }	12,212✔
154
155	-- Disable native after for readview on Tarantool < 3.x
156	if opts.readview and not utils.is_tarantool_3() then	12,212✔
NEW 157	use_native_after = false	×
158	end
159
160	if use_native_after then	12,212✔
161	pairs_opts.after = opts.after_tuple	3,299✔
162	end
163
164	if opts.readview then	12,212✔
NEW 165	raw_gen, param, state = opts.readview_index:pairs(value, pairs_opts)	×
166	else
167	raw_gen, param, state = index:pairs(value, pairs_opts)	24,392✔
168	end
169	local gen = fun.wrap(function(param, state)	24,360✔
170	local next_state, var = raw_gen(param, state)	91,041✔
171
172	if var ~= nil then	91,041✔
173	resp.tuples_lookup = resp.tuples_lookup + 1	84,472✔
174	end
175
176	return next_state, var	91,041✔
177	end, param, state)	12,180✔
178
179	if opts.after_tuple ~= nil and not use_native_after then	12,180✔
180	local err
181	tuple, err = scroll_to_after_tuple(gen, space, index, opts.tarantool_iter, opts.after_tuple, opts.yield_every)	246✔
182	if err ~= nil then	123✔
183	return nil, ExecuteSelectError:new("Failed to scroll to the after_tuple: %s", err)	×
184	end
185
186	if tuple == nil then	123✔
187	return resp	34✔
188	end
189	end
190
191	if tuple == nil then	12,146✔
192	gen.state, tuple = gen(gen.param, gen.state)	24,114✔
193	end
194
195	local looked_up_tuples = 0	12,146✔
196	while true do
197	if tuple == nil then	90,957✔
198	break	6,535✔
199	end
200
201	local matched, early_exit = filter_func(tuple)	84,422✔
202
203	if matched then	84,422✔
204	table.insert(resp.tuples, tuple)	83,371✔
205	resp.tuples_fetched = resp.tuples_fetched + 1	83,371✔
206
207	if opts.limit ~= nil and resp.tuples_fetched >= opts.limit then	83,371✔
208	break	5,592✔
209	end
210	elseif early_exit then	1,051✔
211	break	19✔
212	end
213
214	gen.state, tuple = gen(gen.param, gen.state)	157,622✔
215	looked_up_tuples = looked_up_tuples + 1	78,811✔
216
217	if opts.yield_every ~= nil and looked_up_tuples % opts.yield_every == 0 then	78,811✔
218	fiber.yield()	4,000✔
219	end
220	end
221
222	return resp	12,146✔
223	end
224
225	return executor	633✔

tarantool / crud / 21875500784

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous