Написание более эффективного кода xquery (избегая избыточной итерации)

Question

Вот упрощенная версия проблемы, над которой я работаю: у меня есть куча XML-данных, которые кодируют информацию о людях. Каждый человек уникально идентифицируется атрибутом id, но он может называться многими именами. Например, в одном документе я могу найти

<person id=1>Paul Mcartney</person>
<person id=2>Ringo Starr</person>

А в другом я могу найти:

<person id=1>Sir Paul McCartney</person>
<person id=2>Richard Starkey</person>

Я хочу использовать xquery для создания нового документа, в котором перечислены все имена, связанные с данным идентификатором. i.e.:

<person id=1>
    <name>Paul McCartney</name>
    <name>Sir Paul McCartney</name>
    <name>James Paul McCartney</name>
</person>
<person id=2>
    ...
</person>

То, как я делаю это сейчас в xquery, выглядит примерно так (псевдокод-эск):

let $ids := distinct-terms( [all the id attributes on people] )
for $id in $ids
    return <person id={$id}>
    {
    for $unique-name in distinct-values
            (
            for $name in ( [all names] )
            where $name/@id=$id
            return $name
            )
        return <name>{$unique-name}</name>
    }
    </person>

Проблема в том, что это действительно медленно. Я предполагаю, что узким местом является самый внутренний цикл, который выполняется один раз для каждого идентификатора (которых около 1200). Я имею дело с достаточным количеством данных (300 МБ, разбросано по 800 XML-файлам), поэтому даже одно выполнение запроса во внутреннем цикле занимает около 12 секунд, что означает, что для повторения 1200 раз потребуется около часов (что может быть оптимистично - процесс продолжается уже 3 часа). Это не только медленно, но и использует много виртуальной памяти. Я использую Saxon, и мне пришлось установить максимальный размер кучи Java на 10 ГБ (!), Чтобы избежать ошибок памяти, и в настоящее время он использует 6 ГБ физической памяти.

Так вот, как бы я действительно хотел это сделать (в псевдокоде Pythonic):

persons = {}
for id in ids:
    person[id] = set()
for person in all_the_people_in_my_xml_document:
    persons[person.id].add(person.name)

Там я только что сделал это за линейное время, с помощью всего лишь одной развертки документа xml. Теперь, есть ли способ сделать что-то подобное в xquery? Конечно, если я могу себе это представить, разумный язык программирования должен быть в состоянии сделать это (сказал он в шутку). Проблема, я полагаю, в том, что в отличие от Python, xquery не имеет (насколько я знаю) ничего похожего на ассоциативный массив.

Есть ли какой-нибудь умный способ обойти это? В противном случае, есть ли что-то лучше, чем xquery, который я мог бы использовать для достижения своей цели? Потому что на самом деле вычислительные ресурсы, которые я использую для решения этой относительно простой задачи, просто смешны.

Answer 1

Это, к сожалению, недостаток в XQuery 1.0

XQuery 1.1 добавляет предложение group by к синтаксису для решения этой проблемы, и ваша проблема будет решена с помощью:

for $person in /person
let $id = $person/@id
group by $id
return  <people id="{$id}">{
          for $name in distinct-values($person)
          return <name>{$name}</name>
        }</people>

К сожалению, XQuery 1.1 не получил широкого распространения, поэтому на данный момент вы застряли без предложения group by.

Как разработчик в XQSharp, я не могу говорить ни о каких других реализациях, но мы потратили много времени на настройку нашего оптимизатора, чтобы обнаружить общие шаблоны группировки в XQuery 1.1 и выполнить их с указанным вами алгоритмом.

В частности, следующая версия вашего запроса:

declare variable $people as element(person, xs:untyped)* external;

for $id in distinct-values($people/@id)
return <people id="{$id}">{
          for $person in $people
          where $person/@id = $id
          return <name>{$person}</name>
       }</people>

определяется как группировка, о чем свидетельствует следующий план запроса:

library http://www.w3.org/2005/xpath-functions external;
library http://www.w3.org/2001/XMLSchema external;
declare variable $people external;

for $distinct-person in $people
let $id := http://www.w3.org/2005/xpath-functions:data($distinct-person/attribute::id)
group by
  $id
aggregate
  element {name} { fs:item-sequence-to-node-sequence($distinct-person) }
