penberg / limbo

Limbo is a work-in-progress, in-process OLTP database management system, compatible with SQLite.
MIT License
896 stars 49 forks source link

Optimize where clause bytecode #138

Closed jussisaurio closed 1 month ago

jussisaurio commented 1 month ago

addresses #122

I was exploring support for basic joins, but without this optimization it would have just added more spaghetti to translate_expr().

-> add separate handling for processing AST nodes when we know the top AST node specifies a condition expression (where, join)

Limbo:

>  explain select id from users where first_name = 'John';
addr  opcode             p1    p2    p3    p4             p5  comment
----  -----------------  ----  ----  ----  -------------  --  -------
0     Init               0     13    0                    0   Start at 13
1     OpenReadAsync      0     2     0                    0   root=2
2     OpenReadAwait      0     0     0                    0   
3     RewindAsync        0     0     0                    0   
4     RewindAwait        0     12    0                    0   
5       Column           0     1     1                    0   r[1]= cursor 0 column 1
6       String8          2     0     0     John           0   r[2]= 'John'
7       Ne               1     2     10                   0   r[1] != r[2] -> 10
8       RowId            0     3     0                    0   
9       ResultRow        3     1     0                    0   output=r[3..4]
10    NextAsync          0     0     0                    0   
11    NextAwait          0     4     0                    0   
12    Halt               0     0     0                    0   
13    Transaction        0     0     0                    0   
14    Goto               0     1     0                    0

Sqlite3:

sqlite> explain select id from users where first_name = 'John';
addr  opcode         p1    p2    p3    p4             p5  comment      
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     9     0                    0   Start at 9
1     OpenRead       0     2     0     2              0   root=2 iDb=0; users
2     Rewind         0     8     0                    0   
3       Column         0     1     1                    0   r[1]= cursor 0 column 1
4       Ne             2     7     1     BINARY-8       82  if r[1]!=r[2] goto 7
5       Rowid          0     3     0                    0   r[3]=users.rowid
6       ResultRow      3     1     0                    0   output=r[3]
7     Next           0     3     0                    1   
8     Halt           0     0     0                    0   
9     Transaction    0     0     2     0              1   usesStmtJournal=0
10    String8        0     2     0     John           0   r[2]='John'
11    Goto           0     1     0                    0