0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@krile136

Apexの動的なリレーションシップ解決における二分探索と線形スキャンの比較

0
Last updated at Posted at 2026-02-20

対象読者

  • SObjectのリフレクションに興味がある人(上級Platform developerの中でも一部？)
  • 二分探索の効果を実感したい人

動的なリレーションシップ解決について

私の作っているOSS「ApexEloquent」では、子リレーションを作る際に、いちいち__rがついたリレーション名を調べたり複数形を考えなくて済むように「子供のオブジェクトのクラス」でリレーションを作成できるようになっています。

// 執筆時点ではv1ですがv2では次のように書けるようになります
Scribe scribe = Scribe.of(Account.class)
    .field('Name')
    .withChildren(
        Scribe.asChild(Contact.class)
            .fields(new List<String>{'Id', 'Email'})
            .whereNotNull('Email')
    );
 
// Generates: SELECT name, (SELECT id, email FROM Contacts WHERE Email != NULL) FROM Account

子リレーションをContact.classで指定しているのに、SOQLではちゃんとContactsに変換されています。これが動的なリレーションシップ解決です。

簡単な内部の仕組み

リレーション名はユーザーが自由につけられるので、リフレクションで特定する方法しかありません。
そのため、

  1. 子となるSObjectのクラスから、子オブジェクト名を生成
  2. 親のSObjectのリレーション情報を取得(getChildRelationShips()メソッド)
  3. リレーション情報を巡回、子オブジェクトの名前を取得し、子オブジェクトの名前と一致するかチェック
  4. 名前が一致したら、リレーション情報からリレーション名を取得

というような処理をしています。

getChildRelationShipsとは？

公式リンク
特定の親の子リレーションの情報を取得するものです。
例えば、次のコードを使用すると「Accountを親にもつ子オブジェクトの一覧」を取得できます。

Schema.SObjectType sObjectType = Account.getSObjectType();
List<Schema.ChildRelationship> childRelationships = sObjectType.getDescribe().getChildRelationships();
List<String> childObjectNames = new List<String>();
for (Schema.ChildRelationship cr : childRelationships) {
  String childObjectName = cr.getChildSObject().getDescribe().getName();
  childObjectNames.add(childObjectName);
}

そして、Schema.ChildRelationship型からは、そのリレーション名を取得できます。
あの__rが後ろについたりする調べるのがめんどくさいやつです。

子リレーション情報の並び方について

上のコードで子供のオブジェクト名を出力すると、ある法則性があります。
それはUnicodeの数値順大文字(A-Z が 小文字 a-z より先)という法則です。これは公式リファレンスにも載っていません。
そしてこのUnicodeによる文字列の比較はString型のcompareToにより可能です。

動的リレーションシップ解決の問題点

検索したい子のオブジェクト名を比較するために子のオブジェクト名を

String childObjectName = cr.getChildSObject().getDescribe().getName();

としていますが、途中のgetDescribe()がかなり重い処理なのです。
簡単にいうとそのオブジェクトのメタデータを取得するため重いようです。
そのため、現在の動的リレーションシップの解決方法である「順番に見ていく」方法だと、データベースでいうところのフルスキャンになってしまい効率が悪くせっかくの高速実行が台無しになってしまいます。

問題の解決方法

さて、ここまで上に並べた情報

  • 子リレーションのgetDesctibeが重い
  • 子リレーション情報の並び方はUnicode順になっている
  • Unicodeの比較はcompareToで可能

ここから、次の方法を取ることでこの問題解決ができそうです。
「あるオブジェクトの子リレーションの名前を二分探索法で見つける」。

比較してみる

次のような条件で試験をして、本当に二分探索が有効なのかを検証してみましょう。

  • あるオブジェクトの全ての子リレーション名からランダムに1000個（重複あり）を選ぶ
  • 選んだ1000個をもとに次の３つの条件で試験を行う
    • 頭から順にマッチするか調べる(フルスキャン)
    • 検索する名前の先頭がA~Mなら頭から調べ、それ以外なら後ろから調べる(双方向スキャン)
    • 二分探索法

比較するためのプログラム

// 親オブジェクトを指定
Schema.SObjectType sObjectType = Opportunity.getSObjectType();

System.debug('test SOject: ' + sObjectType.getDescribe().getName());
List<Schema.ChildRelationship> childRelationships = sObjectType.getDescribe().getChildRelationships();
List<String> childObjectNames = new List<String>();
for (Schema.ChildRelationship cr : childRelationships) {
  String childObjectName = cr.getChildSObject().getDescribe().getName();
  childObjectNames.add(childObjectName);
}

Integer trialCount = 1000;
Integer listSize = childObjectNames.size();
System.debug('Total Child Objects: ' + listSize);

// 1000回分のランダムなターゲットを準備
List<String> targetNames = new List<String>();
for (Integer i = 0; i < trialCount; i++) {
  Integer randomIndex = Math.mod(Math.abs(Crypto.getRandomInteger()), listSize);
  targetNames.add(childObjectNames[randomIndex]);
}

// --- 1. フルスキャンの計測 ---
Long countFullScan = 0;
for (String target : targetNames) {
  for (Integer i = 0; i < listSize; i++) {
    countFullScan++; // getDescribe()を呼んだと仮定
    if (childObjectNames[i] == target)
      break;
  }
}

// --- 2. 双方向スキャン（A-Mは前から、N-Zは後ろから） ---
Long countBiDirectional = 0;
for (String target : targetNames) {
  String firstChar = target.substring(0, 1).toUpperCase();
  if (firstChar <= 'M') {
    // 前から
    for (Integer i = 0; i < listSize; i++) {
      countBiDirectional++;
      if (childObjectNames[i] == target)
        break;
    }
  } else {
    // 後ろから
    for (Integer i = listSize - 1; i >= 0; i--) {
      countBiDirectional++;
      if (childObjectNames[i] == target)
        break;
    }
  }
}

