Grouping Records With XSLT 2 and Muenchian Keys Compared

Grouping is the operation XSLT 1.0 does badly, and it comes up constantly: invoices per currency, books per author, errors per code. The language has no group-by. There is a well-known workaround, named after its inventor Steve Muench, and XSLT 2.0 replaced it with a proper instruction. This article does the same grouping both ways on 20,000 invoices, shows what you gain by moving to 2.0 and measures what each costs.

The task

For each currency (the cur attribute of invoice): the number of invoices, the number of lines, and, where the language lets us do it exactly, the revenue (quantity times amount over all lines). The expected answer, from the other tools in this cluster, is 3,897 EUR invoices with 9,764 lines, 12,138 USD with 30,245 and 3,965 VND with 9,810.

XSLT 1.0: the Muenchian method

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="text"/>
  <xsl:key name="by-cur" match="invoice" use="@cur"/>
  <xsl:template match="/invoices">
    <xsl:for-each select="invoice[generate-id() = generate-id(key('by-cur', @cur)[1])]">
      <xsl:sort select="@cur"/>
      <xsl:variable name="g" select="key('by-cur', @cur)"/>
      <xsl:value-of select="@cur"/>: <xsl:value-of select="count($g)"/> invoices, <xsl:value-of select="count($g/line)"/> lines<xsl:text>&#10;</xsl:text>
    </xsl:for-each>
  </xsl:template>
</xsl:stylesheet>

EUR: 3897 invoices, 9764 lines
USD: 12138 invoices, 30245 lines
VND: 3965 invoices, 9810 lines

Three moving parts. xsl:key builds an index: for every invoice, the value of @cur. key('by-cur', 'USD') then returns all USD invoices at once. The trick is the predicate on the for-each: generate-id() = generate-id(key('by-cur', @cur)[1]) is true only for the first invoice in each currency group, because generate-id returns a unique id per node and the first member of the key's node-set is one specific node. So the loop runs once per group. Inside, key('by-cur', @cur) gives the whole group, and count works on it. It is clever and unobvious, and nobody reads it cold; a comment above it is not optional.

Sums in 1.0 are possible (sum($g/line/amount)) but the quantity multiplication is not: sum takes a node-set, and you cannot multiply inside it. The workaround is a recursive template, which is where the 1.0 version stops being pleasant. And every number is an IEEE double, so cents drift.

XSLT 2.0: for-each-group

<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:xs="http://www.w3.org/2001/XMLSchema">
  <xsl:output method="text"/>
  <xsl:template match="/invoices">
    <xsl:for-each-group select="invoice" group-by="@cur">
      <xsl:sort select="current-grouping-key()"/>
      <xsl:value-of select="current-grouping-key()"/>: <xsl:value-of select="count(current-group())"/> invoices, <xsl:value-of select="count(current-group()/line)"/> lines, revenue <xsl:value-of select="format-number(sum(current-group()/line/(xs:decimal(amount) * xs:integer(@qty))), '#,##0.00')"/><xsl:text>&#10;</xsl:text>
    </xsl:for-each-group>
  </xsl:template>
</xsl:stylesheet>

EUR: 3897 invoices, 9764 lines, revenue 1,481,098.58
USD: 12138 invoices, 30245 lines, revenue 4,579,242.21
VND: 3965 invoices, 9810 lines, revenue 1,503,163.23

for-each-group select="invoice" group-by="@cur" does what its name says. Inside it, current-grouping-key() is the currency and current-group() is the group's nodes. The sum uses a path step with an expression, line/(xs:decimal(amount) * xs:integer(@qty)), which XPath 2.0 allows, and xs:decimal keeps the arithmetic exact. The three revenue figures are the same to the cent as the Python streaming script and the DuckDB query elsewhere in this series, and they match: 4,579,242.21 for USD. format-number adds the thousands separators. The 2.0 version is a third the length and readable by someone who has never seen the Muenchian trick.

Note that xsltproc cannot run this. It is XSLT 1.0 only, and a version="2.0" stylesheet needs a 2.0 processor; Saxon is the usual one, and it is free in its Home Edition. The command I used:

java -cp "lib/*" net.sf.saxon.Transform -s:invoices.xml -xsl:group20.xsl

Timings

The 1.0 stylesheet was slow on libxslt: 4 seconds for 20,000 invoices. I did not profile the cause; the work per group is a key lookup over a large node set and a count over the group's lines, which is where I would look first. Saxon, which compiles and optimizes the key, ran it in a second including JVM start-up, and the 2.0 version with the extra revenue calculation in 1.5 seconds. A plain Python loop over the same tree took 0.03 seconds. The lesson is not that XSLT is slow. It is that the grouping idiom's cost depends on the processor, and a stylesheet that is fine at 2,000 records can be a problem at 200,000. Measure with your processor and your data size, and if the cost matters, either use an optimizing processor or do the grouping in code.

Variations worth knowing

The Muenchian pattern generalizes with a composite key: concatenate fields in the use expression (concat(@cur, '|', substring(due, 1, 7)) for currency and month) and compare the same way. Grouping on a range, such as price bands, needs a computed key (floor(price div 100)), and the key is a number then, so the groups sort as text unless you say data-type="number" in the sort.

In XSLT 2.0, for-each-group has three more modes beyond group-by. group-adjacent groups consecutive items with the same key, which fits sorted logs and runs of repeated records. group-starting-with starts a new group at each item that matches a pattern, which turns a flat list of headings and paragraphs into sections. group-ending-with is the mirror. Those cases are painful in 1.0 and are the reason a team that processes document-like XML moves to a 2.0 processor.

Test grouping with a file that has the awkward cases: a group with one member, a record with an empty or missing key (it goes into its own group or is skipped depending on the version; check), keys that differ only in case, and an empty input. The answer on an empty invoices element should be empty output, not an error.

Choosing

If you are on libxslt (PHP, Python's lxml, xsltproc, many embedded systems) you have 1.0, and Muenchian grouping is what there is; keep a comment on it and a test with a small file. If you can choose the processor, use Saxon and write 2.0 or 3.0: the stylesheet is shorter, the arithmetic is exact and the grouping instructions (group-adjacent, group-starting-with) cover cases that 1.0 cannot reach cleanly. If the grouping is the whole job and the data is not XML-native, do it in a script. See choosing between XSLT, XQuery and a script for the wider comparison.

Related reading

For the basics see XSLT basics: templates, match and apply and the cluster overview XSLT and XQuery for real transformations. The same grouping in XQuery is in XQuery basics with BaseX. The Muenchian method is described on the Jeni Tennison XSLT pages, and for-each-group in the XSLT 2.0 specification. Test an XPath in the XPath tester.

When grouping belongs outside XSLT

The result is for a person. A report with totals and formatting is a fine XSLT job. A table of aggregates to be loaded into a database is easier in SQL.

The data is large. XSLT builds the input tree. For hundreds of megabytes, stream the file in a script, or use a processor with streaming support (XSLT 3.0 in Saxon's licensed editions); I did not test streaming here.

The grouping is on computed values. Grouping by month of a date, by a range or by a lookup is awkward in 1.0 and natural in a script.

You only have libxslt. Fix the stylesheet's cost with a profile, or move the work to the host language, where the tree is already in memory.