Poor performance when parsing huge literal in query (e.g. 100MB)

[SimonBin]

The cause seems to be javacc/javacc#72

We encountered this issue when a SPARQL SERVICE clause was sending a large-ish Geometry literal of USA to Fuseki. It stalls forever trying to parse the query.

Ideally, the buffer would expand exponentially or there is an alternative PR linked in the javacc issue. Currently, the parsing buffer is apparently grown in steps of 2KiB

jstack:

"qtp771666241-136" #136 prio=5 os_prio=0 cpu=13385,35ms elapsed=5538,68s tid=0x00007fa188007800 nid=0x15730d runnable  [0x00007fa1341f9000]
   java.lang.Thread.State: RUNNABLE
	at org.apache.jena.sparql.lang.arq.SimpleCharStream.ExpandBuff(SimpleCharStream.java:42)
	at org.apache.jena.sparql.lang.arq.SimpleCharStream.FillBuff(SimpleCharStream.java:103)
	at org.apache.jena.sparql.lang.arq.SimpleCharStream.readChar(SimpleCharStream.java:197)
	at org.apache.jena.sparql.lang.arq.ARQParserTokenManager.jjMoveNfa_0(ARQParserTokenManager.java:4369)
	at org.apache.jena.sparql.lang.arq.ARQParserTokenManager.jjMoveStringLiteralDfa0_0(ARQParserTokenManager.java:211)
	at org.apache.jena.sparql.lang.arq.ARQParserTokenManager.getNextToken(ARQParserTokenManager.java:4793)
	at org.apache.jena.sparql.lang.arq.ARQParser.jj_ntk_f(ARQParser.java:8162)
	at org.apache.jena.sparql.lang.arq.ARQParser.PathElt(ARQParser.java:3603)
	at org.apache.jena.sparql.lang.arq.ARQParser.PathEltOrInverse(ARQParser.java:3635)
	at org.apache.jena.sparql.lang.arq.ARQParser.PathSequence(ARQParser.java:3565)
	at org.apache.jena.sparql.lang.arq.ARQParser.PathAlternative(ARQParser.java:3544)
	at org.apache.jena.sparql.lang.arq.ARQParser.Path(ARQParser.java:3538)
	at org.apache.jena.sparql.lang.arq.ARQParser.VerbPath(ARQParser.java:3493)
	at org.apache.jena.sparql.lang.arq.ARQParser.PropertyListPathNotEmpty(ARQParser.java:3418)
	at org.apache.jena.sparql.lang.arq.ARQParser.TriplesSameSubjectPath(ARQParser.java:3365)
	at org.apache.jena.sparql.lang.arq.ARQParser.TriplesBlock(ARQParser.java:2512)
	at org.apache.jena.sparql.lang.arq.ARQParser.GroupGraphPatternSub(ARQParser.java:2425)
	at org.apache.jena.sparql.lang.arq.ARQParser.GroupGraphPattern(ARQParser.java:2387)
	at org.apache.jena.sparql.lang.arq.ARQParser.WhereClause(ARQParser.java:858)
	at org.apache.jena.sparql.lang.arq.ARQParser.SelectQuery(ARQParser.java:137)
	at org.apache.jena.sparql.lang.arq.ARQParser.Query(ARQParser.java:31)
	at org.apache.jena.sparql.lang.arq.ARQParser.QueryUnit(ARQParser.java:22)
	at org.apache.jena.sparql.lang.ParserARQ$1.exec(ParserARQ.java:48)
	at org.apache.jena.sparql.lang.ParserARQ.perform(ParserARQ.java:95)
	at org.apache.jena.sparql.lang.ParserARQ.parse$(ParserARQ.java:52)
	at org.apache.jena.sparql.lang.SPARQLParser.parse(SPARQLParser.java:33)
	at org.apache.jena.query.QueryFactory.parse(QueryFactory.java:144)
	at org.apache.jena.query.QueryFactory.create(QueryFactory.java:83)
	at org.apache.jena.fuseki.servlets.SPARQLQueryProcessor.execute(SPARQLQueryProcessor.java:251)
	at org.apache.jena.fuseki.servlets.SPARQLQueryProcessor.executeBody(SPARQLQueryProcessor.java:234)
	at org.apache.jena.fuseki.servlets.SPARQLQueryProcessor.execute(SPARQLQueryProcessor.java:213)
	at org.apache.jena.fuseki.servlets.ActionService.executeLifecycle(ActionService.java:58)
	at org.apache.jena.fuseki.servlets.SPARQLQueryProcessor.execPost(SPARQLQueryProcessor.java:83)
	at org.apache.jena.fuseki.servlets.ActionProcessor.process(ActionProcessor.java:34)
	at org.apache.jena.fuseki.servlets.ActionBase.process(ActionBase.java:55)
	at org.apache.jena.fuseki.servlets.ActionExecLib.execActionSub(ActionExecLib.java:125)
	at org.apache.jena.fuseki.servlets.ActionExecLib.execAction(ActionExecLib.java:99)
	at org.apache.jena.fuseki.server.Dispatcher.dispatchAction(Dispatcher.java:164)
	at org.apache.jena.fuseki.server.Dispatcher.process(Dispatcher.java:156)
	at org.apache.jena.fuseki.server.Dispatcher.dispatch(Dispatcher.java:83)
	at org.apache.jena.fuseki.servlets.FusekiFilter.doFilter(FusekiFilter.java:48)
	at org.eclipse.jetty.servlet.FilterHolder.doFilter(FilterHolder.java:202)
	at org.eclipse.jetty.servlet.ServletHandler$Chain.doFilter(ServletHandler.java:1600)
	at org.apache.shiro.web.servlet.ProxiedFilterChain.doFilter(ProxiedFilterChain.java:61)
	at org.apache.shiro.web.servlet.AdviceFilter.executeChain(AdviceFilter.java:108)
	at org.apache.shiro.web.servlet.AdviceFilter.doFilterInternal(AdviceFilter.java:137)
	at org.apache.shiro.web.servlet.OncePerRequestFilter.doFilter(OncePerRequestFilter.java:125)
	at org.apache.shiro.web.servlet.ProxiedFilterChain.doFilter(ProxiedFilterChain.java:66)
	at org.apache.shiro.web.servlet.AdviceFilter.executeChain(AdviceFilter.java:108)
	at org.apache.shiro.web.servlet.AdviceFilter.doFilterInternal(AdviceFilter.java:137)
	at org.apache.shiro.web.servlet.OncePerRequestFilter.doFilter(OncePerRequestFilter.java:125)
	at org.apache.shiro.web.servlet.ProxiedFilterChain.doFilter(ProxiedFilterChain.java:66)
	at org.apache.shiro.web.servlet.AbstractShiroFilter.executeChain(AbstractShiroFilter.java:450)
	at org.apache.shiro.web.servlet.AbstractShiroFilter$1.call(AbstractShiroFilter.java:365)
	at org.apache.shiro.subject.support.SubjectCallable.doCall(SubjectCallable.java:90)
	at org.apache.shiro.subject.support.SubjectCallable.call(SubjectCallable.java:83)
	at org.apache.shiro.subject.support.DelegatingSubject.execute(DelegatingSubject.java:387)
	at org.apache.shiro.web.servlet.AbstractShiroFilter.doFilterInternal(AbstractShiroFilter.java:362)
	at org.apache.shiro.web.servlet.OncePerRequestFilter.doFilter(OncePerRequestFilter.java:125)
	at org.eclipse.jetty.servlet.FilterHolder.doFilter(FilterHolder.java:202)
	at org.eclipse.jetty.servlet.ServletHandler$Chain.doFilter(ServletHandler.java:1600)
	at org.apache.jena.fuseki.servlets.CrossOriginFilter.handle(CrossOriginFilter.java:284)
	at org.apache.jena.fuseki.servlets.CrossOriginFilter.doFilter(CrossOriginFilter.java:247)
	at org.eclipse.jetty.servlet.FilterHolder.doFilter(FilterHolder.java:210)
	at org.eclipse.jetty.servlet.ServletHandler$Chain.doFilter(ServletHandler.java:1600)
	at org.eclipse.jetty.servlet.ServletHandler.doHandle(ServletHandler.java:506)
	at org.eclipse.jetty.server.handler.ScopedHandler.handle(ScopedHandler.java:131)
	at org.eclipse.jetty.security.SecurityHandler.handle(SecurityHandler.java:578)
	at org.eclipse.jetty.server.handler.HandlerWrapper.handle(HandlerWrapper.java:122)
	at org.eclipse.jetty.server.handler.ScopedHandler.nextHandle(ScopedHandler.java:223)
	at org.eclipse.jetty.server.session.SessionHandler.doHandle(SessionHandler.java:1571)
	at org.eclipse.jetty.server.handler.ScopedHandler.nextHandle(ScopedHandler.java:221)
	at org.eclipse.jetty.server.handler.ContextHandler.doHandle(ContextHandler.java:1378)
	at org.eclipse.jetty.server.handler.ScopedHandler.nextScope(ScopedHandler.java:176)
	at org.eclipse.jetty.servlet.ServletHandler.doScope(ServletHandler.java:463)
	at org.eclipse.jetty.server.session.SessionHandler.doScope(SessionHandler.java:1544)
	at org.eclipse.jetty.server.handler.ScopedHandler.nextScope(ScopedHandler.java:174)
	at org.eclipse.jetty.server.handler.ContextHandler.doScope(ContextHandler.java:1300)
	at org.eclipse.jetty.server.handler.ScopedHandler.handle(ScopedHandler.java:129)
	at org.eclipse.jetty.server.handler.gzip.GzipHandler.handle(GzipHandler.java:717)
	at org.eclipse.jetty.server.handler.HandlerWrapper.handle(HandlerWrapper.java:122)
	at org.eclipse.jetty.server.Server.handle(Server.java:562)
	at org.eclipse.jetty.server.HttpChannel.lambda$handle$0(HttpChannel.java:505)
	at org.eclipse.jetty.server.HttpChannel$$Lambda$636/0x000000084084d040.dispatch(Unknown Source)
	at org.eclipse.jetty.server.HttpChannel.dispatch(HttpChannel.java:762)
	at org.eclipse.jetty.server.HttpChannel.handle(HttpChannel.java:497)
	at org.eclipse.jetty.server.HttpConnection.onFillable(HttpConnection.java:282)
	at org.eclipse.jetty.io.AbstractConnection$ReadCallback.succeeded(AbstractConnection.java:319)
	at org.eclipse.jetty.io.FillInterest.fillable(FillInterest.java:100)
	at org.eclipse.jetty.io.SelectableChannelEndPoint$1.run(SelectableChannelEndPoint.java:53)
	at org.eclipse.jetty.util.thread.strategy.AdaptiveExecutionStrategy.runTask(AdaptiveExecutionStrategy.java:412)
	at org.eclipse.jetty.util.thread.strategy.AdaptiveExecutionStrategy.consumeTask(AdaptiveExecutionStrategy.java:381)
	at org.eclipse.jetty.util.thread.strategy.AdaptiveExecutionStrategy.tryProduce(AdaptiveExecutionStrategy.java:268)
	at org.eclipse.jetty.util.thread.strategy.AdaptiveExecutionStrategy.lambda$new$0(AdaptiveExecutionStrategy.java:138)
	at org.eclipse.jetty.util.thread.strategy.AdaptiveExecutionStrategy$$Lambda$624/0x0000000840830c40.run(Unknown Source)
	at org.eclipse.jetty.util.thread.ReservedThreadExecutor$ReservedThread.run(ReservedThreadExecutor.java:407)
	at org.eclipse.jetty.util.thread.QueuedThreadPool.runJob(QueuedThreadPool.java:894)
	at org.eclipse.jetty.util.thread.QueuedThreadPool$Runner.run(QueuedThreadPool.java:1038)
	at java.lang.Thread.run(java.base@11.0.15/Thread.java:829)

