Use recursive SQL to fetch descendants in CpsPath queries (CPS-1664 #4)

- Add recursive SQL method to fetch descendants from queries.
  This changes worst-case complexity from quadratic to linear,
  resulting in extremely large performance increase for large
  number of datanodes.
- Remove RegexQuickFind algorithm as it is no longer faster.
- Updated query performance test timings

Issue-ID: CPS-1664
Signed-off-by: danielhanrahan <daniel.hanrahan@est.tech>
Change-Id: If5f0b54a88af1cb681006bbeca7043345dcdc8da

3 files changed, 37 insertions, 99 deletions

diff --git a/cps-ri/src/main/java/org/onap/cps/spi/impl/CpsDataPersistenceServiceImpl.java b/cps-ri/src/main/java/org/onap/cps/spi/impl/CpsDataPersistenceServiceImpl.java
index be5c66db9a..dbad1552a9 100644
--- a/cps-ri/src/main/java/org/onap/cps/spi/impl/CpsDataPersistenceServiceImpl.java
+++ b/cps-ri/src/main/java/org/onap/cps/spi/impl/CpsDataPersistenceServiceImpl.java
@@ -65,7 +65,6 @@ import org.onap.cps.spi.model.DataNode;
 import org.onap.cps.spi.model.DataNodeBuilder;
 import org.onap.cps.spi.repository.AnchorRepository;
 import org.onap.cps.spi.repository.DataspaceRepository;
-import org.onap.cps.spi.repository.FragmentQueryBuilder;
 import org.onap.cps.spi.repository.FragmentRepository;
 import org.onap.cps.spi.utils.SessionManager;
 import org.onap.cps.utils.JsonObjectMapper;
@@ -305,13 +304,6 @@ public class CpsDataPersistenceServiceImpl implements CpsDataPersistenceService
         return fragmentEntity;
     }
 
-    private Collection<FragmentEntity> buildFragmentEntitiesFromFragmentExtracts(final AnchorEntity anchorEntity,
-                                                                                 final String normalizedXpath) {
-        final List<FragmentExtract> fragmentExtracts =
-            fragmentRepository.findByAnchorAndParentXpath(anchorEntity, normalizedXpath);
-        return FragmentEntityArranger.toFragmentEntityTrees(anchorEntity, fragmentExtracts);
-    }
-
     @Override
     @Timed(value = "cps.data.persistence.service.datanode.query",
             description = "Time taken to query data nodes")
@@ -328,16 +320,11 @@ public class CpsDataPersistenceServiceImpl implements CpsDataPersistenceService
         }
 
         Collection<FragmentEntity> fragmentEntities;
-        if (canUseRegexQuickFind(fetchDescendantsOption, cpsPathQuery)) {
-            return getDataNodesUsingRegexQuickFind(fetchDescendantsOption, dataspaceEntity, anchorEntity, cpsPathQuery);
-        }
-
         if (anchorEntity == ALL_ANCHORS) {
             fragmentEntities = fragmentRepository.findByDataspaceAndCpsPath(dataspaceEntity, cpsPathQuery);
         } else {
             fragmentEntities = fragmentRepository.findByAnchorAndCpsPath(anchorEntity, cpsPathQuery);
         }
-
         if (cpsPathQuery.hasAncestorAxis()) {
             final Collection<String> ancestorXpaths = processAncestorXpath(fragmentEntities, cpsPathQuery);
             if (anchorEntity == ALL_ANCHORS) {
@@ -346,8 +333,9 @@ public class CpsDataPersistenceServiceImpl implements CpsDataPersistenceService
                 fragmentEntities = fragmentRepository.findByAnchorAndXpathIn(anchorEntity, ancestorXpaths);
             }
         }
-
-        return createDataNodesFromProxiedFragmentEntities(fetchDescendantsOption, anchorEntity, fragmentEntities);
+        fragmentEntities = prefetchDescendantsForFragmentEntities(fetchDescendantsOption, anchorEntity,
+            fragmentEntities);
+        return createDataNodesFromFragmentEntities(fetchDescendantsOption, fragmentEntities);
     }
 
     @Override
