Как эффективно пройти со многими вершинами в OrientDB

Question

Я построил дерево в orientdb с большим количеством узлов и ребер в направлении снизу вверх.Я хотел бы получить все листья этого дерева (каждый лист имеет @class LEAF), которые соответствуют определенному условию диапазона (например, val> 150 и val <300): </p>

Пример:

       o
     /   \
    o     o 
   /    /  \ 
  o    o    o
 210  120   /\
          270 180

Результат: 210, 180, 270

До сих пор я пытался использовать следующий запрос:

SELECT FROM(TRAVERSE IN() FROM #123:123) WHERE value > 150 and value < 300

Это работает хорошо с несколькими элементами, но производительность падает сувеличение количества листьев.Итак, мои вопросы:

1. Является ли это наиболее эффективным способом сделать это в OrientDB, особенно если я скажу 300000 листов под каждым узлом?
2. Из документации я знаю, что использование индекса может помочь повысить производительность запросов диапазона, но будет ли индекс использоваться в этом случае?Мое первое предположение - нет, потому что orient сначала обходит, а затем фильтрует пройденные элементы, не так ли?

Answer 1

Чтобы повысить производительность, попробуйте подумать о минимальном объеме работы , который должен выполнить запрос, чтобы найти правильные листы: вы хотите найти листы с определенным значением , которое являются частью определенного дерева .

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

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

Например, давайте создадим дерево примеров:

CREATE CLASS Node EXTENDS V
CREATE PROPERTY Node.name INTEGER
CREATE VERTEX Node SET name = 1
CREATE VERTEX Node SET name = 2
CREATE VERTEX Node SET name = 3
CREATE VERTEX Node SET name = 4

CREATE CLASS LEAF EXTENDS V
CREATE PROPERTY LEAF.val FLOAT
CREATE VERTEX LEAF SET val = 210
CREATE VERTEX LEAF SET val = 120
CREATE VERTEX LEAF SET val = 270
CREATE VERTEX LEAF SET val = 180

CREATE CLASS C EXTENDS E
CREATE PROPERTY C.tree STRING
CREATE EDGE C FROM (SELECT * FROM Node WHERE name = 1) TO (SELECT * FROM Node WHERE name = 2) SET tree = 'example'
CREATE EDGE C FROM (SELECT * FROM Node WHERE name = 1) TO (SELECT * FROM Node WHERE name = 3) SET tree = 'example'
CREATE EDGE C FROM (SELECT * FROM Node WHERE name = 3) TO (SELECT * FROM Node WHERE name = 4) SET tree = 'example'
CREATE EDGE C FROM (SELECT * FROM Node WHERE name = 2) TO (SELECT * FROM LEAF WHERE val = 210) SET tree = 'example'
CREATE EDGE C FROM (SELECT * FROM Node WHERE name = 3) TO (SELECT * FROM LEAF WHERE val = 120) SET tree = 'example'
CREATE EDGE C FROM (SELECT * FROM Node WHERE name = 4) TO (SELECT * FROM LEAF WHERE val = 270) SET tree = 'example'
CREATE EDGE C FROM (SELECT * FROM Node WHERE name = 4) TO (SELECT * FROM LEAF WHERE val = 180) SET tree = 'example'

Обратите внимание, что класс EDGE C содержит свойство C.tree (строка). При создании ребер между Nodes и LEAFs присвойте имя дереву каждому EDGE. В этом случае я добавил SET tree = 'example' к каждому ребру.

Результат выглядит так:

Затем создайте индекс для LEAF.val (для ускорения поиска значения) и индекс для C.tree для быстрой идентификации дерева, к которому принадлежит каждый лист:

CREATE INDEX leafIndex ON LEAF (val) NOTUNIQUE
CREATE INDEX connectIndex ON C (tree) NOTUNIQUE

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

SELECT * FROM LEAF WHERE inE('C').tree = ["example"] AND val > 150 and val < 300

Этот запрос выполняет следующие действия:

1. Выбрать все листья ...
2. Имеет in край класса C со свойством tree, равным «example»
3. И имеют val свойство между 150 и 300

Этот подход также позволяет избежать использования traverse, что обходится дороже, чем использование select.

Результат именно то, что вы хотите:

Из объяснения запроса также видно, что механизм оптимизации использует индекс:

+ FETCH FROM INDEX leafIndex
  val > 150 and val < 300
+ EXTRACT VALUE FROM INDEX ENTRY
  filtering clusters [273,274,275,276,277,278,279,280]
+ FILTER ITEMS WHERE 
  inE('C').tree = ["example"]
+ FILTER ITEMS BY CLASS 
  LEAF
+ CALCULATE PROJECTIONS
  *

Этот запрос должен работать очень хорошо, даже если у вас много листов.

Удачи!

PS. Вы также можете добавить имя дерева в каждую вершину (вместо ребра), это тоже решение! Но в этом случае помните, что происходит, когда лист является частью нескольких деревьев.