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

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

1 голос
/ 30 августа 2011

Представьте, что у вас есть большое количество записей в базе данных 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 сделает это, но где предложения оцениваются перед предложениями order, что на самом деле не помогает.

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

1 Ответ

3 голосов
/ 30 августа 2011

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

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

Я подозреваю, что "метод, который вы предпочли быизбежать "будет работать лучше, но доказательство находится в тестировании. 

//widgets/widget[util:random(count(//widgets/widget))]
...