Created
June 1, 2021 06:06
-
-
Save mlin/a5e9ef7ca0d6583b8397a0fb324e4327 to your computer and use it in GitHub Desktop.
SQLite OP_SeekScan regression
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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") |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment