Memory issue with large queries

[alex-statsig]

Describe the bug
When formatting a large query containing thousands of ids (5,000-10,000+), the formatter uses a very large amount of memory, often OOMing the process.

Expected behavior
While this is a rather large query to deal with, many query engines can handle it fine. The memory consumption to format a <100kB query should not consume GBs of RAM

Actual behavior
The formatting function consumed RAM of nearly 50,000x the original query length

Usage

Here's an example script which generates two similar types of queries which both run into the issue:

const values = Array(10000).fill('myid')

// Large "in" clause
const sql = `SELECT * FROM my_table WHERE col in (${values.map((v) => "'" + v + "'").join(",")})`
// Large number of "or" clauses
// const sql = `SELECT * FROM my_table WHERE (${values.map((v) => "col = '" + v + "'").join(" OR ")})`
const {format} = require('sql-formatter')
const formatted = format(sql, {language: 'sql'})
console.log(Math.round(process.memoryUsage().heapUsed / 1024 / 1024) + " MB")

The first query uses 1.5GB of memory, and the second OOMs with 4GB of memory

[nene]

Thanks for reporting.

Turns out that the problem is caused by the parser. Most likely by the way the grammar is written. Unfortunately that whole "grammar" is more of one big hack to gather some data about the structure of SQL without actually understanding the proper structure of it.

I reduced the grammar down to just match the SELECT <ident>, ... syntax:

main -> statement:+ 

statement -> select_clause (%DELIMITER | %EOF)

select_clause -> %RESERVED_SELECT (identifier | comma):+ 

comma -> %COMMA

identifier -> %IDENTIFIER

and strangely enough even this simple grammar performs just as badly. But when I rewrite the select_clause rule to:

select_clause -> %RESERVED_SELECT identifier (comma identifier):+

the memory usage drops to more sensible levels. However at the same time the running time jumps from 3 to 9 seconds!?!?!

I'm really at my wits end here. There are a bunch of memory usage issues reported to Nearley parser. So this might be related to that.

You might want to instead give a try to prettier-plugin-sql-cst where I'm using a different parser engine. I haven't tested this specific case with it though.