From a42e0a794703ef9b8c9c0ab7d849df3b720fdc43 Mon Sep 17 00:00:00 2001
From: Simon Brandhof <simon.brandhof@sonarsource.com>
Date: Mon, 29 Jan 2018 17:49:14 +0100
Subject: [PATCH] SONAR-10052 fix N+1 syndrome when loading profile descendants

---
 .../db/qualityprofile/QualityProfileDao.java  | 19 ++++---
 .../qualityprofile/QualityProfileMapper.java  |  2 +-
 .../qualityprofile/QualityProfileMapper.xml   |  9 ++--
 .../qualityprofile/QualityProfileDaoTest.java | 52 ++++++++++++++++++-
 .../server/qualityprofile/RuleActivator.java  |  8 ++-
 .../qualityprofile/ws/DeleteAction.java       | 12 +++--
 .../qualityprofile/ws/InheritanceAction.java  |  5 +-
 ...gisterQualityProfilesNotificationTest.java | 15 +++---
 8 files changed, 89 insertions(+), 33 deletions(-)

diff --git a/server/sonar-db-dao/src/main/java/org/sonar/db/qualityprofile/QualityProfileDao.java b/server/sonar-db-dao/src/main/java/org/sonar/db/qualityprofile/QualityProfileDao.java
index 8820d57cad0..1a1d7701ae1 100644
--- a/server/sonar-db-dao/src/main/java/org/sonar/db/qualityprofile/QualityProfileDao.java
+++ b/server/sonar-db-dao/src/main/java/org/sonar/db/qualityprofile/QualityProfileDao.java
@@ -38,6 +38,7 @@ import org.sonar.db.component.ComponentDto;
 import org.sonar.db.organization.OrganizationDto;
 
 import static com.google.common.base.Preconditions.checkArgument;
+import static java.util.Collections.emptyList;
 import static org.sonar.db.DatabaseUtils.executeLargeInputs;
 import static org.sonar.db.DatabaseUtils.executeLargeUpdates;
 
@@ -148,19 +149,21 @@ public class QualityProfileDao implements Dao {
     return mapper(dbSession).selectByLanguage(organization.getUuid(), language);
   }
 
