SQLite OP_SeekScan regression

sqlite_seekscan_regression.py

#!/usr/bin/env python3
# run this script using LD_LIBRARY_PATH to manipulate the SQlite3 library version
import os
import random
import time
import sqlite3

N = 100000
random.seed(42)

print("SQLite version " + sqlite3.sqlite_version)

try:
    os.unlink("/tmp/seek_scan_regression.db")
except FileNotFoundError:
    pass

# schema
dbh = sqlite3.connect("/tmp/seek_scan_regression.db")
dbh.executescript("""
CREATE TABLE node(node_id INTEGER PRIMARY KEY);
CREATE TABLE edge(node_from INTEGER NOT NULL REFERENCES node(node_id), node_to INTEGER NOT NULL REFERENCES node(node_id));
CREATE TABLE temp.sub_nodes(node_id INTEGER PRIMARY KEY)
""")

# populate nodes
for _ in range(N):
    dbh.execute("INSERT INTO node(node_id) VALUES(?)", (None,))

# populate edges
for n in range(1,N):
    dbh.execute("INSERT INTO edge(node_from,node_to) VALUES(?,?)", (n,n+1))
    dbh.execute("INSERT INTO edge(node_from,node_to) VALUES(?,?)", (n,random.randrange(1, N)))

# define a random subset of nodes
for n in random.sample(range(1,N), N//10):
    dbh.execute("INSERT INTO temp.sub_nodes(node_id) VALUES(?)", (n,))

# index graph
dbh.executescript("""
CREATE INDEX edge_from_to ON edge(node_from,node_to);
CREATE INDEX edge_to_from ON edge(node_to,node_from);
ANALYZE
""")
dbh.commit()

# count edges touching only nodes in temp.sub_nodes
sub_edge_query = """
SELECT count(_rowid_)
FROM edge
WHERE node_from IN temp.sub_nodes AND node_to IN temp.sub_nodes
"""

for row in dbh.execute("explain " + sub_edge_query):
    print(row)

for i in range(10):
    t0 = time.time()
    ans = next(dbh.execute(sub_edge_query))[0]
    t1 = time.time()
    print(f"{ans}\t{t1-t0}s")

stdout_3.31.1.txt

SQLite version 3.31.1
(0, 'Init', 0, 28, 0, '', '00', None)
(1, 'Null', 0, 1, 2, '', '00', None)
(2, 'OpenRead', 3, 1644, 0, 'k(3,,,)', '02', None)
(3, 'Once', 0, 5, 0, '', '00', None)
(4, 'OpenRead', 4, 2, 1, '1', '00', None)
(5, 'Rewind', 4, 24, 0, '', '00', None)
(6, 'Rowid', 4, 3, 0, '', '00', None)
(7, 'IsNull', 3, 23, 0, '', '00', None)
(8, 'SeekGE', 3, 23, 3, '1', '00', None)
(9, 'IdxGT', 3, 23, 3, '1', '00', None)
(10, 'Once', 0, 12, 0, '', '00', None)
(11, 'OpenRead', 5, 2, 1, '1', '00', None)
(12, 'Column', 3, 1, 4, '', '00', None)
(13, 'SeekRowid', 5, 22, 4, '', '00', None)
(14, 'Goto', 0, 20, 0, '', '00', None)
(15, 'Goto', 0, 22, 0, '', '00', None)
(16, 'Rewind', 5, 22, 0, '', '00', None)
(17, 'Column', 5, 0, 5, '', '00', None)
(18, 'Ne', 4, 22, 5, '(BINARY)', '00', None)
(19, 'Goto', 0, 22, 0, '', '00', None)
(20, 'IdxRowid', 3, 5, 0, '', '00', None)
(21, 'AggStep', 0, 5, 1, 'count(1)', '01', None)
(22, 'Next', 3, 9, 0, '', '00', None)
(23, 'Next', 4, 6, 0, '', '00', None)
(24, 'AggFinal', 1, 1, 0, 'count(1)', '00', None)
(25, 'Copy', 1, 6, 0, '', '00', None)
(26, 'ResultRow', 6, 1, 0, '', '00', None)
(27, 'Halt', 0, 0, 0, '', '00', None)
(28, 'Transaction', 0, 0, 5, '0', '01', None)
(29, 'Transaction', 1, 0, 1, '0', '01', None)
(30, 'Goto', 0, 1, 0, '', '00', None)
1929	0.011055707931518555s
1929	0.013242244720458984s
1929	0.011191129684448242s
1929	0.011559247970581055s
1929	0.011748552322387695s
1929	0.013076543807983398s
1929	0.011844873428344727s
1929	0.011509895324707031s
1929	0.012105703353881836s
1929	0.011955022811889648s

stdout_3.35.5.txt

SQLite version 3.35.5
(0, 'Init', 0, 25, 0, None, 0, None)
(1, 'Null', 0, 1, 2, None, 0, None)
(2, 'OpenRead', 3, 1644, 0, 'k(3,,,)', 0, None)
(3, 'Once', 0, 5, 0, None, 0, None)
(4, 'OpenRead', 4, 2, 1, '1', 0, None)
(5, 'Rewind', 4, 21, 0, None, 0, None)
(6, 'Rowid', 4, 3, 0, None, 0, None)
(7, 'IsNull', 3, 20, 0, None, 0, None)
(8, 'Once', 0, 10, 0, None, 0, None)
(9, 'OpenRead', 5, 2, 1, '1', 0, None)
(10, 'Rewind', 5, 20, 0, None, 0, None)
(11, 'Rowid', 5, 4, 0, None, 0, None)
(12, 'IsNull', 4, 19, 0, None, 0, None)
(13, 'SeekScan', 18, 16, 0, None, 0, None)
(14, 'SeekGE', 3, 19, 3, '2', 0, None)
(15, 'IdxGT', 3, 19, 3, '2', 0, None)
(16, 'IdxRowid', 3, 5, 0, None, 0, None)
(17, 'AggStep', 0, 5, 1, 'count(1)', 1, None)
(18, 'Next', 3, 15, 0, None, 0, None)
(19, 'Next', 5, 11, 0, None, 0, None)
(20, 'Next', 4, 6, 0, None, 0, None)
(21, 'AggFinal', 1, 1, 0, 'count(1)', 0, None)
(22, 'Copy', 1, 6, 0, None, 0, None)
(23, 'ResultRow', 6, 1, 0, None, 0, None)
(24, 'Halt', 0, 0, 0, None, 0, None)
(25, 'Transaction', 0, 0, 5, '0', 1, None)
(26, 'Transaction', 1, 0, 1, '0', 1, None)
(27, 'Goto', 0, 1, 0, None, 0, None)
1929	6.112736463546753s
1929	6.585275173187256s
1929	6.145063400268555s
1929	5.8329689502716064s
1929	6.072556257247925s
1929	5.89276647567749s
1929	6.187780857086182s
1929	6.085240840911865s
1929	5.964672088623047s
1929	5.95971941947937s