Как лениво оценить порядок XQuery, когда результаты все равно будут небольшим подмножеством?

Представьте, что у вас есть большое количество записей в базе данных XML на основе XQuery:

<widgets>
   <widget id="1" name="Foo Widget" price="19.99" />
   <widget id="2" name="Bar Widget" price="29.99" />
   <widget id="3" name="Baz Widget" price="39.99" />
   <!-- etc. -->
</widget>

Под «большим числом» я подразумеваю миллион или больше.

Вы хотите получить один элемент из списка случайным образом, используя XQuery:

let $widgets := for $widget in //widgets/widget
  order by util:random()
  return $widget

for $val in subsequence($widgets, 1, 1)
  return $val

Когда количество записей растет, выполнение оценки занимает слишком много времени, так как кажется, что загружается все из базы данных и переупорядочивается в памяти. Я думаю, что это может быть O(n log 2n). Медлительность, вызывающая вздох.

Есть ли более ленивый и лучший способ сделать это?

Есть метод «подсчитать количество элементов, затем случайным образом выбрать число от нуля для подсчета», которого я бы предпочел избежать.

В идеале база данных могла бы это сделать, если бы была какая-то фича типа:

let $widgets := for $widget in //widgets/widget
  order by util:random()
  limit 1
  return $widget

Думаю, это будет FLOLWR. Но этого нет в спецификации XQuery, хотя это достаточно распространенная вещь, которую можно сделать в SQL (или даже в SPARQL или ряде других языков запросов).

Есть ли способ получить это? Добавление предложения where сделает это, но предложения where оцениваются до предложений порядка, что на самом деле не помогает.

Какие-либо предложения? (Приложение, отправляющее XQueries, написано на Java, а база данных XML — это eXist, если это поможет с какими-то немного более кривыми, нестандартными идеями.)


random xquery exist-db
person Tom Morris    schedule 30.08.2011    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Оптимизатор может работать лучше, если вы не используете промежуточную переменную, но это большая вероятность.

subsequence(
 for $widget in //widgets/widget
  order by util:random()
  return $widget
 ,1,1)

Я подозреваю, что «метод, которого вы бы предпочли избежать», будет работать лучше, но доказательство в бенчмаркинге.

//widgets/widget[util:random(count(//widgets/widget))]
person evil otto    schedule 30.08.2011
comment
Да, это решение, которое я в итоге использовал. Это намного быстрее. - person Tom Morris; 05.09.2011
comment
@evilotto Я также не понимаю, почему нужно избегать получения ровно одного элемента напрямую :) Разве ваш запрос не должен быть //widgets/widget[1 + util:random(count(//widgets/widget))] (потому что последовательности основаны на 1)? - person ᴠɪɴᴄᴇɴᴛ; 19.02.2015