-  public List<QProfileDto> selectChildren(DbSession dbSession, QProfileDto profile) {
-    return mapper(dbSession).selectChildren(profile.getKee());
+  public List<QProfileDto> selectChildren(DbSession dbSession, Collection<QProfileDto> profiles) {
+    List<String> uuids = profiles.stream().map(QProfileDto::getKee).collect(MoreCollectors.toArrayList(profiles.size()));
+    return DatabaseUtils.executeLargeInputs(uuids, chunk -> mapper(dbSession).selectChildren(chunk));
   }
 
   /**
-   * All descendants, in the top-down order.
+   * All descendants, in any order. The specified profiles are not included into results.
    */
-  public List<QProfileDto> selectDescendants(DbSession dbSession, QProfileDto profile) {
-    List<QProfileDto> descendants = new ArrayList<>();
-    for (QProfileDto child : selectChildren(dbSession, profile)) {
-      descendants.add(child);
-      descendants.addAll(selectDescendants(dbSession, child));
+  public Collection<QProfileDto> selectDescendants(DbSession dbSession, Collection<QProfileDto> profiles) {
+    if (profiles.isEmpty()) {
+      return emptyList();
     }
+    Collection<QProfileDto> children = selectChildren(dbSession, profiles);
+    List<QProfileDto> descendants = new ArrayList<>(children);
+    descendants.addAll(selectDescendants(dbSession, children));
     return descendants;
   }
 
diff --git a/server/sonar-db-dao/src/main/java/org/sonar/db/qualityprofile/QualityProfileMapper.java b/server/sonar-db-dao/src/main/java/org/sonar/db/qualityprofile/QualityProfileMapper.java
index 5dcb7fc1a61..fd3751cc09a 100644
--- a/server/sonar-db-dao/src/main/java/org/sonar/db/qualityprofile/QualityProfileMapper.java
+++ b/server/sonar-db-dao/src/main/java/org/sonar/db/qualityprofile/QualityProfileMapper.java
@@ -76,7 +76,7 @@ public interface QualityProfileMapper {
 
   // INHERITANCE
 
-  List<QProfileDto> selectChildren(String uuid);
+  List<QProfileDto> selectChildren(@Param("uuids") Collection<String> uuids);
 
   // PROJECTS
 
diff --git a/server/sonar-db-dao/src/main/resources/org/sonar/db/qualityprofile/QualityProfileMapper.xml b/server/sonar-db-dao/src/main/resources/org/sonar/db/qualityprofile/QualityProfileMapper.xml
index e7f433fb441..2bbeecc2b0b 100644
--- a/server/sonar-db-dao/src/main/resources/org/sonar/db/qualityprofile/QualityProfileMapper.xml
+++ b/server/sonar-db-dao/src/main/resources/org/sonar/db/qualityprofile/QualityProfileMapper.xml
@@ -201,14 +201,15 @@
       and oqp.organization_uuid = #{organizationUuid, jdbcType=VARCHAR}
   </select>
 
+  <!-- the join on "org_qprofiles parent" is required to benefit from the index on uuid -->
   <select id="selectChildren" parameterType="string" resultType="org.sonar.db.qualityprofile.QProfileDto">
-    select
-    <include refid="qProfileColumns"/>
+    select <include refid="qProfileColumns"/>
     from org_qprofiles oqp
     inner join rules_profiles rp on oqp.rules_profile_uuid = rp.kee
+    inner join org_qprofiles parent on parent.uuid = oqp.parent_uuid
     where
-      oqp.parent_uuid = #{uuid, jdbcType=VARCHAR}
-    ORDER BY rp.name
+      parent.uuid in <foreach collection="uuids" item="uuid" open="(" close=")" separator=",">#{uuid, jdbcType=VARCHAR}</foreach>
+    order by rp.name
   </select>
 
   <select id="countProjectsByOrganizationAndProfiles" resultType="KeyLongValue" parameterType="map">
diff --git a/server/sonar-db-dao/src/test/java/org/sonar/db/qualityprofile/QualityProfileDaoTest.java b/server/sonar-db-dao/src/test/java/org/sonar/db/qualityprofile/QualityProfileDaoTest.java
index 5e00dba9177..73f4c60c7b0 100644
--- a/server/sonar-db-dao/src/test/java/org/sonar/db/qualityprofile/QualityProfileDaoTest.java
+++ b/server/sonar-db-dao/src/test/java/org/sonar/db/qualityprofile/QualityProfileDaoTest.java
@@ -43,6 +43,7 @@ import static com.google.common.collect.ImmutableList.of;
 import static com.google.common.collect.Lists.newArrayList;
 import static java.util.Arrays.asList;
 import static java.util.Collections.emptyList;
+import static java.util.Collections.singleton;
 import static java.util.Collections.singletonList;
 import static org.apache.commons.lang.RandomStringUtils.randomAlphanumeric;
 import static org.assertj.core.api.Assertions.assertThat;
@@ -466,7 +467,7 @@ public class QualityProfileDaoTest {
       .setIsBuiltIn(false);
     underTest.insert(dbSession, original6);
 
-    List<QProfileDto> dtos = underTest.selectChildren(dbSession, original3);
+    List<QProfileDto> dtos = underTest.selectChildren(dbSession, singleton(original3));
 
     assertThat(dtos).hasSize(2);
 
@@ -481,6 +482,55 @@ public class QualityProfileDaoTest {
     assertThat(dto2.getParentKee()).isEqualTo("java_parent");
   }
 
+  @Test
+  public void selectDescendants_returns_empty_if_no_children() {
+    QProfileDto base = db.qualityProfiles().insert(db.getDefaultOrganization());
+
+    Collection<QProfileDto> descendants = underTest.selectDescendants(dbSession, singleton(base));
+
+    assertThat(descendants).isEmpty();
+  }
+
+  @Test
+  public void selectDescendants_returns_profile_does_not_exist() {
+    Collection<QProfileDto> descendants = underTest.selectDescendants(dbSession, singleton(new QProfileDto().setKee("unknown")));
+
+    assertThat(descendants).isEmpty();
+  }
+
+  @Test
+  public void selectDescendants_returns_descendants_in_any_order() {
+    QProfileDto base1 = db.qualityProfiles().insert(db.getDefaultOrganization());
+    QProfileDto child1OfBase1 = db.qualityProfiles().insert(db.getDefaultOrganization(), p -> p.setParentKee(base1.getKee()));
+    QProfileDto child2OfBase1 = db.qualityProfiles().insert(db.getDefaultOrganization(), p -> p.setParentKee(base1.getKee()));
+    QProfileDto grandChildOfBase1 = db.qualityProfiles().insert(db.getDefaultOrganization(), p -> p.setParentKee(child1OfBase1.getKee()));
+    QProfileDto base2 = db.qualityProfiles().insert(db.getDefaultOrganization());
+    QProfileDto childOfBase2 = db.qualityProfiles().insert(db.getDefaultOrganization(), p -> p.setParentKee(base2.getKee()));
+    QProfileDto grandChildOfBase2 = db.qualityProfiles().insert(db.getDefaultOrganization(), p -> p.setParentKee(childOfBase2.getKee()));
+    QProfileDto other = db.qualityProfiles().insert(db.getDefaultOrganization());
+
+    // descendants of a single base profile
+    verifyDescendants(singleton(base1), asList(child1OfBase1, child2OfBase1, grandChildOfBase1));
+    verifyDescendants(singleton(child1OfBase1), asList(grandChildOfBase1));
+    verifyDescendants(singleton(child2OfBase1), emptyList());
+    verifyDescendants(singleton(grandChildOfBase1), emptyList());
+
+    // descendants of a multiple base profiles
+    verifyDescendants(asList(base1, base2), asList(child1OfBase1, child2OfBase1, grandChildOfBase1, childOfBase2, grandChildOfBase2));
+    verifyDescendants(asList(base1, childOfBase2), asList(child1OfBase1, child2OfBase1, grandChildOfBase1, grandChildOfBase2));
+    verifyDescendants(asList(child1OfBase1, grandChildOfBase2), asList(grandChildOfBase1));
+    verifyDescendants(asList(other, base2), asList(childOfBase2, grandChildOfBase2));
+
+  }
+
+  private void verifyDescendants(Collection<QProfileDto> baseProfiles, Collection<QProfileDto> expectedDescendants) {
+    Collection<QProfileDto> descendants = underTest.selectDescendants(dbSession, baseProfiles);
+    String[] expectedUuids = expectedDescendants.stream().map(QProfileDto::getKee).toArray(String[]::new);
+    assertThat(descendants)
+      .extracting(QProfileDto::getKee)
+      .containsExactlyInAnyOrder(expectedUuids);
+  }
+
   @Test
   public void countProjectsByProfileKey() {
     QProfileDto profileWithoutProjects = db.qualityProfiles().insert(organization);
diff --git a/server/sonar-server/src/main/java/org/sonar/server/qualityprofile/RuleActivator.java b/server/sonar-server/src/main/java/org/sonar/server/qualityprofile/RuleActivator.java
index 3786ccdf433..757a336b4c6 100644
--- a/server/sonar-server/src/main/java/org/sonar/server/qualityprofile/RuleActivator.java
+++ b/server/sonar-server/src/main/java/org/sonar/server/qualityprofile/RuleActivator.java
@@ -51,6 +51,7 @@ import org.sonar.server.user.UserSession;
 import org.sonar.server.util.TypeValidations;
 
 import static com.google.common.base.Preconditions.checkArgument;
+import static java.util.Collections.singleton;
 import static org.sonar.server.ws.WsUtils.checkRequest;
 
 /**
@@ -374,10 +375,7 @@ public class RuleActivator {
     // load profiles
     List<QProfileDto> aliasedBuiltInProfiles = db.qualityProfileDao().selectQProfilesByRuleProfile(dbSession, builtInProfile);
     List<QProfileDto> profiles = new ArrayList<>(aliasedBuiltInProfiles);
-    for (QProfileDto aliasProfile : aliasedBuiltInProfiles) {
-      // FIXME N+1 syndrome. To be optimized by replacing db column parent_kee by ancestor_keys.
-      profiles.addAll(db.qualityProfileDao().selectDescendants(dbSession, aliasProfile));
-    }
+    profiles.addAll(db.qualityProfileDao().selectDescendants(dbSession, aliasedBuiltInProfiles));
     builder.setProfiles(profiles);
     builder.setBaseProfile(builtInProfile);
 
@@ -398,7 +396,7 @@ public class RuleActivator {
     List<RuleDefinitionDto> rules = completeWithRules(dbSession, builder, ruleKeys);
 
     // load descendant profiles
-    List<QProfileDto> profiles = new ArrayList<>(db.qualityProfileDao().selectDescendants(dbSession, profile));
+    List<QProfileDto> profiles = new ArrayList<>(db.qualityProfileDao().selectDescendants(dbSession, singleton(profile)));
     profiles.add(profile);
     if (profile.getParentKee() != null) {
       profiles.add(db.qualityProfileDao().selectByUuid(dbSession, profile.getParentKee()));
diff --git a/server/sonar-server/src/main/java/org/sonar/server/qualityprofile/ws/DeleteAction.java b/server/sonar-server/src/main/java/org/sonar/server/qualityprofile/ws/DeleteAction.java
index fde297eec76..a361327e34a 100644
--- a/server/sonar-server/src/main/java/org/sonar/server/qualityprofile/ws/DeleteAction.java
+++ b/server/sonar-server/src/main/java/org/sonar/server/qualityprofile/ws/DeleteAction.java
@@ -19,6 +19,7 @@
  */
 package org.sonar.server.qualityprofile.ws;
 
+import java.util.Collection;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
@@ -37,6 +38,7 @@ import org.sonar.server.qualityprofile.QProfileFactory;
 import org.sonar.server.user.UserSession;
 
 import static com.google.common.base.Preconditions.checkArgument;
+import static java.util.Collections.singleton;
 import static org.sonar.server.qualityprofile.ws.QProfileWsSupport.createOrganizationParam;
 
 public class DeleteAction implements QProfileWsAction {
@@ -82,7 +84,7 @@ public class DeleteAction implements QProfileWsAction {
       OrganizationDto organization = wsSupport.getOrganization(dbSession, profile);
       wsSupport.checkCanEdit(dbSession, organization, profile);
 
-      List<QProfileDto> descendants = selectDescendants(dbSession, profile);
+      Collection<QProfileDto> descendants = selectDescendants(dbSession, profile);
       ensureNoneIsMarkedAsDefault(dbSession, profile, descendants);
 
       profileFactory.delete(dbSession, merge(profile, descendants));
@@ -91,11 +93,11 @@ public class DeleteAction implements QProfileWsAction {
     response.noContent();
   }
 
-  private List<QProfileDto> selectDescendants(DbSession dbSession, QProfileDto profile) {
-    return dbClient.qualityProfileDao().selectDescendants(dbSession, profile);
+  private Collection<QProfileDto> selectDescendants(DbSession dbSession, QProfileDto profile) {
+    return dbClient.qualityProfileDao().selectDescendants(dbSession, singleton(profile));
   }
 
-  private void ensureNoneIsMarkedAsDefault(DbSession dbSession, QProfileDto profile, List<QProfileDto> descendants) {
+  private void ensureNoneIsMarkedAsDefault(DbSession dbSession, QProfileDto profile, Collection<QProfileDto> descendants) {
     Set<String> allUuids = new HashSet<>();
     allUuids.add(profile.getKee());
     descendants.forEach(p -> allUuids.add(p.getKee()));
@@ -111,7 +113,7 @@ public class DeleteAction implements QProfileWsAction {
       });
   }
 
-  private static List<QProfileDto> merge(QProfileDto profile, List<QProfileDto> descendants) {
+  private static List<QProfileDto> merge(QProfileDto profile, Collection<QProfileDto> descendants) {
     return Stream.concat(Stream.of(profile), descendants.stream())
       .collect(MoreCollectors.toList(descendants.size() + 1));
   }
diff --git a/server/sonar-server/src/main/java/org/sonar/server/qualityprofile/ws/InheritanceAction.java b/server/sonar-server/src/main/java/org/sonar/server/qualityprofile/ws/InheritanceAction.java
index d3645beaf47..84152cef2a5 100644
--- a/server/sonar-server/src/main/java/org/sonar/server/qualityprofile/ws/InheritanceAction.java
+++ b/server/sonar-server/src/main/java/org/sonar/server/qualityprofile/ws/InheritanceAction.java
@@ -37,6 +37,7 @@ import org.sonar.db.qualityprofile.QProfileDto;
 import org.sonarqube.ws.Qualityprofiles.InheritanceWsResponse;
 import org.sonarqube.ws.Qualityprofiles.InheritanceWsResponse.QualityProfile;
 
+import static java.util.Collections.singleton;
 import static org.sonar.core.util.Protobuf.setNullable;
 import static org.sonar.db.qualityprofile.ActiveRuleDto.OVERRIDES;
 import static org.sonar.server.qualityprofile.ws.QProfileWsSupport.createOrganizationParam;
@@ -74,7 +75,7 @@ public class InheritanceAction implements QProfileWsAction {
       QProfileDto profile = wsSupport.getProfile(dbSession, reference);
       OrganizationDto organization = wsSupport.getOrganization(dbSession, profile);
       List<QProfileDto> ancestors = ancestors(profile, dbSession);
-      List<QProfileDto> children = dbClient.qualityProfileDao().selectChildren(dbSession, profile);
+      List<QProfileDto> children = dbClient.qualityProfileDao().selectChildren(dbSession, singleton(profile));
       List<QProfileDto> allProfiles = new ArrayList<>();
       allProfiles.add(profile);
       allProfiles.addAll(ancestors);
@@ -85,7 +86,7 @@ public class InheritanceAction implements QProfileWsAction {
     }
   }
 
-  public List<QProfileDto> ancestors(QProfileDto profile, DbSession dbSession) {
+  private List<QProfileDto> ancestors(QProfileDto profile, DbSession dbSession) {
     List<QProfileDto> ancestors = new ArrayList<>();
     collectAncestors(profile, ancestors, dbSession);
     return ancestors;
diff --git a/server/sonar-server/src/test/java/org/sonar/server/qualityprofile/RegisterQualityProfilesNotificationTest.java b/server/sonar-server/src/test/java/org/sonar/server/qualityprofile/RegisterQualityProfilesNotificationTest.java
index 3bbcaa35ced..c55583f7731 100644
--- a/server/sonar-server/src/test/java/org/sonar/server/qualityprofile/RegisterQualityProfilesNotificationTest.java
+++ b/server/sonar-server/src/test/java/org/sonar/server/qualityprofile/RegisterQualityProfilesNotificationTest.java
@@ -20,6 +20,7 @@
 package org.sonar.server.qualityprofile;
 
 import com.google.common.collect.Multimap;
+import java.security.SecureRandom;
 import java.util.Arrays;
 import java.util.Random;
 import java.util.function.Consumer;
@@ -68,7 +69,7 @@ import static org.sonar.server.qualityprofile.ActiveRuleChange.Type.UPDATED;
 
 public class RegisterQualityProfilesNotificationTest {
 
-  private static final Random RANDOM = new Random();
+  private static final Random RANDOM = new SecureRandom();
 
   private System2 system2 = mock(System2.class);
   @Rule
@@ -227,11 +228,11 @@ public class RegisterQualityProfilesNotificationTest {
     RuleDefinitionDto rule = db.rules().insert(r -> r.setLanguage(language).setSeverity(Severity.MINOR));
     OrganizationDto organization = db.organizations().insert();
 
-    QProfileDto builtInQProfileDto = insertProfile(organization, orgQProfile -> orgQProfile.setIsBuiltIn(true).setLanguage(language));
-    db.qualityProfiles().activateRule(builtInQProfileDto, rule);
-    QProfileDto childQProfileDto = insertProfile(organization, orgQProfile -> orgQProfile.setIsBuiltIn(false).setLanguage(language).setParentKee(builtInQProfileDto.getKee()));
-    qProfileRules.activateAndCommit(db.getSession(), childQProfileDto, singleton(RuleActivation.create(rule.getKey())));
-    addPluginProfile(builtInQProfileDto, rule);
+    QProfileDto builtInProfile = insertProfile(organization, orgQProfile -> orgQProfile.setIsBuiltIn(true).setLanguage(language));
+    db.qualityProfiles().activateRule(builtInProfile, rule);
+    QProfileDto childProfile = insertProfile(organization, orgQProfile -> orgQProfile.setIsBuiltIn(false).setLanguage(language).setParentKee(builtInProfile.getKee()));
+    db.qualityProfiles().activateRule(childProfile, rule, ar -> ar.setInheritance(ActiveRuleDto.INHERITED).setSeverity(Severity.MINOR));
+    addPluginProfile(builtInProfile, rule);
     builtInQProfileRepositoryRule.initialize();
     db.commit();
 
@@ -242,7 +243,7 @@ public class RegisterQualityProfilesNotificationTest {
     Multimap<QProfileName, ActiveRuleChange> updatedProfiles = captor.<Multimap<QProfileName, ActiveRuleChange>>getValue();
     assertThat(updatedProfiles.keySet())
       .extracting(QProfileName::getName, QProfileName::getLanguage)
-      .containsExactlyInAnyOrder(tuple(builtInQProfileDto.getName(), builtInQProfileDto.getLanguage()));
+      .containsExactlyInAnyOrder(tuple(builtInProfile.getName(), builtInProfile.getLanguage()));
     assertThat(updatedProfiles.values())
       .extracting(value -> value.getActiveRule().getRuleId(), ActiveRuleChange::getType)
       .containsExactlyInAnyOrder(tuple(rule.getId(), UPDATED));
-- 
2.39.5