Performant text search in a large number of XML text nodes and decide if a pattern occurs once

Admin 1
Viewed 162

I have XML files with size about 50MB to a maximum of 2GB with tens or hundreds of thousands of mycomment elements that have only a text node. The path to mycomment node is not fix and not defined and thus //mycomment is the only way to get all of them. Length of mycomment/text() is about 50 to 500 chars. I need to search for one pattern in all mycomment text nodes in order to categorize the file. If pattern " mypattern1234 " is found in one of the text nodes variable hit is set to 1 else it is empty. Is it a good solution to calculate hit like this:

  <xsl:variable name="hit">
    <xsl:if test="//mycomment[contains(text(),' mypattern1234 ')]">1</xsl:if>
  </xsl:variable>

:-) I'm using XSLT v1.0. Thank you.

xslt-1.0 xslt search
4 Answers

You're not going to be able to handle a 2GB input document unless you switch to a streaming XSLT 3.0 processor such as Saxon-EE.

If you're using a streaming processor then I would suggest doing it as

<xsl:source-document href="input.xml" streamable="yes">
  <xsl:if test="//text()[parent::comment][contains(.,' mypattern1234 ')]>1</xsl:if>
</xsl:source-document>

It's a bit less overhead to only look at the text nodes and then examine their context, rather than to matching the element nodes and then setting up a search for the child text nodes.

I would expect a 2Gb search to run in about a minute, depending on your hardware. However, the scan of the source document should stop as soon as a match is found, so if you find a match near the start of the document it will be much faster than this.

user_4154480

It is not clear whether the mycomment elements can have mixed contents or text nodes interleaved with comments or processing instructions. Normally, if you expect the mycomment elements to only have text content, I would check on mycomment[contains(., ' foo ')], there is no need to select down to text node children. If you want to do that, then I would use mycomment/text()[contains(., ' foo ')], your check of text() as the argument to contains would select the first text child node, so in e.g. <mycomment>foo <!-- a comment --> mypattern1234 </mycomment> the text would not be detected.

As for efficiency, that will depend very much on the XSLT processor used.

user_2522280

Aside from XML technologies ripgrep makes searching orders of magnitude faster:

#!/bin/zsh

DATABASE="$1"
SEARCH_PATTERN="$2"

if [ "${#SEARCH_PATTERN}" != 0 ] && [ "${#DATABASE}" != 0 ] ; then

RAWHIT=`rg -C 5 "$SEARCH_PATTERN" "$DATABASE"`

if [ "${#RAWHIT}" != 0 ] ; then
HIT=`echo $RAWHIT | rg -c -U "<comment>.*$SEARCH_PATTERN.*</comment>"`
if [ "${#HIT}" != 0 ] ; then
    echo "Pattern found"
else
    echo "Pattern not found"
fi 
else
    echo "Pattern not found"
fi
else
    echo "Missing Search Pattern or Database"
fi

Running and time measurement on i5 platform:

> time ./run.sh DB50C1000000P.xml Foo4711
Pattern found
./run.sh DB50C1000000P.xml Foo4711  0,23s user 0,58s system 98% cpu 0,828 total

> time ./run.sh DB50C1000000P.xml Foo4711a
Pattern not found
./run.sh DB50C1000000P.xml Foo4711a  0,23s user 0,59s system 98% cpu 0,829 total

Database download: Database

Admin1

Comparing the techniques - XPath with XQuery or XSLT and ripgrep:

  • Solution 1 (M.H.): //comment[contains(.,'searchpattern')]
  • Solution 2 (M.S.): //comment[contains(text(),'searchpattern')]
  • Solution 3 (M.K.): //text()[parent:comment][contains(.,'searchpattern')]

Platform:

MacBook, i5, macOS v10.15.4, 16GB RAM

XML Database:

Size: 2.46GB

Number of comment element nodes (have a single text node where the pattern will be searched) = 5914102

Number of other element nodes (not comment) = 11829597

XQuery v3.1, BaseX v9.3.2

 > time java -Xmx10g -cp /Users/ms/Projekte/basex/BaseX.jar org.basex.BaseX -bsolution=1 -bdatabase=DB50C1000000P -bpattern=Foo4711 run.xqy
 Solution 1: Pattern found
 java -Xmx10g -cp /Users/ms/Projekte/basex/BaseX.jar org.basex.BaseX    run.xq  28,96s user 2,82s system 188% cpu 16,826 total

 > time java -Xmx10g -cp /Users/ms/Projekte/basex/BaseX.jar org.basex.BaseX -bsolution=1 -bdatabase=DB50C1000000P -bpattern=Foo4711a run.xqy
 Solution 1: Pattern not found
 java -Xmx10g -cp /Users/ms/Projekte/basex/BaseX.jar org.basex.BaseX    run.xq  42,62s user 4,05s system 140% cpu 33,233 total

 > time java -Xmx10g -cp /Users/ms/Projekte/basex/BaseX.jar org.basex.BaseX -bsolution=2 -bdatabase=DB50C1000000P -bpattern=Foo4711 run.xqy 
 Solution 2: Pattern found
 java -Xmx10g -cp /Users/ms/Projekte/basex/BaseX.jar org.basex.BaseX    run.xq  29,25s user 2,70s system 196% cpu 16,271 total

 > time java -Xmx10g -cp /Users/ms/Projekte/basex/BaseX.jar org.basex.BaseX -bsolution=2 -bdatabase=DB50C1000000P -bpattern=Foo4711a run.xqy
 Solution 2: Pattern not found
 java -Xmx10g -cp /Users/ms/Projekte/basex/BaseX.jar org.basex.BaseX    run.xq  47,45s user 4,84s system 143% cpu 36,341 total

 > time java -Xmx10g -cp /Users/ms/Projekte/basex/BaseX.jar org.basex.BaseX -bsolution=3 -bdatabase=DB50C1000000P -bpattern=Foo4711 run.xqy
 Solution 3: Pattern found
 java -Xmx10g -cp /Users/ms/Projekte/basex/BaseX.jar org.basex.BaseX    run.xq  30,09s user 2,70s system 195% cpu 16,773 total

 > time java -Xmx10g -cp /Users/ms/Projekte/basex/BaseX.jar org.basex.BaseX -bsolution=3 -bdatabase=DB50C1000000P -bpattern=Foo4711a run.xqy
 Solution 3: Pattern not found
 java -Xmx10g -cp /Users/ms/Projekte/basex/BaseX.jar org.basex.BaseX    run.xq  45,42s user 4,32s system 148% cpu 33,413 total

