From d94dd78ad001d72182133f7681b979d730698d83 Mon Sep 17 00:00:00 2001 From: danielhanrahan Date: Wed, 3 May 2023 19:51:27 +0100 Subject: 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 Change-Id: If5f0b54a88af1cb681006bbeca7043345dcdc8da --- .../spi/impl/CpsDataPersistenceServiceImpl.java | 74 +++++----------------- .../cps/spi/repository/FragmentQueryBuilder.java | 22 +------ .../cps/spi/repository/FragmentRepository.java | 40 ++++++------ 3 files changed, 37 insertions(+), 99 deletions(-) (limited to 'cps-ri/src') 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 be5c66db9..dbad1552a 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 buildFragmentEntitiesFromFragmentExtracts(final AnchorEntity anchorEntity, - final String normalizedXpath) { - final List 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 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 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 prefetchDescendantsForFragmentEntities( + final FetchDescendantsOption fetchDescendantsOption, + final AnchorEntity anchorEntity, + final Collection proxiedFragmentEntities) { + if (FetchDescendantsOption.OMIT_DESCENDANTS.equals(fetchDescendantsOption)) { + return proxiedFragmentEntities; + } - private List getDataNodesUsingRegexQuickFind(final FetchDescendantsOption fetchDescendantsOption, - final DataspaceEntity dataspaceEntity, - final AnchorEntity anchorEntity, - final CpsPathQuery cpsPathQuery) { - final String xpathRegex = FragmentQueryBuilder.getXpathSqlRegexForQuickFindWithDescendants(cpsPathQuery); - final List fragmentExtracts = (anchorEntity == ALL_ANCHORS) - ? fragmentRepository.quickFindWithDescendantsAcrossAnchors(dataspaceEntity.getId(), xpathRegex) - : fragmentRepository.quickFindWithDescendants(anchorEntity.getId(), xpathRegex); - final Collection fragmentEntities = - createFragmentEntitiesFromFragmentExtracts(anchorEntity, fragmentExtracts); - return createDataNodesFromFragmentEntities(fetchDescendantsOption, fragmentEntities); - } + final List fragmentEntityIds = proxiedFragmentEntities.stream() + .map(FragmentEntity::getId).collect(Collectors.toList()); + + final List fragmentExtracts = + fragmentRepository.findExtractsWithDescendantsByIds(fragmentEntityIds, fetchDescendantsOption.getDepth()); - private Collection createFragmentEntitiesFromFragmentExtracts( - final AnchorEntity anchorEntity, final Collection fragmentExtracts) { if (anchorEntity == ALL_ANCHORS) { final Collection 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 createDataNodesFromProxiedFragmentEntities( - final FetchDescendantsOption fetchDescendantsOption, - final AnchorEntity anchorEntity, - final Collection proxiedFragmentEntities) { - final List 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 unproxiedFragmentEntities = - buildFragmentEntitiesFromFragmentExtracts(anchorEntityForFragmentExtract, normalizedXpath); - for (final FragmentEntity unproxiedFragmentEntity : unproxiedFragmentEntities) { - dataNodes.add(toDataNode(unproxiedFragmentEntity, fetchDescendantsOption)); - } - } - } - return Collections.unmodifiableList(dataNodes); - } - private List createDataNodesFromFragmentEntities(final FetchDescendantsOption fetchDescendantsOption, final Collection fragmentEntities) { final List 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 515bbd616..76cfaa89f 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 d20e4d35a..a2763184a 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, deleteByAnchorIdAndXpathLikeAny(anchorId, listXpathPatterns); } - @Query("SELECT f FROM FragmentEntity f WHERE anchor = :anchor" - + " AND (xpath = :parentXpath OR xpath LIKE CONCAT(:parentXpath,'/%'))") - List 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 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 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 findAllXpathByAnchorIdAndXpathIn(@Param("anchorId") int anchorId, @@ -150,4 +131,25 @@ public interface FragmentRepository extends JpaRepository, 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 findExtractsWithDescendantsByIds(@Param("ids") long[] ids, + @Param("maxDepth") int maxDepth); + + default List findExtractsWithDescendantsByIds(final Collection ids, final int maxDepth) { + return findExtractsWithDescendantsByIds(ids.stream().mapToLong(id -> id).toArray(), maxDepth); + } + } -- cgit 1.2.3-korg