Skip to content

SQLite Primary Key representation differences

Jump to bottom
Kirill Yukhin edited this page Jul 6, 2017 · 2 revisions

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:

  1. SQLite was taught that Index (PK is Index as well in absence of rowid) has Index columns not grouped in first place [1]
  2. 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

Developer Guidelines ↗

Architecture

How To ...?

Recipes

Upgrade instructions

Useful links

Old discussions

Personal pages

Clone this wiki locally