XSLT v3.0, SaxonEE v9-9-1-7J

 > time java -Xmx10g -jar /Users/ms/Projekte/SaxonEE9-9-1-7J/saxon9ee.jar  -s:empty.xml -xsl:run.xsl -o:out.xml database=DB50C1000000P.xml pattern=Foo4711 solution=1 
 Solution 1: Pattern found
 java -Xmx10g -jar /Users/ms/Projekte/SaxonEE9-9-1-7J/saxon9ee.jar -s:empty.xm  27,43s user 5,88s system 134% cpu 24,719 total

 > time java -Xmx10g -jar /Users/ms/Projekte/SaxonEE9-9-1-7J/saxon9ee.jar  -s:empty.xml -xsl:run.xsl -o:out.xml database=DB50C1000000P.xml pattern=Foo4711a solution=1
 Solution 1: Pattern not found
 java -Xmx10g -jar /Users/ms/Projekte/SaxonEE9-9-1-7J/saxon9ee.jar -s:empty.xm  30,28s user 9,06s system 131% cpu 29,964 total

 > time java -Xmx10g -jar /Users/ms/Projekte/SaxonEE9-9-1-7J/saxon9ee.jar  -s:empty.xml -xsl:run.xsl -o:out.xml database=DB50C1000000P.xml pattern=Foo4711 solution=2 
 Solution 2: Pattern found
 java -Xmx10g -jar /Users/ms/Projekte/SaxonEE9-9-1-7J/saxon9ee.jar -s:empty.xm  27,55s user 4,44s system 158% cpu 20,202 total

 > time java -Xmx10g -jar /Users/ms/Projekte/SaxonEE9-9-1-7J/saxon9ee.jar  -s:empty.xml -xsl:run.xsl -o:out.xml database=DB50C1000000P.xml pattern=Foo4711a solution=2
 Solution 2: Pattern not found
 java -Xmx10g -jar /Users/ms/Projekte/SaxonEE9-9-1-7J/saxon9ee.jar -s:empty.xm  34,47s user 5,24s system 177% cpu 22,324 total

 > time java -Xmx10g -jar /Users/ms/Projekte/SaxonEE9-9-1-7J/saxon9ee.jar  -s:empty.xml -xsl:run.xsl -o:out.xml database=DB50C1000000P.xml pattern=Foo4711 solution=3 
 Solution 3: Pattern found
 java -Xmx10g -jar /Users/ms/Projekte/SaxonEE9-9-1-7J/saxon9ee.jar -s:empty.xm  16,13s user 0,62s system 130% cpu 12,816 total

 > time java -Xmx10g -jar /Users/ms/Projekte/SaxonEE9-9-1-7J/saxon9ee.jar  -s:empty.xml -xsl:run.xsl -o:out.xml database=DB50C1000000P.xml pattern=Foo4711a solution=3
 Solution 3: Pattern not found
 java -Xmx10g -jar /Users/ms/Projekte/SaxonEE9-9-1-7J/saxon9ee.jar -s:empty.xm  47,26s user 1,56s system 110% cpu 44,247 total

Result

Good Case: There is a at least one comment with the search pattern

Fastest (16,13s): Solution 3 (M.K.) on XSLT v3.0, SaxonEE v9-9-1-7J

Slowest (30,09s): Solution 3 (M.K.) on XQuery v3.1, BaseX v9.3.2

Bad Case: There is no comment with the search pattern

Fastest (30,28s): Solution 1 (M.H.) on XQuery v3.1, BaseX v9.3.2

Slowest (47,26s): Solution 3 (M.K.) on XQuery v3.1, BaseX v9.3.2

Scripts and XML Database

https://gitlab.com/ms152718212/xslxqyfindpattern

Solutions with non XML technologies

ripgrep (rg)

> time rg -C 5 'Foo4711' DB50C1000000P.xml | rg -c -U '<comment>(?s:[^<]*)Foo4711(?s:[^<]*)</comment>' 
4

rg -C 5 'Foo4711' DB50C1000000P.xml  0,27s user 0,72s system 90% cpu 1,094 total

rg -c -U '<comment>(?s:[^<]*)Foo4711(?s:[^<]*)</comment>'  0,01s user 0,01s system 1% cpu 1,092 total


> time rg -C 5 'Foo4711a' DB50C1000000P.xml | rg -c -U '<comment>(?s:[^<]*)Foo4711a(?s:[^<]*)</comment>'

rg -C 5 'Foo4711a' DB50C1000000P.xml  0,24s user 0,66s system 93% cpu 0,957 total

rg -c -U '<comment>(?s:[^<]*)Foo4711a(?s:[^<]*)</comment>'  0,01s user 0,01s system 1% cpu 0,957 total
Admin1
Related