Анализатор зависимостей дерева выражений - PullRequest
Новая
       5

Анализатор зависимостей дерева выражений

6 голосов
/ 26 сентября 2010

Я строю анализатор зависимостей дерева выражений для перекрестного источника данных IQueryProvider.

То есть у меня есть IQueryable с некоторыми элементами, которые могут выполняться локально в памяти по отношению к какому-либо произвольному поставщику (скажем, Entity Framework).Некоторые другие элементы в IQueryable идут против объекта, который мне нужен для удаленного вызова WCF.Операция WCF берет сериализованное дерево выражений, десериализует его, выполняет запрос LINQ к своему собственному локальному хранилищу данных (скажем, также Entity Framework), а затем отправляет мне обратно результаты (хотя этот механизм также может быть службами данных WCF.DataServiceQuery ... но я не использую его, потому что его уровень функциональной поддержки ограничен ... в лучшем случае).Как только я получу результаты от службы WCF, я выполню результат запроса LINQ в памяти против локально выполненного запроса LINQ.

Итак, что же такого сложного в этом?Что ж, мне нужно определить зависимости дерева выражений, чтобы мой локальный базовый поставщик запросов не взорвался при попытке выполнить мой запрос LINQ, в котором есть компоненты, которые могут быть выполнены только в удаленной службе WCF ... и наоборот.

Давайте рассмотрим простой сценарий: 

  var result = 
   (from entityX in new Query<MyEntityX>()
   from entityY in new Query<MyEntityY>()
   where entityX.SomeProperty == "Hello" &&
   entityY.SomeOtherProperty == "Hello 2" && entityX.Id == entityY.XId).ToList();

Query<T> - это простая запрашиваемая оболочка с моим собственным провайдером, которая имеет возможность проанализировать дерево и выяснить, что делать перед заменой.корни с другим поставщиком запросов.Итак, в приведенном выше случае мне нужно:

  1. Выполнить запрос к MyEntityA, используя локальный контекст объекта, и применить только критерии myEntityX.SomeProperty == "Hello".То есть, выполните следующее локально:

    // assume the functionality for replacing new Query<MyEntityA> with new<br> // ObjectContext<MyEntityA>() is already there...<br> var resultX = (from entityX in new Query<MyEntityX>()<br> where entityX.SomeProperty == "Hello").ToList().AsQueryable();

  2. Отправьте через сериализованный код и выполните его на моей удаленной службе WCF, а затем верните результаты.

    // Send the preceeding expression over the over the wire<br> // and get the results back (just take my word this already works)<br> var resultY = (from entityY in new Query<MyEntityY>()<br> where entityY.SomeOtherProperty == "Hello 2").ToList().AsQueryable();

  3. Выполнить в памяти следующее:

    var finalResult = (from entityX in resultX<br> from entityY in resultY<br> where entityX.SomeProperty == "Hello" &&<br> entityY.SomeOtherProperty == "Hello 2" &&<br> entityX.Id == entityY.XId).ToList();

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

var result = 
(from i in  
  (from entityX in new Query<MyEntityX>()  
   from entityY in new Query<MyEntityY>()  
   select new { PropX = entityX, PropY = entityY })  
where  
   i.PropX.SomeProperty == "Hello" && i.PropY.SomeOtherProperty == "Hello 2"  
   && i.PropX.Id == i.PropY.XId  
select i)  
.ToList();

Это должно привести к тому, что те же два отдельных запроса выше фактически будут выполнены до того, как остальные будут оценены в памяти.На несвязанной ноте, я думаю, я, вероятно, буду использовать PLINQ и / или DRYAD для запуска операций в памяти с улучшенной производительностью.

Итак, у меня есть некоторые идеи (например, сделать несколько проходов по дереву с посетителем и накапливатькандидатов на данный тип сущности), но я ищу предложения других людей о том, как накапливать части моего дерева выражений, которые могут быть выполнены в заданном контексте ... то есть, зная, что тот, где критерии применимы к одномулежащий в основе новый Query<T> и другой критерий применим к другому ... чтобы я мог выяснить, что я могу сделать с хранилищем данных 1, что я могу сделать с хранилищем данных 2 и что мне нужно сделать в памяти, и выполнитьразличные части дерева соответственно.Это вроде Funcletizer, но немного сложнее ...

Спасибо за любую помощь.

