Files
325d5b08b4 enhance: speed up expr parsing with SLL-first two-stage ANTLR prediction (#50782)
issue: #50781

## What this PR does

Two parse-path enhancements in `internal/parser/planparserv2` (no
grammar regeneration, no public API change):

- **SLL-first two-stage parse** (`parseExpr`): parse with
`PredictionModeSLL` first; only if SLL cannot decide, rewind the token
buffer and reparse with full `PredictionModeLL` + default recovery. A
clean SLL parse is provably identical to a pure-LL parse.
- **Drop ANTLR's default `ConsoleErrorListener`** in the pooled
lexer/parser so a syntax error no longer does stderr I/O on the hot
failure path.

Note: `antlr-go` v4.13.1 (and upstream `dev`) ship `BailErrorStrategy`
with an unimplemented `ParseCancellationException` (`panic("implement
me")`), so the standard bail-based two-stage cannot be used; "SLL could
not decide" is detected via a probe error listener instead.

## Performance — the win is concentrated, not uniform

Parse-only (lex+parse, AST cache bypassed), separate cold-start
processes, min of repeated runs (GC-noise filtered). The honest
per-expression picture:

| expression class | example | LL → TS | allocs/op |
|---|---|---|---|
| **range compare `a<x<b`** | `10 < Int64Field < 100` | **~58000 → ~8700
ns (~7× faster)** | **1295 → 184** |
| equality / comparison | `Int64Field == 100` | ~neutral (±2%) | 175 →
177 |
| `in`, `like`, `is null`, JSON, `&&`/`||` | `StringField like "x%"` |
~neutral (±2%) | +2 |
| large `in[...]`, bitwise, deep logical | — | ~neutral (±3%) | ~equal |

The grammar's `Range`/`ReverseRange` alternatives are ambiguous with
nested `Relational`, which drives ANTLR's full-LL prediction into a
pathological path (1295 allocs for one `a<x<b`). SLL resolves it
directly. **That single class accounts for essentially all of the
aggregate gain (~-19% ns/op, -21% allocs across a 144-expression
corpus); every other expression class is within measurement noise of
LL.** The only added cost is one ~40-byte allocation per parse (the
probe listener).

So this is high value if range filters (`10 < age < 100`) are common in
the workload, and neutral otherwise — not a uniform speedup.

## Correctness

The SLL two-stage parse is verified to produce the **exact same parse
tree** as a pure-LL parse, compared structurally via
`antlr.TreesStringTree` (an S-expression that encodes nesting — unlike
`GetText()`, which only concatenates leaf tokens and cannot detect a
precedence/associativity divergence). Verified across:
- the existing benchmark corpus (`TestTwoStageMatchesLL`),
- ~106 valid expressions, simple → complex, covering comparisons,
arithmetic/bitwise/shift/unary/power, ranges, IN, string/like/regex,
arrays, JSON, struct fields, null/exists, text/phrase/match_*,
random_sample, spatial `st_*`, timestamptz (which exercises the SLL→LL
fallback), template variables, calls and deep nesting
(`TestTwoStageMatchesLL_Corpus`),
- 13 malformed expressions, rejected identically by both strategies
(`TestTwoStageMatchesLL_Invalid`).

Full `planparserv2` package test suite passes;
`gofumpt`/`gci`/`golangci-lint` clean.

## Evaluated and rejected

Moving the two leading `Timestamptz*` `expr` alternatives out of the
grammar was measured to change parse time by **<1%** with identical
allocations (the DFA caches the decision after first use), so it is
intentionally **not** included.

/kind enhancement

---------

Signed-off-by: xiaofanluan <xf@hjjaq.com>
Co-authored-by: xiaofanluan <xf@hjjaq.com>
Co-authored-by: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
2026-06-30 00:44:29 +08:00

87 lines
2.5 KiB
Go

package planparserv2
import (
"sync"
"github.com/antlr4-go/antlr/v4"
antlrparser "github.com/milvus-io/milvus/internal/parser/planparserv2/generated"
)
var (
lexerPool = sync.Pool{
New: func() interface{} {
return antlrparser.NewPlanLexer(nil)
},
}
parserPool = sync.Pool{
New: func() interface{} {
return antlrparser.NewPlanParser(nil)
},
}
)
func getLexer(stream *antlr.InputStream, listeners ...antlr.ErrorListener) *antlrparser.PlanLexer {
lexer := lexerPool.Get().(*antlrparser.PlanLexer)
// Drop ANTLR's default ConsoleErrorListener (see getParser).
lexer.RemoveErrorListeners()
for _, listener := range listeners {
lexer.AddErrorListener(listener)
}
lexer.SetInputStream(stream)
return lexer
}
func getParser(lexer *antlrparser.PlanLexer, listeners ...antlr.ErrorListener) *antlrparser.PlanParser {
tokenStream := antlr.NewCommonTokenStream(lexer, antlr.TokenDefaultChannel)
parser := parserPool.Get().(*antlrparser.PlanParser)
// Drop ANTLR's default ConsoleErrorListener so a syntax error does not do
// stderr I/O on the hot failure path; only our own listener stays attached.
parser.RemoveErrorListeners()
for _, listener := range listeners {
parser.AddErrorListener(listener)
}
parser.BuildParseTrees = true
parser.SetInputStream(tokenStream)
// Hand the parser out in the default LL prediction mode. parseExpr flips it to
// SLL for stage 1 and only restores LL on the (rare) stage-2 path, so a parser
// returned to the pool after a clean stage-1 parse is still in SLL mode —
// antlr-go's SetInputStream/reset does not restore predictionMode. Reset it
// here so the pool always yields an LL parser and any caller that runs the
// pooled parser directly (e.g. parser.Expr() in tests/benchmarks) never
// inherits SLL-only behavior that could reject inputs full LL accepts.
parser.GetInterpreter().SetPredictionMode(antlr.PredictionModeLL)
return parser
}
func putLexer(lexer *antlrparser.PlanLexer) {
lexer.SetInputStream(nil)
lexer.RemoveErrorListeners()
lexerPool.Put(lexer)
}
func putParser(parser *antlrparser.PlanParser) {
parser.SetInputStream(nil)
parser.RemoveErrorListeners()
parserPool.Put(parser)
}
// resetLexerPool resets the lexer pool (for testing)
func resetLexerPool() {
lexerPool = sync.Pool{
New: func() interface{} {
return antlrparser.NewPlanLexer(nil)
},
}
}
// resetParserPool resets the parser pool (for testing)
func resetParserPool() {
parserPool = sync.Pool{
New: func() interface{} {
return antlrparser.NewPlanParser(nil)
},
}
}