- 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
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;
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")
}
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) {
fragmentEntities = fragmentRepository.findByAnchorAndXpathIn(anchorEntity, ancestorXpaths);
}
}
-
- return createDataNodesFromProxiedFragmentEntities(fetchDescendantsOption, anchorEntity, fragmentEntities);
+ fragmentEntities = prefetchDescendantsForFragmentEntities(fetchDescendantsOption, anchorEntity,
+ fragmentEntities);
+ return createDataNodesFromFragmentEntities(fetchDescendantsOption, fragmentEntities);
}
@Override
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());
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());
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
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) {
deleteByAnchorIdAndXpathLikeAny(anchorId, listXpathPatterns);\r
}\r
\r
- @Query("SELECT f FROM FragmentEntity f WHERE anchor = :anchor"\r
- + " AND (xpath = :parentXpath OR xpath LIKE CONCAT(:parentXpath,'/%'))")\r
- List<FragmentExtract> findByAnchorAndParentXpath(@Param("anchor") AnchorEntity anchorEntity,\r
- @Param("parentXpath") String parentXpath);\r
-\r
- @Query(value = "SELECT id, anchor_id AS anchorId, xpath, parent_id AS parentId,"\r
- + " CAST(attributes AS TEXT) AS attributes"\r
- + " FROM FRAGMENT WHERE anchor_id = :anchorId AND xpath ~ :xpathRegex",\r
- nativeQuery = true)\r
- List<FragmentExtract> quickFindWithDescendants(@Param("anchorId") int anchorId,\r
- @Param("xpathRegex") String xpathRegex);\r
-\r
- @Query(value = "SELECT id, anchor_id AS anchorId, xpath, parent_id AS parentId,"\r
- + " CAST(attributes AS TEXT) AS attributes"\r
- + " FROM FRAGMENT WHERE dataspace_id = :dataspaceId AND xpath ~ :xpathRegex",\r
- nativeQuery = true)\r
- List<FragmentExtract> quickFindWithDescendantsAcrossAnchors(@Param("dataspaceId") int dataspaceId,\r
- @Param("xpathRegex") String xpathRegex);\r
-\r
@Query(value = "SELECT xpath FROM fragment WHERE anchor_id = :anchorId AND xpath = ANY (:xpaths)",\r
nativeQuery = true)\r
List<String> findAllXpathByAnchorIdAndXpathIn(@Param("anchorId") int anchorId,\r
return findExtractsWithDescendants(anchorId, xpaths.toArray(new String[0]), maxDepth);\r
}\r
\r
+ @Query(value\r
+ = "WITH RECURSIVE parent_search AS ("\r
+ + " SELECT id, 0 AS depth "\r
+ + " FROM fragment "\r
+ + " WHERE id = ANY (:ids) "\r
+ + " UNION "\r
+ + " SELECT c.id, depth + 1 "\r
+ + " FROM fragment c INNER JOIN parent_search p ON c.parent_id = p.id"\r
+ + " WHERE depth <= (SELECT CASE WHEN :maxDepth = -1 THEN " + Integer.MAX_VALUE + " ELSE :maxDepth END) "\r
+ + ") "\r
+ + "SELECT f.id, anchor_id AS anchorId, xpath, f.parent_id AS parentId, CAST(attributes AS TEXT) AS attributes "\r
+ + "FROM fragment f INNER JOIN parent_search p ON f.id = p.id",\r
+ nativeQuery = true\r
+ )\r
+ List<FragmentExtract> findExtractsWithDescendantsByIds(@Param("ids") long[] ids,\r
+ @Param("maxDepth") int maxDepth);\r
+\r
+ default List<FragmentExtract> findExtractsWithDescendantsByIds(final Collection<Long> ids, final int maxDepth) {\r
+ return findExtractsWithDescendantsByIds(ids.stream().mapToLong(id -> id).toArray(), maxDepth);\r
+ }\r
+\r
}\r
where: 'the following parameters are used'
scenario | anchor | cpsPath || durationLimit | expectedNumberOfDataNodes
'top element' | 'openroadm1' | '/openroadm-devices' || 250 | 50 * 86 + 1
- 'leaf condition' | 'openroadm2' | '//openroadm-device[@ne-state="inservice"]' || 650 | 50 * 86
+ 'leaf condition' | 'openroadm2' | '//openroadm-device[@ne-state="inservice"]' || 250 | 50 * 86
'ancestors' | 'openroadm3' | '//openroadm-device/ancestor::openroadm-devices' || 250 | 50 * 86 + 1
- 'leaf condition + ancestors' | 'openroadm4' | '//openroadm-device[@status="success"]/ancestor::openroadm-devices' || 500 | 50 * 86 + 1
+ 'leaf condition + ancestors' | 'openroadm4' | '//openroadm-device[@status="success"]/ancestor::openroadm-devices' || 250 | 50 * 86 + 1
}
def 'Query complete data trees across all anchors with #scenario.'() {
recordAndAssertPerformance("Query across anchors ${scenario}", durationLimit, durationInMillis)
where: 'the following parameters are used'
scenario | cpspath || durationLimit | expectedNumberOfDataNodes
- 'top element' | '/openroadm-devices' || 1 | 5 * (50 * 86 + 1)
- 'leaf condition' | '//openroadm-device[@ne-state="inservice"]' || 2500 | 5 * (50 * 86)
- 'ancestors' | '//openroadm-device/ancestor::openroadm-devices' || 12000 | 5 * (50 * 86 + 1)
+ 'top element' | '/openroadm-devices' || 1000 | 5 * (50 * 86 + 1)
+ 'leaf condition' | '//openroadm-device[@ne-state="inservice"]' || 1000 | 5 * (50 * 86)
+ 'ancestors' | '//openroadm-device/ancestor::openroadm-devices' || 1000 | 5 * (50 * 86 + 1)
'leaf condition + ancestors' | '//openroadm-device[@status="success"]/ancestor::openroadm-devices' || 1000 | 5 * (50 * 86 + 1)
}
where: 'the following parameters are used'
scenario | fetchDescendantsOption | anchor || durationLimit | expectedNumberOfDataNodes
'no descendants' | OMIT_DESCENDANTS | 'openroadm1' || 100 | 50
- 'direct descendants' | DIRECT_CHILDREN_ONLY | 'openroadm2' || 400 | 50 * 2
- 'all descendants' | INCLUDE_ALL_DESCENDANTS | 'openroadm3' || 500 | 50 * 86
+ 'direct descendants' | DIRECT_CHILDREN_ONLY | 'openroadm2' || 150 | 50 * 2
+ 'all descendants' | INCLUDE_ALL_DESCENDANTS | 'openroadm3' || 200 | 50 * 86
}
def 'Query ancestors with #scenario.'() {
where: 'the following parameters are used'
scenario | fetchDescendantsOption | anchor || durationLimit | expectedNumberOfDataNodes
'no descendants' | OMIT_DESCENDANTS | 'openroadm1' || 100 | 1
- 'direct descendants' | DIRECT_CHILDREN_ONLY | 'openroadm2' || 250 | 1 + 50
- 'all descendants' | INCLUDE_ALL_DESCENDANTS | 'openroadm3' || 400 | 1 + 50 * 86
+ 'direct descendants' | DIRECT_CHILDREN_ONLY | 'openroadm2' || 200 | 1 + 50
+ 'all descendants' | INCLUDE_ALL_DESCENDANTS | 'openroadm3' || 300 | 1 + 50 * 86
}
}
Code Review / cps.git / commitdiff