Pekka Enberg
53633e8b6f
core/btree: Add PageContent::new() helper
2025-04-10 13:14:38 +03:00
Pekka Enberg
a7fa7f7c62
core/btree: Unify debug() tracing
2025-04-10 08:39:07 +03:00
Pekka Enberg
761c03f7c5
core/btree: Clean up B-Tree offset comments
2025-04-10 08:27:55 +03:00
Pekka Enberg
86a4d3e33b
core/btree: Move B-Tree header offsets in a module
...
The grouping (with a fancy comment) makes the code a bit more readable.
2025-04-10 08:19:08 +03:00
Pekka Enberg
11782cbff8
core/btree: Clean up imports
2025-04-10 07:52:10 +03:00
Pere Diaz Bou
6a02730c1a
rebase fixes
2025-04-09 15:56:04 +02:00
Pere Diaz Bou
7b384f8e5c
set iteration_state for insert
2025-04-09 15:29:06 +02:00
Pere Diaz Bou
6b7575bf3f
fix tree traversal assumptions on traversal
2025-04-09 15:04:45 +02:00
Pere Diaz Bou
f2d9e1e8f5
fix divider cell in index
2025-04-09 15:04:45 +02:00
Pere Diaz Bou
12899034c9
make insert idx re-entrant
2025-04-09 15:04:45 +02:00
Pere Diaz Bou
d9453f6e06
fix cell_get_raw_region length calculation
2025-04-09 15:04:45 +02:00
Pere Diaz Bou
0f59fc7e36
Merge 'Decrease page count on balancing fixes' from Pere Diaz Bou
...
* Comment how decrease of pages happen while balancing
* Free pages no longer used after balancing finished.
Reviewed-by: Jussi Saurio <jussi.saurio@gmail.com>
Closes #1278
2025-04-09 15:04:25 +02:00
Pere Diaz Bou
f1df09ffd9
free no longer used pages after balance
2025-04-09 11:12:39 +02:00
Jussi Saurio
aa6e2d853a
Merge 'Support backwards index scan and seeks + utilize indexes in removing ORDER BY' from Jussi Saurio
...
## Main stuff
- Support iterating an index backwards
- Support scanning an index (instead of seeking with a condition)
- Support backwards index seeks
- Support backwards rowid seeks
- Fix existing backwards iteration logic for table btrees
- Remove ORDER BY entirely if any index satisfies the ordering
- Add fuzz tests for rowid seeks, 1 and 2 column index seeks
## Bytecode examples (note the lack of order by sorting):
one column index order by, forwards:
```sql
limbo> explain select first_name from users order by age;
addr opcode p1 p2 p3 p4 p5 comment
---- ----------------- ---- ---- ---- ------------- -- -------
0 Init 0 13 0 0 Start at 13
1 OpenReadAsync 0 2 0 0 table=users, root=2
2 OpenReadAwait 0 0 0 0
3 OpenReadAsync 1 274 0 0 table=age_idx, root=274
4 OpenReadAwait 0 0 0 0
5 RewindAsync 1 0 0 0
6 RewindAwait 1 12 0 0 Rewind table age_idx
7 DeferredSeek 1 0 0 0
8 Column 0 1 1 0 r[1]=users.first_name
9 ResultRow 1 1 0 0 output=r[1]
10 NextAsync 1 0 0 0
11 NextAwait 1 7 0 0
12 Halt 0 0 0 0
13 Transaction 0 0 0 0 write=false
14 Goto 0 1 0 0
```
one column index order by, backwards:
```sql
limbo> explain select first_name from users order by age desc;
addr opcode p1 p2 p3 p4 p5 comment
---- ----------------- ---- ---- ---- ------------- -- -------
0 Init 0 13 0 0 Start at 13
1 OpenReadAsync 0 2 0 0 table=users, root=2
2 OpenReadAwait 0 0 0 0
3 OpenReadAsync 1 274 0 0 table=age_idx, root=274
4 OpenReadAwait 0 0 0 0
5 LastAsync 1 0 0 0
6 LastAwait 1 0 0 0
7 DeferredSeek 1 0 0 0
8 Column 0 1 1 0 r[1]=users.first_name
9 ResultRow 1 1 0 0 output=r[1]
10 PrevAsync 1 0 0 0
11 PrevAwait 1 0 0 0
12 Halt 0 0 0 0
13 Transaction 0 0 0 0 write=false
14 Goto 0 1 0 0
```
rowid seek, backwards:
```sql
limbo> explain select * from users where id < 100 order by id desc;
addr opcode p1 p2 p3 p4 p5 comment
---- ----------------- ---- ---- ---- ------------- -- -------
0 Init 0 19 0 0 Start at 19
1 OpenReadAsync 0 2 0 0 table=users, root=2
2 OpenReadAwait 0 0 0 0
3 Integer 100 11 0 0 r[11]=100
4 SeekLT 0 18 11 0
5 RowId 0 1 0 0 r[1]=users.rowid
6 Column 0 1 2 0 r[2]=users.first_name
7 Column 0 2 3 0 r[3]=users.last_name
8 Column 0 3 4 0 r[4]=users.email
9 Column 0 4 5 0 r[5]=users.phone_number
10 Column 0 5 6 0 r[6]=users.address
11 Column 0 6 7 0 r[7]=users.city
12 Column 0 7 8 0 r[8]=users.state
13 Column 0 8 9 0 r[9]=users.zipcode
14 Column 0 9 10 0 r[10]=users.age
15 ResultRow 1 10 0 0 output=r[1..10]
16 PrevAsync 0 0 0 0
17 PrevAwait 0 0 0 0
18 Halt 0 0 0 0
19 Transaction 0 0 0 0 write=false
20 Goto 0 1 0 0
```
two column order by, setup:
```sql
cargo run dualpk.db
Limbo v0.0.18-pre.3
Enter ".help" for usage hints.
limbo> .schema
CREATE TABLE a(b,c,d,e, primary key (d,c));
```
two column order by, forwards:
```sql
limbo> explain select * from a order by d,c;
addr opcode p1 p2 p3 p4 p5 comment
---- ----------------- ---- ---- ---- ------------- -- -------
0 Init 0 16 0 0 Start at 16
1 OpenReadAsync 0 2 0 0 table=a, root=2
2 OpenReadAwait 0 0 0 0
3 OpenReadAsync 1 3 0 0 table=sqlite_autoindex_a_1, root=3
4 OpenReadAwait 0 0 0 0
5 RewindAsync 1 0 0 0
6 RewindAwait 1 15 0 0 Rewind table sqlite_autoindex_a_1
7 DeferredSeek 1 0 0 0
8 Column 0 0 1 0 r[1]=a.b
9 Column 0 1 2 0 r[2]=a.c
10 Column 0 2 3 0 r[3]=a.d
11 Column 0 3 4 0 r[4]=a.e
12 ResultRow 1 4 0 0 output=r[1..4]
13 NextAsync 1 0 0 0
14 NextAwait 1 7 0 0
15 Halt 0 0 0 0
16 Transaction 0 0 0 0 write=false
17 Goto 0 1 0 0
```
two column order by, forwards with index seek:
```sql
limbo> explain select * from a where d > 100 order by d,c;
addr opcode p1 p2 p3 p4 p5 comment
---- ----------------- ---- ---- ---- ------------- -- -------
0 Init 0 16 0 0 Start at 16
1 OpenReadAsync 0 2 0 0 table=a, root=2
2 OpenReadAwait 0 0 0 0
3 OpenReadAsync 1 3 0 0 table=sqlite_autoindex_a_1, root=3
4 OpenReadAwait 0 0 0 0
5 Integer 100 5 0 0 r[5]=100
6 SeekGT 1 15 5 0
7 DeferredSeek 1 0 0 0
8 Column 0 0 1 0 r[1]=a.b
9 Column 0 1 2 0 r[2]=a.c
10 Column 0 2 3 0 r[3]=a.d
11 Column 0 3 4 0 r[4]=a.e
12 ResultRow 1 4 0 0 output=r[1..4]
13 NextAsync 1 0 0 0
14 NextAwait 1 7 0 0
15 Halt 0 0 0 0
16 Transaction 0 0 0 0 write=false
17 Goto 0 1 0 0
```
two column order by, forwards with index scan and termination condition:
```sql
limbo> explain select * from a where d < 100 order by d,c;
addr opcode p1 p2 p3 p4 p5 comment
---- ----------------- ---- ---- ---- ------------- -- -------
0 Init 0 18 0 0 Start at 18
1 OpenReadAsync 0 2 0 0 table=a, root=2
2 OpenReadAwait 0 0 0 0
3 OpenReadAsync 1 3 0 0 table=sqlite_autoindex_a_1, root=3
4 OpenReadAwait 0 0 0 0
5 Null 0 5 0 0 r[5]=NULL
6 SeekGT 1 17 5 0
7 Integer 100 6 0 0 r[6]=100
8 IdxGE 1 17 6 0
9 DeferredSeek 1 0 0 0
10 Column 0 0 1 0 r[1]=a.b
11 Column 0 1 2 0 r[2]=a.c
12 Column 0 2 3 0 r[3]=a.d
13 Column 0 3 4 0 r[4]=a.e
14 ResultRow 1 4 0 0 output=r[1..4]
15 NextAsync 1 0 0 0
16 NextAwait 1 7 0 0
17 Halt 0 0 0 0
18 Transaction 0 0 0 0 write=false
19 Goto 0 1 0 0
```
two column order by, backwards:
```sql
limbo> explain select * from a order by d desc,c desc;
addr opcode p1 p2 p3 p4 p5 comment
---- ----------------- ---- ---- ---- ------------- -- -------
0 Init 0 16 0 0 Start at 16
1 OpenReadAsync 0 2 0 0 table=a, root=2
2 OpenReadAwait 0 0 0 0
3 OpenReadAsync 1 3 0 0 table=sqlite_autoindex_a_1, root=3
4 OpenReadAwait 0 0 0 0
5 LastAsync 1 0 0 0
6 LastAwait 1 0 0 0
7 DeferredSeek 1 0 0 0
8 Column 0 0 1 0 r[1]=a.b
9 Column 0 1 2 0 r[2]=a.c
10 Column 0 2 3 0 r[3]=a.d
11 Column 0 3 4 0 r[4]=a.e
12 ResultRow 1 4 0 0 output=r[1..4]
13 PrevAsync 1 0 0 0
14 PrevAwait 1 0 0 0
15 Halt 0 0 0 0
16 Transaction 0 0 0 0 write=false
17 Goto 0 1 0 0
```
two column order by, backwards with index seek:
```sql
limbo> explain select * from a where d < 100 order by d desc,c desc;
addr opcode p1 p2 p3 p4 p5 comment
---- ----------------- ---- ---- ---- ------------- -- -------
0 Init 0 16 0 0 Start at 16
1 OpenReadAsync 0 2 0 0 table=a, root=2
2 OpenReadAwait 0 0 0 0
3 OpenReadAsync 1 3 0 0 table=sqlite_autoindex_a_1, root=3
4 OpenReadAwait 0 0 0 0
5 Integer 100 5 0 0 r[5]=100
6 SeekLT 1 15 5 0
7 DeferredSeek 1 0 0 0
8 Column 0 0 1 0 r[1]=a.b
9 Column 0 1 2 0 r[2]=a.c
10 Column 0 2 3 0 r[3]=a.d
11 Column 0 3 4 0 r[4]=a.e
12 ResultRow 1 4 0 0 output=r[1..4]
13 PrevAsync 1 0 0 0
14 PrevAwait 1 0 0 0
15 Halt 0 0 0 0
16 Transaction 0 0 0 0 write=false
17 Goto 0 1 0 0
```
two column order by, backwards with index scan and termination
condition:
```sql
limbo> explain select * from a where d > 100 order by d desc,c desc;
addr opcode p1 p2 p3 p4 p5 comment
---- ----------------- ---- ---- ---- ------------- -- -------
0 Init 0 18 0 0 Start at 18
1 OpenReadAsync 0 2 0 0 table=a, root=2
2 OpenReadAwait 0 0 0 0
3 OpenReadAsync 1 3 0 0 table=sqlite_autoindex_a_1, root=3
4 OpenReadAwait 0 0 0 0
5 LastAsync 1 0 0 0
6 LastAwait 1 0 0 0
7 Integer 100 6 0 0 r[6]=100
8 IdxLE 1 17 6 0
9 DeferredSeek 1 0 0 0
10 Column 0 0 1 0 r[1]=a.b
11 Column 0 1 2 0 r[2]=a.c
12 Column 0 2 3 0 r[3]=a.d
13 Column 0 3 4 0 r[4]=a.e
14 ResultRow 1 4 0 0 output=r[1..4]
15 PrevAsync 1 0 0 0
16 PrevAwait 1 0 0 0
17 Halt 0 0 0 0
18 Transaction 0 0 0 0 write=false
19 Goto 0 1 0 0
```
Reviewed-by: Preston Thorpe (@PThorpe92)
Closes #1209
2025-04-09 12:03:14 +03:00
Pere Diaz Bou
edc3a420fb
comment how page count is decreased while balancing
2025-04-09 11:02:49 +02:00
Jussi Saurio
0888c71ba0
use seek() instead of do_seek() to set iteration state
2025-04-09 10:26:02 +03:00
Jussi Saurio
5e3a37a192
Try to name iteration direction sensitive method better
2025-04-09 10:14:29 +03:00
Jussi Saurio
0bb87b060a
Fix existing table btree backwards iteration logic
2025-04-09 10:14:29 +03:00
Jussi Saurio
f5220d281d
Fix off-by-one logic in btree table traversal
2025-04-09 10:14:29 +03:00
Jussi Saurio
fa295af635
Fix insert fuzz test by bypassing internal invariant
2025-04-09 10:14:29 +03:00
Jussi Saurio
c9190236f0
btree: support backwards index seeks and iteration
2025-04-09 10:14:29 +03:00
Pere Diaz Bou
ce7e0188f6
bring back i64 page sizes while balancing
2025-04-08 17:57:39 +02:00
Pere Diaz Bou
cf62099bf5
allow insertion of multiple overflow cells
2025-04-08 16:43:15 +02:00
Pere Diaz Bou
029da5c81c
Improve readability of balance_non_root with comments and validation extraction
2025-04-08 16:43:15 +02:00
Pere Diaz Bou
fded6ccaf3
rever iterations fuzz test
2025-04-08 14:09:17 +02:00
Pere Diaz Bou
c0c66bf8af
remove wrong comment
2025-04-08 14:06:48 +02:00
Pere Diaz Bou
8c4003908f
bring back usize, it shouldn't underflow
2025-04-08 14:05:30 +02:00
Pere Diaz Bou
40f8bbe132
clippy
2025-04-08 11:31:38 +02:00
Pere Diaz Bou
8e88b0cd14
new_page_sizes as Vec<i64>
2025-04-08 11:31:38 +02:00
Pere Diaz Bou
3950ab1e52
account for divider cell size in page size
2025-04-08 11:31:38 +02:00
Pere Diaz Bou
6086284613
fix debug imports
2025-04-07 18:06:52 +02:00
Pere Diaz Bou
83f13596a4
decrease fuzz test steps again
2025-04-07 18:01:08 +02:00
Pere Diaz Bou
f137ddfdf8
add loop left pointer validation
2025-04-07 18:01:08 +02:00
Pere Diaz Bou
6ac2368ae2
update divider cell that is being balanced
2025-04-07 18:00:49 +02:00
Pere Diaz Bou
0541da46df
add strict btree validation after non root balancing in debug mode
2025-04-07 18:00:49 +02:00
Pere Diaz Bou
ff8ec5455c
fix divider cell selection
2025-04-07 18:00:30 +02:00
Pere Diaz Bou
9eb9e7021e
Fix index table new divider cell pointer
2025-04-07 18:00:30 +02:00
Pere Diaz Bou
f4920cb96b
assert new divider cell points to the correct place
2025-04-07 18:00:30 +02:00
Pere Diaz Bou
15ed7642c9
check all keys are present on every insert with fuzz test
...
Let's make sure every insert does still contain all keys. Previously we
did this at the end but it made it hard to debug issues that
`validate_btree` might not encounter.
2025-04-07 18:00:30 +02:00
PThorpe92
bd04b10f17
Fix btree tests to adapt to new type for BTreeKey
2025-04-05 11:19:10 -04:00
PThorpe92
abc97c8774
Add doc comments to new btree key enum and remove unused lifetimes
2025-04-05 11:19:10 -04:00
PThorpe92
6b42808f1a
Dont re-seek if we are inserting a new unique index
2025-04-05 11:19:10 -04:00
PThorpe92
068ab4ab27
Refactor btree to reuse existing insert and seek with idx keys
2025-04-05 11:19:09 -04:00
PThorpe92
007fbe8cc7
Fix unique index issue and prealloc in sql string for schema
2025-04-05 11:19:09 -04:00
PThorpe92
2c3fd509fe
Remove unused imports and consolidate ordering comparison
2025-04-05 11:19:09 -04:00
PThorpe92
b0016a0ee2
Support create index with SeekEnd and IdxCreate opcode functionality
2025-04-05 11:15:36 -04:00
TcMits
56fa9049c3
fix: overflow pos in write_page
2025-04-03 15:02:53 +07:00
Pekka Enberg
ed1854c8de
Merge 'Request load page on insert_into_page' from Pere Diaz Bou
...
We assumed page was loaded because before inserting we would move there.
`NewRowId` unfortunately moves cursor to the rightmost page causing
eviction of root page -- this arose the issue with `insert_into_page`
not loading the page we were supposed to have loaded so I added
`return_if_locked_maybe_load` which is a utility macro to check if the
page is locked and if not, load it if needed.
Closes #1138
2025-04-02 18:52:25 +03:00
Pere Diaz Bou
5dedc68fda
remove arc import
2025-04-02 16:56:34 +02:00
Pere Diaz Bou
e85fb86ff4
Request load page on insert_into_page
...
We assumed page was loaded because before inserting we would move there. `NewRowId` unfortunately moves cursor to the rightmost page causing eviction of root page -- this arose the issue with `insert_into_page` not loading the page we were supposed to have loaded so I added `return_if_locked_maybe_load` which is a utility macro to check if the page is locked and if not, load it if needed.
2025-04-02 16:24:53 +02:00
