News for hackers. Stuff that matters.
Re:Xee: A Modern XPath and XSLT Engine in Rust by infogulch on Friday March 28, 2025 @01:22PM (#43507924)
There are many humongous XML sources. E.g. the Wikipedia archive is 42GB of uncompressed text. Holding a fully parsed representation of it in memory would take even more, perhaps even >100GB which immediately puts this size of document out of reach.

The obvious solution is streaming, but streaming appears to not be supported, though is listed under Challenging Future Ideas: https://github.com/Paligo/xee/blob/main/ideas.md

How hard is it to implement XML/XSLT/XPATH streaming?

Re:Xee: A Modern XPath and XSLT Engine in Rust by jerf on Friday March 28, 2025 @04:17PM (#43509467)
"How hard is it to implement XML/XSLT/XPATH streaming?"

It's actually quite annoying on the general case. It is completely possible to write an XPath expression that says to match a super early tag on an arbitrarily-distant further tag.

In another post in this thread I mention how I think it's better to think of it as a multicursor, and this is part of why. XPath doesn't limit itself to just "descending", you can freely cursor up and down in the document as you write your expression.

So it is easy to write expressions where you literally can't match the first tag, or be sure you shouldn't return it, until the whole document has been parsed.

Re:Xee: A Modern XPath and XSLT Engine in Rust by riedel on Friday March 28, 2025 @05:24PM (#43509926)
I think from a grammar side, XPath had made some decisions that make it really hard to generally implement it efficiently. About 10 years ago I was looking into binary XML systems and compiling stuff down for embedded systems realizing that it is really hard to e.g. create efficient transducers (in/out pushdown automata) for XSLT due to complexity of XPath.
Re:Xee: A Modern XPath and XSLT Engine in Rust by ssdspoimdsjvv on Saturday March 29, 2025 @07:20AM (#43514567)
Streaming is defined in the XSLT 3 spec: https://www.w3.org/TR/xslt-30/#streamability. When you want to use streaming, you are confined to a subset of XPath that is "guaranteed streamable", e.g. you can't just freely navigate the tree anymore. There are some special instructions in XSLT such as <xsl:merge> and <xsl:accumulator> that make it easier to collect your results.

Saxon's paid edition supports it. I've done it a few times, but you have to write your XSLT in a completely different way to make it work.

Re:Xee: A Modern XPath and XSLT Engine in Rust by riedel on Sunday March 30, 2025 @04:24AM (#43522410)
This was as I remember under development at the time. However, if working on bounded memory on communication buffers it, without remembering all the details, it was a pain not because of XSLT but mostly its interactions with XPATH. I was at the time formally looking into hedge grammars and visibly pushdown automata as formal basis, but to me it seemed at the time, that formal complexity was unnecessarily pushed beyond what was straightforward feasible. As I said it was about transforming binary (intermediate) representations of XML. Use case was actually to build message middlewares/routers for IoT stuff at the time. IMHO also the picked binary XML standards where mostly the wrong choice for small embedded systems (interestingly MPEG 7 is btw one of the few standards that supports rather nice streaming binary XML. I think however it is only used in digital broadcasting)
Re:Xee: A Modern XPath and XSLT Engine in Rust by mintplant on Friday March 28, 2025 @09:30PM (#43511907)
Would it be possible to transform a large XML document into something on-disk that could be queried like a database by the XPath evaluator?
Re:Xee: A Modern XPath and XSLT Engine in Rust by econ on Friday March 28, 2025 @09:48PM (#43512004)
It seems to me one could replace each text node with the offset. Perhaps limit it to longer instances?
Re:Xee: A Modern XPath and XSLT Engine in Rust by chii on Saturday March 29, 2025 @04:35AM (#43513831)
You'd basically be building an index into each node.

There's some fast databases that store prefix trees, which might be suitable for such a task actually (something like infinitydb). But building this database will basically take a while (it will require parsing the entire document). But i suppose if reading/querying is going to happen many times, its worth it?

Re:Xee: A Modern XPath and XSLT Engine in Rust by phonon on Saturday March 29, 2025 @05:19AM (#43514019)
Like MarkLogic?
Re:Xee: A Modern XPath and XSLT Engine in Rust by jerf on Saturday March 29, 2025 @11:20AM (#43516229)
Given the nature of this processing, I think even an NVMe-based disk storage would be awfully slow. (People often forget, or never realize, that the "gigabytes per second" that NVMe yields is for sequential access. Random access is quite a bit slower; still stomps spinning rust, but by much less. And this is going to be a random access sort of job, so we're in the "several multiples slower than RAM" regime of access.) This sort of thing really wants RAM, and even then, RAM with an eye towards cache coherency and other such performance considerations.
Re:Xee: A Modern XPath and XSLT Engine in Rust by faassen on Friday March 28, 2025 @01:56PM (#43508261)
Anything could be supported with sufficient effort, but streaming hasn't been my priority so far and I haven't explored it in detail. I want to get XSLT 3.0 working properly first.

There's a potential alternative to streaming, though - succinct storage of XML in memory:

https://blog.startifact.com/posts/succinct/

I've built a succinct XML library named Xoz (not integrated into Xee yet):

https://github.com/Paligo/xoz

The parsed in memory overhead goes down to 20% of the original XML text in my small experiments.

There's a lot of questions on how this functions in the real world, but this library also has very interesting properties like "jump to the descendant with this tag without going through intermediaries".

Re:Xee: A Modern XPath and XSLT Engine in Rust by bambax on Friday March 28, 2025 @02:42PM (#43508692)
> I want to get XSLT 3.0 working properly first

May I ask why? I used to do a lot of XSLT in 2007-2012 and stuck with XSLT 2.0. I don't know what's in 3.0 as I've never actually tried it but I never felt there was some feature missing from 2.0 that prevented me to do something.

As for streaming, an intermediary step would be the ability to cut up a big XML file in smaller ones. A big XML document is almost always the concatenation of smaller files (that's certainly the case for Wikipedia for example). If one can output smaller files, transform each of them, and then reconstruct the initial big file without ever loading it in full in memory, that should cover a huge proportion of "streaming" needs.

Re:Xee: A Modern XPath and XSLT Engine in Rust by faassen on Friday March 28, 2025 @03:57PM (#43509331)
XSLT has been a goal of this project from the start, as my customer uses it. XSLT 3.0 simply as that's the latest specification. What tooling do you use for XSLT 2.0?
Re:Xee: A Modern XPath and XSLT Engine in Rust by bambax on Friday March 28, 2025 @04:03PM (#43509378)
Saxon's free version, which IIRC only implemented 2.0.
Re:Xee: A Modern XPath and XSLT Engine in Rust by infogulch on Friday March 28, 2025 @02:04PM (#43508343)
0.2x of the original size would certainly make big documents more accessible. I've heard of succinct storage, but not in the context of xml before, thanks for sharing!
Re:Xee: A Modern XPath and XSLT Engine in Rust by faassen on Friday March 28, 2025 @02:20PM (#43508484)
I myself actually had no idea succinct data structures existed until last December , but then I found a paper that used them in the context of XML. Just to be clear: it's 120% of the original size; as it stands this library still uses more memory than the original document, just not a lot of overhead. Normal tree libraries, even if the tree is immutable, take a parent pointer, and a first child pointer and next and previous sibling pointers per node. Even though some nodes can be stored more compactly it does add up.

I suspect with the right FM-Index Xoz might be able to store huge documents in a smaller size than the original, but that's an experiment for the future.

Re:Xee: A Modern XPath and XSLT Engine in Rust by lambda on Friday March 28, 2025 @05:48PM (#43510158)
Would you be able to parse it in a streaming fashion and just store the structure of the document in memory, with just offsets for all of the string locations, and then re-read those from disk as needed?

With modern SSDs and disk cache, that's likely enough to be plenty performant without having to store the whole document in memory at once.

Re:Xee: A Modern XPath and XSLT Engine in Rust by wongarsu on Friday March 28, 2025 @01:31PM (#43508016)
100GB doesn't sound that out of reach. It's expensive in a laptop, but in a desktop that's about $300 of RAM and our supported by many consumer mainboards. Hetzner will rent me a dedicated server with that amount of ram for $61/month.

If the payloads in question are in that range, the time spent to support streaming doesn't feel justified compared to just using a machine with more memory. Maybe reducing the size of the parsed representation would be worth it though, since that benefits nearly every use case

Re:Xee: A Modern XPath and XSLT Engine in Rust by infogulch on Friday March 28, 2025 @01:58PM (#43508278)
I just pulled the 100GB number out of nowhere, I have no idea how much overhead parsed xml consumes, it could be less or it could be more than 2.5x (it probably depends on the specific document in question).

In any case I don't have $1500 to blow on a new computer with 100GB of ram in the unsubstantiated hope that it happens to fit, just so I can play with the Wikipedia data dump. And I don't think that's a reasonable floor for every person that wants to mess with big xml files.

Re:Xee: A Modern XPath and XSLT Engine in Rust by philipkglass on Friday March 28, 2025 @02:43PM (#43508698)
In the case of Wikipedia dumps there is an easy work-around. The XML dump starts with a small header and "<siteinfo>" section. Then it's just millions of "page" documents for the Wiki pages.

You can read the document as a streaming text source and split it into chunks based on matching pairs of "<page>" and "</page>" with a simple state machine. Then you can stream those single-page documents to an XML parser without worrying about document size. This of course doesn't apply in the general case where you are processing arbitrary huge XML documents.

I have processed Wikipedia many times on a machine with only 8 GB of RAM.

Re:Xee: A Modern XPath and XSLT Engine in Rust by hyhjtgh on Friday March 28, 2025 @02:10PM (#43508394)
Xml and textual formats in general are ill suited to such large documents. Step 1 should really be to convert and/or split the file into smaller parts.
Re:Xee: A Modern XPath and XSLT Engine in Rust by intrasight on Friday March 28, 2025 @09:32PM (#43511918)
Or shred into a proper database designed for that
Re:Xee: A Modern XPath and XSLT Engine in Rust by nicoburns on Friday March 28, 2025 @07:09PM (#43510878)
Shouldn't parsed XML be smaller than the raw uncompressed text? (as you could deduplicate strings). I'd expect that to be a significant saving for something like wikipedia in XML
Re:Xee: A Modern XPath and XSLT Engine in Rust by philipkglass on Friday March 28, 2025 @07:32PM (#43511027)
For Wikipedia, the bulk of the data in the XML is inside a "<text>" block that contains wikitext: https://en.wikipedia.org/wiki/Help:Wikitext

For the English Wikipedia the wikitext accounts for about 80% of the bytes of the uncompressed XML.

Re:Xee: A Modern XPath and XSLT Engine in Rust by dleeftink on Friday March 28, 2025 @01:41PM (#43508100)
StackExchange also, not necessarily streamable but records are newline delimited which makes it easier to sample (at least the last time I worked with the Data Dump).
Re:Xee: A Modern XPath and XSLT Engine in Rust by 01HNNWZ0MV43FF on Friday March 28, 2025 @01:37PM (#43508062)
Is that all in one big document?
Re:Xee: A Modern XPath and XSLT Engine in Rust by magicalhippo on Friday March 28, 2025 @03:20PM (#43509049)
We regularly parse ~1GB XML documents at work, and got laughed at by someone I know who worked with bulk invoices when I called it a large XML file.

Not sure how common 100GB files are but I can certainly image that being the norm in certain niches.

Re:Xee: A Modern XPath and XSLT Engine in Rust by heelix on Saturday March 29, 2025 @09:50AM (#43515534)
I used to work for a NoSQL company that was more or less an XQUERY engine. One of the things we would complain about is we did use wikipedia as a test data set, so the standing joke was for those of us dealing with really big volumes we'd complain about 'only testing Wikipedia' sized things. Good times.