SQLite Primary Key representation differences - tsafin/tarantool GitHub Wiki
Intro
Let's start from example:
CREATE TABLE t3(a, x PRIMARY KEY, y, z); /* NO ROWID here. */
In SQLite no-rowid tables are represented as unique not null index over PK columns. Non-PK columns are also stored in such an index. SQLite performs reorder of columns, placing key columns at first place AND sorting by other columns as well.
X, A, Y, Z
Capital X means sorted by column X
This is done for improving performance of select statements. For example:
sqlite> EXPLAIN SELECT A.y FROM t4 A, t3 B WHERE A.x=10 AND A.a=44 AND A.y>1 AND A.y<10 ;
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Init 0 16 0 00 Start at 16
1 OpenRead 2 3 0 k(1,) 00 root=3 iDb=0; sqlite_autoindex_t4_1
2 OpenRead 3 2 0 k(1,) 00 root=2 iDb=0; sqlite_autoindex_t3_1
3 Explain 0 0 0 SEARCH TABLE t4 AS A USING PRIMARY KEY (x=? AND a=? AND y>? AND y<?) 00
4 Integer 10 1 0 00 r[1]=10
5 Integer 44 2 0 00 r[2]=44
6 Integer 1 3 0 00 r[3]=1
7 SeekGT 2 15 1 3 00 key=r[1..3]
8 Integer 10 3 0 00 r[3]=10
9 IdxGE 2 15 1 3 00 key=r[1..3]
10 Explain 0 1 1 SCAN TABLE t3 AS B 00
11 Rewind 3 15 4 0 00
12 Column 2 2 4 00 r[4]=t4.y
13 ResultRow 4 1 0 00 output=r[4]
14 Next 3 12 0 01
15 Halt 0 0 0 00
16 Transaction 0 0 2 0 01 usesStmtJournal=0
17 Goto 0 1 0 00
In example above optimizer discovers that all columns in WHERE clause are actually sorted. And instead of emitting 3 seeks: by a, x and y columns it instead performs seek by all 3 columns simultaneously:
4 Integer 10 1 0 00 r[1]=10 /* <-- x condition. */
5 Integer 44 2 0 00 r[2]=44 /* <-- a condition. */
6 Integer 1 3 0 00 r[3]=1 /* <-- lower bound for y. */
7 SeekGT 2 15 1 3 00 key=r[1..3]
Tarantool represents all indexes including primary by supporting dedicated structure of pointers to corresponding fields. Order of columns in tuple doesn't change. No other sorting is performed.
PK slot1 | a, X, y, z
|________^
Current state
Obviously, PK representation in Tarantool won't allow code generator to emit correct code at all. So, to map SQLite's primary key to Tarantool:
- SQLite was taught that Index (PK is Index as well in absence of rowid) has Index columns not grouped in first place [1]
- When creating Index - all non-key columns are added to Index (making it unique, BTW) [2, 3]
This leads to this representation of PK:
PK slot1, slot2, slot3, slot4 | A, X, Y, Z
|______|______|______|_____^__^ ^ ^
|______|______|_____| | |
|______|___________| |
|______________|
Having #1 done as well we have SQLite byte-code VM working.
The issue
Solution is ineffective in different ways, but most important issue is that Tarantool doesn't allow more than 255 entries in Index definition. This effectively means that table cannot contain more than 255 columns.
Perspective
Need to change SQLite VM to block this kind of optimization and return to original Tarantool's Index layout: only key columns are part of Index.
[1] - https://github.com/tarantool/tarantool/blob/kyukhin/sql2-exp/src/lib/sqlite/src/build.c#L820
[2] - https://github.com/tarantool/tarantool/blob/kyukhin/sql2-exp/src/box/sql.c#L899
[3] - https://github.com/tarantool/tarantool/blob/kyukhin/sql2-exp/src/box/sql.c#L936