Ускорение SPARQL-запроса на GraphDB - PullRequest
Новая
       16

Ускорение SPARQL-запроса на GraphDB

0 голосов
/ 28 августа 2018

Я пытаюсь ускорить и оптимизировать этот запрос 

select distinct ?root where { 
    ?root a :Root ;
          :hasnode* ?node ;
          :hasnode* ?node2 .

    ?node a :Node ;
           :hasAnnotation ?ann .
    ?ann :hasReference ?ref .
    ?ref a :ReferenceType1 .

    ?node2 a :Node ;
            :hasAnnotation ?ann2 .
    ?ann2 :hasReference ?ref2 .
    ?ref2 a :ReferenceType2 .

}

По сути, я анализирую несколько деревьев и хочу получить все деревья (то есть корни деревьев), в которых есть хотя бы пара нижележащих узлов с шаблоном, подобным этому: 

?node_x a :Node ;
       :hasAnnotation ?ann_x .
?ann_x :hasReference ?ref_x .
?ref_x a :ReferenceTypex .

один с x = 1, а другой с x = 2.

Поскольку в моем графе один узел может иметь не более одного предиката :hasAnnotation, мне не нужно указывать, что эти узлы должны быть разными.

Проблема

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

Мое (безобразное) решение: разбить его пополам

Я заметил, что если искать шаблон узла за раз, я получаю свой результат через несколько секунд (!).

К сожалению, мой текущий подход состоит в том, чтобы дважды выполнить следующий тип запроса: 

select distinct ?root where { 
    ?root a :Root ;
          :hasnode* ?node .

    ?node a :Node ;
           :hasAnnotation ?ann_x .
    ?ann_x :hasReference ?ref_x .
    ?ref_x a :ReferenceTypex .
}

один с x = 1, а другой с x = 2.

Сохранение частичных результатов (т. Е. ?root s) в 2 наборах, скажем R1 и R2 и, наконец, вычисление пересечения между этими наборами результатов.

Есть ли способ ускорить мой первоначальный подход к получению результатов, просто используя SPARQL?

PS: я работаю с GraphDB.

Ответы [ 2 ]

0 голосов
/ 29 августа 2018

Не зная конкретного набора данных, я могу дать вам только некоторые общие указания, как оптимизировать запрос:

Избегайте использования DISTINCT для больших наборов данных

Оптимизатор запросов GraphDB не будет автоматически переписывать запрос для использования EXISTS для всех шаблонов, не участвующих в проекции. Семантика запроса состоит в том, чтобы найти, что есть хотя бы один такой шаблон, но не дает мне всех привязок, а затем устранить дублированные результаты.

Материализация путей собственности

GraphDB имеет очень эффективный механизм прямого связывания и относительно не очень оптимизированное расширение пути свойств. Если вас не интересует производительность записи / обновления данных, я предлагаю вам объявить :hasNode как транзитивное свойство (см. owl: TransitiveProperty в запросе ), что исключит подстановочный знак пути свойства. Это во много раз увеличит скорость запроса.

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

select ?root where { 
    ?root a :Root ;
          :hasnode ?node ;
          :hasnode ?node2 .

    FILTER (?node != ?node2)

    FILTER EXISTS {
        ?node a :Node ;
               :hasAnnotation ?ann .
        ?ann :hasReference ?ref .
        ?ref a :ReferenceType1 .
    }

    FILTER EXISTS {
        ?node2 a :Node ;
                :hasAnnotation ?ann2 .
        ?ann2 :hasReference ?ref2 .
        ?ref2 a :ReferenceType2 .
    }
}
0 голосов
/ 28 августа 2018

Ну, собрав авто-подсказку :) и предложение Станислава, я нашел решение.

Решение 1, вложенный запрос

Вложив запрос следующим образом, я получаю результат в 15s. 

select distinct ?root where { 
    ?root a :Root ;
          :hasnode* ?node .
    ?node a :Node ;
          :hasAnnotation ?ann .
    ?ann :hasReference ?ref .
    ?ref a :ReferenceType1 .
    {
        select distinct ?root where { 
            ?root a :Root ;
                  :hasnode* ?node2 .
            ?node2 a :Node ;
                   :hasAnnotation ?ann2 .
            ?ann2 :hasReference ?ref2 .
            ?ref2 a :ReferenceType2 .
        }
    }
}

Решение 2: группы в {}

Группировка деталей в {}, как предположил Станислав, заняла 60s. 

select distinct ?root where { 
    {
    ?root a :Root ;
          :hasnode* ?node .

    ?node a :Node ;
           :hasAnnotation ?ann .
    ?ann :hasReference ?ref .
    ?ref a :ReferenceType1 .
    }
    {
        ?root a :Root ;
          :hasnode* ?node2 .

              ?node2 a :Node ;
            :hasAnnotation ?ann2 .
    ?ann2 :hasReference ?ref2 .
    ?ref2 a :ReferenceType2 .
    }
}

Вероятно, оптимизатор GraphDB создает план запроса, более эффективный для моих данных в первом случае (объяснения приветствуются).

Я когда-либо думал о SPARQL «декларативным» образом, но, похоже, существует огромный разброс в производительности по сравнению с тем, как вы пишете SPARQL. Исходя из SQL, мне кажется, что такая изменчивость производительности намного больше, чем в реляционном мире.

Однако, читая этого поста , кажется, я недостаточно осведомлен о динамике оптимизатора SPARQL. :)

...