Opportunities for performance optimization

[krishvishal]

Hi, I've been going through SQLite source code and docs, and have compared it with lemon-rs implementation. I want to get your thoughts on my ideas.

• SQLite uses lookaside buffers to allocate many small objects such as parse tree nodes in them, avoiding many calls to malloc and free. There are many calls to the function sqlite3DbMallocRaw in many objects' initialization.

• Currently the enum YYMINORTYPE has many complex variants inside it and also a few heap allocated objects as well. Due to this all variants in the enum smaller variants will also occupy size of the largest variant. One optimization could be split the enum into SmallYYMINORTYPE and BigYYMINORTYPE and group the variants appropriately. This article goes into a deeper discussion on this issue.

I propose that we use an arena allocator like bumpalo to ameliorate the cost of heap allocs. This will also increase cache locality because all the objects are allocated in a contiguous region and also reduces the calls to malloc.

I was thinking of an API like the following

let sql = "SELECT 1".into_owned();
let bump = Bump::new();
parser = Parser::new(sql, &bump);

We will use the bump allocator to allocate short lived but large objects and this will also allocate sufficiently large memory in the beginning of the parsing and free all at once at the end.

[gwenn]

You cannot easily compare SQLite parsing which mainly generates bytecode (Vdbe).
Versus lemon-rs which generates an AST.

Another way to avoid (some) allocations would be #33: almost no String, only Span to initial input.
And we might be able to reduce the YYMINORTYPE size by boxing some part of the AST: #8

[krishvishal]

Thank you for the pointers I will look into them.

Boxing part of AST seems easier, I will look into it.

[gwenn]

https://github.com/apache/datafusion-sqlparser-rs/blob/main/Cargo.toml doesn't seem to use any specific allocator.

[krishvishal]

Using arena allocator for parsing seems to be a common pattern in many applications that do parsing. That is why I have suggested that we use it.

Some examples:

[1] - https://stellate.co/blog/graphql-query-parsing-8x-faster-with-rust - wrote a parser for GraphQL in rust that's faster than previous rust parser because they used arenas.
[2] - https://iliabylich.github.io/arena-based-parsers/tldr.html - rewrote parser for Ruby lang using arenas and got 2x speedup.
[3] - https://rustc-dev-guide.rust-lang.org/memory.html#arenas-and--interning - rustc compiler uses arena
[4] - https://www.enterprisedb.com/blog/exploring-postgress-arena-allocator-writing-http-server-scratch
[5] - https://www.cybertec-postgresql.com/en/memory-context-for-postgresql-memory-management/