Dolt is the first relational database that supports Git-like versioning. Dolt's content-addressed storage layer plugs into two wire layers, MySQL and

Reducing Yacc Latency by 80%

submited by

Style Pass

2024-10-11 06:00:05

Dolt is the first relational database that supports Git-like versioning. Dolt's content-addressed storage layer plugs into two wire layers, MySQL and now Postgres (DoltgreSQL).

While half of the team works on reaching 100% Postgres compatibility, I continue to chase perf. The topic of today's blog is our Yacc SQL parser.

Parsing is commonly thought to be an insignificant fraction of query time, but as we've made other parts of execution faster, it has crept up to 15% of our small queries:

Today's changes make parsing about 80% faster. On a linux server this translates to about ~30 microseconds of the smallest queries, and ~2% of larger queries with more involved AST structures. Here are a few notable standouts from the sysbench benchmarks:

TPC-C similarly sees about ~2% improvement on the average query, reflected in the 95% percentile tail latency (p95). Because the bulk of TPC-C queries are small selects and inserts, we've gained a 5% boost to the transaction throughput per second (TPS):

Lexing and parsing a query string are the first steps in query planning. Lexing splits a query string into sets of tokens, and parsing builds those tokens into a valid sentence in our SQL grammar as a typed abstract syntax tree (AST).