1 Ответ

4 голосов
/ 12 октября 2010

Это интересная проблема. Я бы рассмотрел подход, состоящий из нескольких этапов:

  1. анализ выражений (возможно, снизу вверх) дерева выражений и маркировка узлов как «удаленных», «локальных» и «нейтральных»
  2. нисходящая идентификация «удаленных» подвыражений
  3. удаленное выполнение запроса (исключение подвыражения)
  4. локальное выполнение запроса

Ниже приводится более подробная информация для каждой фазы. В разделе Замечания в конце моего ответа приведены некоторые важные замечания.

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

Этап 1: Анализ экспрессии и тегирование

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

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

Подход снизу вверх для обхода и обработки дерева выражений кажется подходящим для этого случая. Причина в том, что при обработке данного узла X, имеющего подузлы Y_1-Y_n, категория узла X сильно зависит от категорий его подузлов от Y_1 до T_n.

Перепишем предоставленный вами образец: 

entityX.SomeProperty == "Hello" &&
entityY.SomeOtherProperty == "Hello 2" && 
entityX.Id == entityY.Id

в схему соответствующего дерева выражений: 

&&(&&(==(Member(SomeProperty, Var(entityX)), "Hello"), 
      ==(Member(SomeOtherProperty, Var(entityY)), "Hello 2")),
   ==(Member(Id, Var(entityX)), Member(Id, Var(entityY)))

Это дерево выражений будет помечено снизу вверх. R для «удаленного», L для «локального», N для «нейтрального». Если entityX удаленно, а entityY локально, результат будет выглядеть следующим образом: 

L:&&(L:&&(R:==(R:Member(SomeProperty, R:Var(entityX)), N:"Hello"), 
          L:==(L:Member(SomeOtherProperty, L:Var(entityY)), N:"Hello 2")),
     L:==(R:Member(Id, R:Var(entityX)), L:Member(Id, L:Var(entityY)))

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

  • выполнение доступа к свойству объекта даст ту же категорию, что и объект;
  • строковый литерал будет нейтральным;
  • сравнение равенства локального и удаленного подвыражения будет иметь локальную категорию;
  • оператор and снова будет отдавать предпочтение локальному, а не удаленному.

Тем не менее, вы можете рассмотреть возможность объединения подхода «снизу вверх» с проходом оптимизации «сверху вниз» для получения лучших результатов. Считайте это (символическим): R == R + L. Как вы хотите выполнить сравнение равенства? При чистом подходе снизу вверх вы выполняете его локально. Однако в некоторых ситуациях может быть лучше предварительно рассчитать L локально, заменить подвыражение фактическим значением (т.е. нейтральным) и выполнить сравнение на равенство удаленно. Другими словами, вы можете в конечном итоге реализовать оптимизатор плана запросов.

Фаза 2: Идентификация удаленных подвыражений

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

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

Следовательно, возможно, потребуется выполнитьзаданный запрос с несколькими обходами к удаленному обработчику запросов.Альтернативный подход состоял бы в том, чтобы разрешить двунаправленную связь между процессорами запросов, чтобы «удаленный» процессор мог идентифицировать «локальное» (на самом деле «удаленное» с его точки зрения) выражение и вызвать обратный вызов «локального» процессорачтобы выполнить его.

Этап 3: Удаленное выполнение запроса

На третьем этапе список удаленных подвыражений будет отправлен «удаленному» обработчику запросов для выполнения.(См. Также обсуждение на предыдущем этапе.)

Вопрос также состоит в том, как определить подвыражения, которые можно использовать для эффективного ограничения результирующего набора данных, возвращаемых удаленным процессором запросов.Для этого необходимо учитывать семантику операторов верхнего уровня в дереве выражений (обычно && и ||).Оценка коротких замыканий && и || немного усложняет ситуацию, поскольку препроцессор запросов может не переупорядочивать операнды.

Этап 4: Локальное выполнение запроса

Когда выполняются все удаленные подвыраженияих вхождения в исходном дереве выражений заменяются собранными результатами.

Примечания

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

  • Для обработки псевдонимов данных (как в PropX = entityX … i.PropX.SomeProperty == "Hello" пример, который вы предоставили) вам придется выполнить анализ потока данных.Здесь вы, скорее всего, получите набор дел, которые будут слишком сложными и заслуживающими рассмотрения.

...