query is something simple as

{ ?c ^<http://www.opengis.net/ont/geosparql#sfContains> "<?xml version=\"1.0\" encoding=\"UTF-8\"?><gml:MultiSurface xmlns:gml=\"http://www.opengis.net/ont/gml\" gml:id=\"g2015_2014_0.104.wkb_geometry\" srsDimension=\"2\" srsName=\"urn:ogc:def:crs:EPSG::3857\"><gml:surfaceMember><gml:Polygon gml:id=\"g2015_2014_0.104.wkb_geometry.1\"><gml:exterior><gml:LinearRing><gml:posList>HUGE POS LIST</gml:posList></gml:LinearRing></gml:exterior></gml:Polygon></gml:surfaceMember></gml:MultiSurface>"^^<http://www.opengis.net/ont/geosparql#gmlLiteral> }

automatically injected from a service clause

[afs]

Reading the JavaCC issue, it seems the query size is not the problem.

It is the presence of large tokens over 2048 bytes.

@SimonBin Is that correct?

SimpleCharStream and JavaCharStream are not Jena code. They are generated by JavaCC. They are committed to the codebase so people building Jena do not need to install JavaCC themselves.

[SimonBin]

Yes I believe this is correct

[afs]

I don't see a PR on the javacc issue that is suitable.

There is an interesting suggestion about lexical states. ARQ only parses from strings, not streams, and only from data already already converted UTF-8. Access to the input would enable slicing literals direly out of the string.

Rather than disrupt the existing processing, it could be done with a new token e.g. X"....".

USER_CHAR_STREAM is also an option.

There is some investigation to do such as updating for Javacc 7.0 (the Jena codebase files were produced from JavaCC 6.0). #1328.

FYI: The different parsers use different techniques to handle unicode and it is in some tests about surrogate pairs.

[SimonBin]

I tried to regenerate the grammars with javacc/javacc#85 applied, as that sounds promising. (you can check the code here: AKSW@95c41d2 ) but there seems to be a bug in javacc/javacc#85 which makes the parsing fail with ContentIllegalInProlog

[afs]

javacc/javacc#85 has not been integrated into javacc releases.

Jena running it's own fork of javacc is highly undesirable - it's technical debt. Users must be able to build Jena and while we ship the generated code in a Jena release so uses don't have to run javacc themselves (e.g. only old versions are available in Ubuntu app repos) they should be able to.

I'm not even sure javacc/javacc#85 is the right solution - it has access overhead. Maybe that's why ArrayList grows by 1.5 each step.

The case of 100Mb literals in a query is not mainstream 😄 . (Maybe search by SHA512?)

#1328 (JavaCC 7.0 upgrade) is in Jena/main.

(Background: the main RIOT parsers do not use JavaCC.)

ContentIllegalInProlog is an XML error. Maybe it should not have the ?xml part. RDF XML Literals do not have the <?xml>.
If you change your example to an rdf:XMLLiteral, there is a warning.

[SimonBin]

nb JavaCC 7 does not influence this performance

[LorenzBuehmann]

The case of 100Mb literals in a query is not mainstream smile . (Maybe search by SHA512?)

True.
But to give some background (why SHA512 is not a workaround here): we're currently trying to make use of GeoSPARQL in our projects, we gathered boundaries/borders of administrative regions from an external dataset provided as GML (which in fact is XML) - for USA the polygon is ~100MB, we tried to deal with this initially, spotted the limitation in Jena, and of course in the meantime simplified the polygon directly via SPARQL query function call (with some custom Jena function unfortunately, GeoSPARQL standard lacks a lots of quite things people in my opinion would be happy to have - good thing, we can extend Jena for our work)

[afs]

Does quite explain why there is a 100Mb literal in a query but no matter.

SPARQL parsing is central so any changes need to be done carefully, and be proven and mature. Like javacc, I'm thinking about unforeseen consequences.

The parser to use is (surprise!) controlled by a registry SPARQLParserRegistry so extension code can change the parser for an experimental one.

Also --

The jaavcc issue suggests a different approach which is also more efficient - lexical states and lexical actions. The string for token image can be created directly without going through the javacc buffering.

[LorenzBuehmann]

Fair. But even if we cannot fix this - also given that it's more a corner case with literals in MB scale and beyond - we wanted to at least report this behavior - could be a good FAQ entry or the like.
Luckily, in our case we own both Fuseki instances A (with the polygons) and B (with the points), thus, we indeed switched the direction, gathering the polygon via a SERVICE request from A and doing the point in polygon check in B compared to passing the polygon from A to B to make the point in polygon check via the SERVICE request.

[afs]

Yes, good to report.

It might be more of an issue in INSERT DATA although then there is usually the option of POSTing RDF.

Fuseki has "Fuseki modules" so adding a modified parser does not require a complete rebuild.

Or in this case the plain Jena initialization that can modify the server.

The lexical actions approach looks interesting.

[new-javacc]

Do you have an actual test case and the grammar somewhere I can look? I'm curious.

[new-javacc]

javacc/javacc#85 has not been integrated into javacc releases.

Jena running it's own fork of javacc is highly undesirable - it's technical debt. Users must be able to build Jena and while we ship the generated code in a Jena release so uses don't have to run javacc themselves (e.g. only old versions are available in Ubuntu app repos) they should be able to.

Not sure why you needed to fork. Let me know if there is something that I can do to help with that. If the issue is with CharStream, just set USER_CHAR_STREAM=true and write your own stream class that does better buffer management. But like I said most often it's grammar inefficiencies that manifest this way. And use ideas like lexical states to more elegantly handling huge tokens.

I'm not even sure javacc/javacc#85 is the right solution - it has access overhead. Maybe that's why ArrayList grows by 1.5 each step.

Not sure what this is. I don't think we merged into main I will check.

The case of 100Mb literals in a query is not mainstream smile . (Maybe search by SHA512?)

It's not unheard of. But if you expect this to happen even occasionally (as opposed to rarely), you might want to redo your rule for literals. Negation opreator does generate a lot of overhead in terms of state etc.

#1328 (JavaCC 7.0 upgrade) is in Jena/main.

(Background: the main RIOT parsers do not use JavaCC.)

ContentIllegalInProlog is an XML error. Maybe it should not have the ?xml part. RDF XML Literals do not have the <?xml>. If you change your example to an rdf:XMLLiteral, there is a warning.

[afs]

The issue we experience is buffer management. Linear growth of a few Kbytes for 100Mb is a lot of recopying. If it grew at say x1.5 (like a Java ArrayList) the effect would be much less. (The same issues can arise with Arraylist but much less pronounced).

The grammar is the grammar in the SPARQL specification - it really "is the grammar" because the HTML in th spec was produced from this JavaCC grammar!

The negation is only 3 chars ahead maximum.

@SimonBin - is this triple-quoted literals or single-quoted?

In both cases, if the XML uses " for attributes, then a ' quoting may make a difference but I suspect the buffer expansion is going to dominate.