@@ -356,30 +344,20 @@ public class CpsDataPersistenceServiceImpl implements CpsDataPersistenceService
         return queryDataNodes(dataspaceName, QUERY_ACROSS_ANCHORS, cpsPath, fetchDescendantsOption);
     }
 
-    private static boolean canUseRegexQuickFind(final FetchDescendantsOption fetchDescendantsOption,
-                                                final CpsPathQuery cpsPathQuery) {
-        return fetchDescendantsOption.equals(FetchDescendantsOption.INCLUDE_ALL_DESCENDANTS)
-            && !cpsPathQuery.hasAncestorAxis()
-            && !cpsPathQuery.hasLeafConditions()
-            && !cpsPathQuery.hasTextFunctionCondition()
-            && !cpsPathQuery.hasContainsFunctionCondition();
-    }
+    private Collection<FragmentEntity> prefetchDescendantsForFragmentEntities(
+                                            final FetchDescendantsOption fetchDescendantsOption,
+                                            final AnchorEntity anchorEntity,
+                                            final Collection<FragmentEntity> proxiedFragmentEntities) {
+        if (FetchDescendantsOption.OMIT_DESCENDANTS.equals(fetchDescendantsOption)) {
+            return proxiedFragmentEntities;
+        }
 
-    private List<DataNode> getDataNodesUsingRegexQuickFind(final FetchDescendantsOption fetchDescendantsOption,
-                                                           final DataspaceEntity dataspaceEntity,
-                                                           final AnchorEntity anchorEntity,
-                                                           final CpsPathQuery cpsPathQuery) {
-        final String xpathRegex = FragmentQueryBuilder.getXpathSqlRegexForQuickFindWithDescendants(cpsPathQuery);
-        final List<FragmentExtract> fragmentExtracts = (anchorEntity == ALL_ANCHORS)
-            ? fragmentRepository.quickFindWithDescendantsAcrossAnchors(dataspaceEntity.getId(), xpathRegex)
-            : fragmentRepository.quickFindWithDescendants(anchorEntity.getId(), xpathRegex);
-        final Collection<FragmentEntity> fragmentEntities =
-            createFragmentEntitiesFromFragmentExtracts(anchorEntity, fragmentExtracts);
-        return createDataNodesFromFragmentEntities(fetchDescendantsOption, fragmentEntities);
-    }
+        final List<Long> fragmentEntityIds = proxiedFragmentEntities.stream()
+            .map(FragmentEntity::getId).collect(Collectors.toList());
+
+        final List<FragmentExtract> fragmentExtracts =
+            fragmentRepository.findExtractsWithDescendantsByIds(fragmentEntityIds, fetchDescendantsOption.getDepth());
 
-    private Collection<FragmentEntity> createFragmentEntitiesFromFragmentExtracts(
-                    final AnchorEntity anchorEntity, final Collection<FragmentExtract> fragmentExtracts) {
         if (anchorEntity == ALL_ANCHORS) {
             final Collection<Integer> anchorIds = fragmentExtracts.stream()
                 .map(FragmentExtract::getAnchorId).collect(Collectors.toSet());
@@ -391,28 +369,6 @@ public class CpsDataPersistenceServiceImpl implements CpsDataPersistenceService
         return FragmentEntityArranger.toFragmentEntityTrees(anchorEntity, fragmentExtracts);
     }
 
-    private List<DataNode> createDataNodesFromProxiedFragmentEntities(
-                                            final FetchDescendantsOption fetchDescendantsOption,
-                                            final AnchorEntity anchorEntity,
-                                            final Collection<FragmentEntity> proxiedFragmentEntities) {
-        final List<DataNode> dataNodes = new ArrayList<>(proxiedFragmentEntities.size());
-        for (final FragmentEntity proxiedFragmentEntity : proxiedFragmentEntities) {
-            if (FetchDescendantsOption.OMIT_DESCENDANTS.equals(fetchDescendantsOption)) {
-                dataNodes.add(toDataNode(proxiedFragmentEntity, fetchDescendantsOption));
-            } else {
-                final String normalizedXpath = getNormalizedXpath(proxiedFragmentEntity.getXpath());
-                final AnchorEntity anchorEntityForFragmentExtract = (anchorEntity == ALL_ANCHORS)
-                        ? proxiedFragmentEntity.getAnchor() : anchorEntity;
-                final Collection<FragmentEntity> unproxiedFragmentEntities =
-                    buildFragmentEntitiesFromFragmentExtracts(anchorEntityForFragmentExtract, normalizedXpath);
-                for (final FragmentEntity unproxiedFragmentEntity : unproxiedFragmentEntities) {
-                    dataNodes.add(toDataNode(unproxiedFragmentEntity, fetchDescendantsOption));
-                }
-            }
-        }
-        return Collections.unmodifiableList(dataNodes);
-    }
-
     private List<DataNode> createDataNodesFromFragmentEntities(final FetchDescendantsOption fetchDescendantsOption,
                                                                final Collection<FragmentEntity> fragmentEntities) {
         final List<DataNode> dataNodes = new ArrayList<>(fragmentEntities.size());
diff --git a/cps-ri/src/main/java/org/onap/cps/spi/repository/FragmentQueryBuilder.java b/cps-ri/src/main/java/org/onap/cps/spi/repository/FragmentQueryBuilder.java
index 515bbd6165..76cfaa89f8 100644
--- a/cps-ri/src/main/java/org/onap/cps/spi/repository/FragmentQueryBuilder.java
+++ b/cps-ri/src/main/java/org/onap/cps/spi/repository/FragmentQueryBuilder.java
@@ -46,7 +46,6 @@ public class FragmentQueryBuilder {
     private static final String REGEX_ABSOLUTE_PATH_PREFIX = "^";
     private static final String REGEX_DESCENDANT_PATH_PREFIX = "^.*\\/";
     private static final String REGEX_OPTIONAL_LIST_INDEX_POSTFIX = "(\\[@(?!.*\\[).*?])?$";
-    private static final String REGEX_FOR_QUICK_FIND_WITH_DESCENDANTS = "(\\[@.*?])?(\\/.*)?$";
     private static final AnchorEntity ACROSS_ALL_ANCHORS = null;
 
     @PersistenceContext
@@ -77,31 +76,12 @@ public class FragmentQueryBuilder {
         return getQueryForDataspaceOrAnchorAndCpsPath(dataspaceEntity, ACROSS_ALL_ANCHORS, cpsPathQuery);
     }
 
-    /**
-     * Create a regular expression (string) for matching xpaths based on the given cps path query.
-     *
-     * @param cpsPathQuery the cps path query to determine the required regular expression
-     * @return a string representing the required regular expression
-     */
-    public static String getXpathSqlRegex(final CpsPathQuery cpsPathQuery) {
+    private static String getXpathSqlRegex(final CpsPathQuery cpsPathQuery) {
         final StringBuilder xpathRegexBuilder = getRegexStringBuilderWithPrefix(cpsPathQuery);
         xpathRegexBuilder.append(REGEX_OPTIONAL_LIST_INDEX_POSTFIX);
         return xpathRegexBuilder.toString();
     }
 
-    /**
-     * Create a regular expression (string) for matching xpaths with (all) descendants
-     * based on the given cps path query.
-     *
-     * @param cpsPathQuery the cps path query to determine the required regular expression
-     * @return a string representing the required regular expression
-     */
-    public static String getXpathSqlRegexForQuickFindWithDescendants(final CpsPathQuery cpsPathQuery) {
-        final StringBuilder xpathRegexBuilder = getRegexStringBuilderWithPrefix(cpsPathQuery);
-        xpathRegexBuilder.append(REGEX_FOR_QUICK_FIND_WITH_DESCENDANTS);
-        return xpathRegexBuilder.toString();
-    }
-
     private Query getQueryForDataspaceOrAnchorAndCpsPath(final DataspaceEntity dataspaceEntity,
                                                          final AnchorEntity anchorEntity,
                                                          final CpsPathQuery cpsPathQuery) {
diff --git a/cps-ri/src/main/java/org/onap/cps/spi/repository/FragmentRepository.java b/cps-ri/src/main/java/org/onap/cps/spi/repository/FragmentRepository.java
index d20e4d35a4..a2763184a6 100755
--- a/cps-ri/src/main/java/org/onap/cps/spi/repository/FragmentRepository.java
+++ b/cps-ri/src/main/java/org/onap/cps/spi/repository/FragmentRepository.java
@@ -93,25 +93,6 @@ public interface FragmentRepository extends JpaRepository<FragmentEntity, Long>,
         deleteByAnchorIdAndXpathLikeAny(anchorId, listXpathPatterns);

     }

 

-    @Query("SELECT f FROM FragmentEntity f WHERE anchor = :anchor"

-        + " AND (xpath = :parentXpath OR xpath LIKE CONCAT(:parentXpath,'/%'))")

-    List<FragmentExtract> findByAnchorAndParentXpath(@Param("anchor") AnchorEntity anchorEntity,

-                                                     @Param("parentXpath") String parentXpath);

-

-    @Query(value = "SELECT id, anchor_id AS anchorId, xpath, parent_id AS parentId,"

-        + " CAST(attributes AS TEXT) AS attributes"

-        + " FROM FRAGMENT WHERE anchor_id = :anchorId AND xpath ~ :xpathRegex",

-        nativeQuery = true)

-    List<FragmentExtract> quickFindWithDescendants(@Param("anchorId") int anchorId,

-                                                   @Param("xpathRegex") String xpathRegex);

-

-    @Query(value = "SELECT id, anchor_id AS anchorId, xpath, parent_id AS parentId,"

-        + " CAST(attributes AS TEXT) AS attributes"

-        + " FROM FRAGMENT WHERE dataspace_id = :dataspaceId AND xpath ~ :xpathRegex",

-        nativeQuery = true)

-    List<FragmentExtract> quickFindWithDescendantsAcrossAnchors(@Param("dataspaceId") int dataspaceId,

-                                                                @Param("xpathRegex") String xpathRegex);

-

     @Query(value = "SELECT xpath FROM fragment WHERE anchor_id = :anchorId AND xpath = ANY (:xpaths)",

         nativeQuery = true)

     List<String> findAllXpathByAnchorIdAndXpathIn(@Param("anchorId") int anchorId,

@@ -150,4 +131,25 @@ public interface FragmentRepository extends JpaRepository<FragmentEntity, Long>,
         return findExtractsWithDescendants(anchorId, xpaths.toArray(new String[0]), maxDepth);

     }

 

+    @Query(value

+        = "WITH RECURSIVE parent_search AS ("

+        + "  SELECT id, 0 AS depth "

+        + "    FROM fragment "

+        + "   WHERE id = ANY (:ids) "

+        + "   UNION "

+        + "  SELECT c.id, depth + 1 "

+        + "    FROM fragment c INNER JOIN parent_search p ON c.parent_id = p.id"

+        + "   WHERE depth <= (SELECT CASE WHEN :maxDepth = -1 THEN " + Integer.MAX_VALUE + " ELSE :maxDepth END) "

+        + ") "

+        + "SELECT f.id, anchor_id AS anchorId, xpath, f.parent_id AS parentId, CAST(attributes AS TEXT) AS attributes "

+        + "FROM fragment f INNER JOIN parent_search p ON f.id = p.id",

+        nativeQuery = true

+    )

+    List<FragmentExtract> findExtractsWithDescendantsByIds(@Param("ids") long[] ids,

+                                                           @Param("maxDepth") int maxDepth);

+

+    default List<FragmentExtract> findExtractsWithDescendantsByIds(final Collection<Long> ids, final int maxDepth) {

+        return findExtractsWithDescendantsByIds(ids.stream().mapToLong(id -> id).toArray(), maxDepth);

+    }

+

 }