You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "LucaCappelletti94 (via GitHub)" <gi...@apache.org> on 2026/05/23 13:47:57 UTC
[PR] Parser: fix exponential parse time on speculative NOT prefix parsing [datafusion-sqlparser-rs]
LucaCappelletti94 opened a new pull request, #2351:
URL: https://github.com/apache/datafusion-sqlparser-rs/pull/2351
`parse_prefix` wraps `parse_expr_prefix_by_reserved_word` in `try_parse`, which speculatively dispatches `parse_not` for the `NOT` keyword. `parse_not`'s inner `parse_subexpr(UnaryNot)` infix-loops through `-`, hits the next `NOT` and recurses, so on chains like `SELECT x-not-b.x-not-b...` ending in a parse error every `NOT` segment re-walks the rest of the chain and `parse_not` is called 2^N - 1 times.
Fix is a per-parse `BTreeSet<usize>` of token positions where the speculative `parse_not` already failed. Subsequent visits at the same position skip the speculation and fall back to identifier interpretation.
| Input | Before | After |
|-------|--------|-------|
| 903 B cursed libFuzzer artifact | ~12 s | ~2.5 ms |
| `SELECT x-not-b.` * 22 | ~11 s | ~1 ms |
| `SELECT x-not-b.` * 30 | (too slow to measure) | ~1.5 ms |
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Parser: fix exponential parse time on speculative NOT prefix parsing [datafusion-sqlparser-rs]
Posted by "LucaCappelletti94 (via GitHub)" <gi...@apache.org>.
LucaCappelletti94 commented on PR #2351:
URL: https://github.com/apache/datafusion-sqlparser-rs/pull/2351#issuecomment-4527766838
Closing as superseded by #2352. The new per-arm `try_parse(reserved_word)` cache in #2352 generalises this PR's NOT-specific cache to all reserved-word prefixes: regression input parses in 948us on the amended branch vs >60s on apache main.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Parser: fix exponential parse time on speculative NOT prefix parsing [datafusion-sqlparser-rs]
Posted by "LucaCappelletti94 (via GitHub)" <gi...@apache.org>.
LucaCappelletti94 closed pull request #2351: Parser: fix exponential parse time on speculative NOT prefix parsing
URL: https://github.com/apache/datafusion-sqlparser-rs/pull/2351
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org