Этот тормознутый xquery.

Я и раньше замечал, что xquery не блещет скоростью. Но недавно попытался решить эту задачу с помощью онного и убедился, что при сколько-нибудь сложных запросах xquery становится совершенно непригоден.

Вкратце условие задачи: даны координаты 1000000 звёзд в трёхмерном пространстве, нужно найти 2 самые близкие из них. Оставим за кадром то, что у неё есть решение проще чем за O(n^2) и просто посмотрим как увеличивается скорость выборки по запросу. В качестве среды исполнения используется BaseX.

Для того, чтобы просто вернуть корневой элемент

for $i in collection('stars')
return $i

потребуется 2.6 мс. Но от него толку мало, нужно возвращать каждую запись с 3 координатами. Вот такой зарос

for $i in collection('stars')/csv/record
return $i

работает уже 237 мс. Далее нужна функция, которая сравнит каждый элемент с каждым. На текущий момент это делать не очень удобно, т.к. узлы представляют из себя такую конструкцию:

<record>
  <entry>678966</entry>
  <entry>362701</entry>
  <entry>675437</entry>
</record>

Для начала переименуем элементы entry во что-нибудь более понятное. Например в такую структуру:

<record>
  <X>295404</X>
  <Y>556987</Y>
  <Z>987496</Z>
</record>

по-хорошему, надо было звёздам выдать id-шники, но у меня от этого basex свалился :( Итак, вызов простой функции для подсчёта расстояния между 2 точками занимает 181 мс.:

declare namespace t = 'none';

declare function t:dist($s1, $s2)
{
  let $dist := (data($s2/X) - data($s1/X)) * (data($s2/X) - data($s1/X)) +
    (data($s2/Y) - data($s1/Y)) * (data($s2/Y) - data($s1/Y)) +
    (data($s2/Z) - data($s1/Z)) * (data($s2/Z) - data($s1/Z))
  return $dist
};

let $i := collection('stars')/csv/record
return t:dist(head($i), $i[last()])

Теперь посмотрим, за сколько выполнится один проход:

declare namespace t = 'none';

declare function t:dist($s1, $s2)
{
  let $dist := (data($s2/X) - data($s1/X)) * (data($s2/X) - data($s1/X)) +
    (data($s2/Y) - data($s1/Y)) * (data($s2/Y) - data($s1/Y)) +
    (data($s2/Z) - data($s1/Z)) * (data($s2/Z) - data($s1/Z))
  return $dist
};

declare function t:findDist($s1)
{
  for $i in collection('stars')/csv/record[data(X) != data($s1/X)][data(Y) != data($s1/Y)][data(Z) != data($s1/Z)]
  return t:dist($i, $s1)
};

declare function t:findMin($s1)
{
  let $x := min(t:findDist($s1))
  return $x
};

let $i := collection('stars')/csv/record
return t:findMin(head($i))

Такой запрос выполняется от 16 до 17 секунд. Т.е. чтобы посчитать 1000000 значений потребуется ~185 суток или 5 месяцев!! И это без возможности параллельного выполнения запроса. Явно недостаточно для конкурса, проходящего 4 дня.