// --- 3. 二分探索 ---
Long countBinarySearch = 0;
for (String target : targetNames) {
  Integer low = 0;
  Integer high = listSize - 1;
  while (low <= high) {
    countBinarySearch++; // 中央値のgetDescribe()
    Integer mid = (low + high) / 2;
    Integer res = target.compareTo(childObjectNames[mid]);
    if (res == 0)
      break;
    if (res > 0)
      low = mid + 1;
    else
      high = mid - 1;
  }
}

System.debug('--- 1000回試行時の getDescribe() 推定呼び出し回数 ---');
System.debug('1. フルスキャン: ' + countFullScan);
System.debug('2. 双方向スキャン: ' + countBiDirectional);
System.debug('3. 二分探索: ' + countBinarySearch);
System.debug('----------------------------------------------');
System.debug(
  '二分探索はフルスキャンの約 ' + (Double.valueOf(countFullScan) / countBinarySearch).format() + ' 倍速い'
);

代表的なオブジェクトの結果

User

test SOject: User
Total Child Objects: 2274
--- 1000回試行時の getDescribe() 推定呼び出し回数 ---

  1. フルスキャン: 1172845
  2. 双方向スキャン: 673868
  3. 二分探索: 8931

二分探索はフルスキャンの約 131.323 倍速い

Account

test SOject: Account
Total Child Objects: 157
--- 1000回試行時の getDescribe() 推定呼び出し回数 ---

  1. フルスキャン: 78221
  2. 双方向スキャン: 42932
  3. 二分探索: 6006

二分探索はフルスキャンの約 13.024 倍速い

Opportunity

test SOject: Opportunity
Total Child Objects: 112
--- 1000回試行時の getDescribe() 推定呼び出し回数 ---

  1. フルスキャン: 55900
  2. 双方向スキャン: 30836
  3. 二分探索: 5413

二分探索はフルスキャンの約 10.327 倍速い

Product2

test SOject: Product2
Total Child Objects: 67
--- 1000回試行時の getDescribe() 推定呼び出し回数 ---

  1. フルスキャン: 33168
  2. 双方向スキャン: 17099
  3. 二分探索: 5172

二分探索はフルスキャンの約 6.413 倍速い

グラフによる比較

スキャン方法によるgetDescribe呼出回数.png
フルスキャンと双方向スキャンは子リレーション数が増えるにつれ、右肩上がりにgetDescribeの呼出回数が増えているのがわかります。一方、二分探索法の場合ほぼ変わらないということからプロジェクトがどんどん大きくなってもこの二分探索法であれば動的リレーションシップ解決にかかる時間を抑えられるということがわかりました。

また、子リレーション数が少ない場合でも二分探索はフルスキャンよりも数倍速度が高いということもわかりました。

計算量の検証

フルスキャンの計算量

  • 計算量(最悪):
O(n)
  • 予測される数値:
平均してリストの真ん中で見つかると仮定すると \frac{n}{2}​ 回
  • 1000回試行の予測式:
1000×\frac{n}{2}​=500n

検証

  • Account (n=157): 予測 157×500=78,500 → 実測 78,221（誤差ほぼなし！）
  • User (n=2274): 予測 2274×500=1,137,000 → 実測 1,172,845（予測通り!）

双方向スキャンの計算量

  • 計算量 (最悪):
O(n)

(結局、半分になっても定数倍の差なのでオーダーは変わりません）

  • 予測される数値（1回あたり）:
    もし文字の分布が「A-M」と「N-Z」で完全に 50:50 で、かつそれぞれの区間内でも均等に分布しているなら、探索距離は最大でも $n/2$ になります。その場合の平均は
\frac{n}{4} 回
  • 1000回試行の予測式:
1000×\frac{n}{4}=250n

検証

  • User (n=2274): 予測 250×2274=568,500 → 実測 673,868

考察: 予測より少し多いですが、これはSalesforceのオブジェクト名が「A-M」に偏っている（あるいはその逆）ため、片方のグループのリストが長くなり、探索回数が増えたと考えられます。
実際、このテストをした組織には連携アプリの兼ね合いでKから始まるカスタムオブジェクトが大量に入っています。そのため、A-M側に偏ったと考えられます。

二分探索

  • 計算量 (最悪):
O(log_2 n)
  • 1000回試行の予測式:
1000×log_2 n

検証

  • User (n=2274):
1000×log_2 ​2274≈11150

実測は 8,931回 でした。これは「最悪のケース（最後まで見つからない）」ではなく、途中のステップでヒットするケースも多いため、さらに少なくなったと考えられます。

結論

フルスキャンが計算量的にも一番遅いことはわかっていました。双方向スキャンもちょっと面白いと思いましたが、やはり理論的にも実測値としても二分探索が最適ということがわかりました。ApexEloquentのv2ではこの方法で動的リレーションシップの解決を行いたいと思います。

データベースの知識との繋がり

検証した二分探索法は、実はデータベースでのインデックスによる検索の仕組みと同じです。
そして、Salesforceが子リレーションの情報を「子リレーションの名前」でこっそりソートして返ってくると仕組みを逆手に取り、メモリ上のリストに対して手動でインデックス検索をする手法の検証をしたのです。だから早くなってある意味当然なのです。

SalesforceではId、Name、そして外部キーには自動的にインデックスが振られるようになっています。このインデックスを使わない検索は、今回検証した「フルスキャン」をするのと同じ意味です。みなさん、気をつけてSOQLを組み立てましょうね！

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?