as
  $:temp:19
return
  element {person} { (attribute {id} { $id } , fs:item-sequence-to-node-sequence($:temp:19)) }

Обратите внимание, что требуется аннотация типа as element(person, xs:untyped)*, поскольку, не зная, что узлы нетипизированы (не проверены на соответствие схеме), обработчик запросов не может знать, что $person/@id не имеет нескольких элементов в своем значение данных. XQSharp еще не поддерживает группу по выражениям, где каждый узел может иметь более одного ключа. Однако в этом случае левое внешнее соединение все еще замечено, и поэтому сложность должна быть примерно n log n , а не квадратичной, как вы испытываете.

К сожалению, хотя добавление вразделенных значений вокруг группы людей в группе (для фильтрации дублированных имен), похоже, мешает XQSharp найти соединение; это было зарегистрировано как ошибка. Сейчас это можно решить, выполнив запрос в два этапа - сгруппировав имена по идентификатору и удалив повторяющиеся имена.

Таким образом, в XQuery 1.0 нет лучшего подхода, но некоторые реализации (например, XQSharp) смогут эффективно оценить это. В случае сомнений проверьте план запроса.

Для более подробного ознакомления с оптимизациями соединения, выполненными XQSharp, посмотрите это сообщение в блоге .

Answer 2

В противном случае, есть что-то лучше, чем xquery, который я мог бы использовать для достичь моей цели? Потому что на самом деле, вычислительные ресурсы я бросать в это относительно просто проблема вроде смешная.

Вот простое решение XSLT 2.0 (для удобства два из трех документов представлены <xsl:variable> с):

<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
 <xsl:output omit-xml-declaration="yes" indent="yes"/>

 <xsl:variable name="vDoc2">
  <persons>
   <person id="1">Sir Paul McCartney</person>
   <person id="2">Richard Starkey</person>
  </persons>
 </xsl:variable>

 <xsl:variable name="vDoc3">
  <persons>
   <person id="1">James Paul McCartney</person>
   <person id="2">Richard Starkey - Ringo Starr</person>
  </persons>
 </xsl:variable>

 <xsl:template match="/">
  <xsl:for-each-group group-by="@id" select=
   "(/ | $vDoc2 | $vDoc3)/*/person">

   <person id="{current-grouping-key()}">
     <xsl:for-each select="current-group()">
       <name><xsl:sequence select="text()"/></name>
     </xsl:for-each>
   </person>

  </xsl:for-each-group>
 </xsl:template>
</xsl:stylesheet>

Когда это преобразование применяется к следующему документу XML :

<persons>
    <person id="1">Paul Mcartney</person>
    <person id="2">Ringo Starr</person>
</persons>

желаемый, правильный результат получается :

<person id="1">
   <name>Paul Mcartney</name>
   <name>Sir Paul McCartney</name>
   <name>James Paul McCartney</name>
</person>
<person id="2">
   <name>Ringo Starr</name>
   <name>Richard Starkey</name>
   <name>Richard Starkey - Ringo Starr</name>
</person>

Answer 3

Другой вариант: использовать карту.

let $map := map:map()
let $people :=
  for $person in $all-people
  return map:put($map, $person/@id, 
    (map:get($map, $person/@id), <name>{$person/text()}</name>))
return
  for $id in map:keys($map)
  return 
    <person id="{$id}">{map:get($map, $id)}</person>

Answer 4

Если вы используете обновление базы данных XML, например eXist db, вы можете выполнить группировку, как и в Pythonesque, непосредственно в XML-документ, где, по-видимому, в любом случае необходим результат для дальнейшей обработки.

let $persons := doc("/db/temp/p3.xml")/persons
let $person-groups := doc("/db/temp/p2.xml")/person-groups
for $person in $persons/person
let $name := element name {$person/text()}
let $person-group := $person-groups/person-group[@id=$person/@id]
return
   if ($person-group) 
   then update insert $name into $person-group
   else update insert element person-group {attribute id {$person/@id}, $name} 
       into $person-groups

Для моих экспериментов с 10000 узлов с более чем 100 разными идентификаторами, eXist на нашем сервере имеет пропускную способность около 100 узлов в секунду.

Обратите внимание, что расширение обновления для XQuery в eXist отличается от синтаксиса XQuery Update