Skip to content

Java: Improve several join-orders #20088

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 3 commits into from
Jul 18, 2025
Merged

Java: Improve several join-orders #20088

merged 3 commits into from
Jul 18, 2025
+24 −9

Conversation

aschackmull
Copy link
Contributor

These were all identified by the join-order badness metric and relate to the mass inclusion of quality queries (see #19799 (comment))

Commit 1: For Generics::hasParameterSubstitution the join after the delta is much improved if we join on both columns at the same time.
Before:

Pipeline standard for Generics::hasParameterSubstitution/6#69ef8058@fa8a3w37 was evaluated in 4 iterations totaling 37ms (delta sizes total: 14069).
          22988  ~2%    {4} r1 = SCAN `Generics::hasSubstitution/4#141198e9#prev_delta` OUTPUT In.1, In.0, In.2, In.3
        3849584  ~0%    {5}    | JOIN WITH `Generics::ParameterizedType.getTypeArgument/1#dispred#1493bd8f_201#join_rhs` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Rhs.2
        3849584  ~0%    {6}    | JOIN WITH `Generics::ParameterizedType.getGenericType/0#dispred#d00cd684` ON FIRST 1 OUTPUT Lhs.0, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Rhs.1
        6164397  ~3%    {7}    | JOIN WITH `Generics::unificationTargets/2#f62be8b8_10#join_rhs` ON FIRST 1 OUTPUT Rhs.1, Lhs.4, Lhs.1, Lhs.2, Lhs.3, Lhs.0, Lhs.5
          14148  ~0%    {5}    | JOIN WITH `Generics::ParameterizedType.getTypeArgument/1#dispred#1493bd8f` ON FIRST 3 OUTPUT Lhs.0, Lhs.3, Lhs.4, Lhs.5, Lhs.6
          14093  ~4%    {6}    | JOIN WITH `Generics::ParameterizedType.getGenericType/0#dispred#d00cd684` ON FIRST 1 OUTPUT Rhs.1, Lhs.0, Lhs.4, Lhs.3, Lhs.1, Lhs.2
          14069  ~4%    {6}    | AND NOT `Generics::hasParameterSubstitution/6#69ef8058#prev`(FIRST 6)
                        return r1

After:

Pipeline standard for Generics::hasParameterSubstitution/6#69ef8058@942b1w00 was evaluated in 4 iterations totaling 1ms (delta sizes total: 14068).
        14101  ~0%    {4} r1 = JOIN `Generics::hasSubstitution/4#141198e9#prev_delta` WITH `project#Generics::unificationTargetsParameterized/5#fbd9d89b_2301#join_rhs` ON FIRST 2 OUTPUT Rhs.2, Lhs.2, Lhs.3, Rhs.3
        14092  ~6%    {5}    | JOIN WITH `Generics::ParameterizedType.getGenericType/0#dispred#d00cd684` ON FIRST 1 OUTPUT Lhs.3, Lhs.1, Lhs.2, Lhs.0, Rhs.1
        14092  ~4%    {6}    | JOIN WITH `Generics::ParameterizedType.getGenericType/0#dispred#d00cd684` ON FIRST 1 OUTPUT Lhs.4, Lhs.3, Rhs.1, Lhs.0, Lhs.1, Lhs.2
        14068  ~4%    {6}    | AND NOT `Generics::hasParameterSubstitution/6#69ef8058#prev`(FIRST 6)
                      return r1

Commit 2: getSourceDeclaration and the TC of getASourceSuperType commute, and switching them yields a much better join order in these two cases.
Before:

[2025-07-18 10:53:27] Evaluated non-recursive predicate ContainsTypeMismatch::MismatchedContainerAccess#ac8b7648@88b9e2nn in 34ms (size: 1350).
Evaluated relational algebra for predicate ContainsTypeMismatch::MismatchedContainerAccess#ac8b7648@88b9e2nn with tuple counts:
           3699   ~3%    {6} r1 = JOIN `_#Expr::Call.getCallee/0#dispred#3c1718adMerge_#Expr::Call.getCallee/0#dispred#3c1718adMerge_10#join__#shared` WITH `Expr::Call.getCallee/0#dispred#3c1718ad` ON FIRST 1 OUTPUT Lhs.4, Lhs.1, Lhs.2, Lhs.3, Lhs.0, Rhs.1
           3699   ~0%    {6}    | JOIN WITH `Member::Member.getDeclaringType/0#dispred#6084de84` ON FIRST 1 OUTPUT Lhs.5, Lhs.3, Lhs.1, Lhs.2, Lhs.4, Rhs.1
           3699   ~2%    {5}    | JOIN WITH `Member::Callable.getParameter/1#dispred#58097e89` ON FIRST 2 OUTPUT Rhs.2, Lhs.2, Lhs.3, Lhs.4, Lhs.5
           3699   ~6%    {5}    | JOIN WITH `Variable::Parameter.getType/0#dispred#bfa3c0f9` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4
           3486   ~1%    {4}    | JOIN WITH JDK::TypeObject#5026c17b ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.3, Lhs.4
                     
           3486   ~3%    {3} r2 = JOIN r1 WITH `#Type::RefType.hasQualifiedName/2#dispred#459e386fMerge_120#join_rhs` ON FIRST 2 OUTPUT Lhs.3, Rhs.2, Lhs.2
            730   ~0%    {1}    | JOIN WITH `Type::RefType.getSourceDeclaration/0#dispred#770ab75c` ON FIRST 2 OUTPUT Lhs.2
                     
           3486   ~0%    {3} r3 = JOIN r1 WITH `#Type::RefType.hasQualifiedName/2#dispred#459e386fMerge_120#join_rhs` ON FIRST 2 OUTPUT Rhs.2, Lhs.2, Lhs.3
        6544767   ~0%    {3}    | JOIN WITH `#Type::RefType.getSourceDeclaration/0#dispred#770ab75cMerge_10#join_rhs` ON FIRST 1 OUTPUT Lhs.2, Rhs.1, Lhs.1
           1348   ~0%    {1}    | JOIN WITH `doublyBoundedFastTC:#Type::RefType.getASourceSupertype/0#dispred#418e5974Merge:_##Type::RefType.getASourceSupertype/0#dispred#418e5974MergePlus#bf#sourceBound#2#2#3#2#3#2#3_##Type__#higher_order_body:##Type::RefType.getASourceSupertype/0#dispred#418e5974MergePlus#bf#sinkBound#3` ON FIRST 2 OUTPUT Lhs.2
                     
           2078  ~52%    {1} r4 = r2 UNION r3
                         return r4

After:

[2025-07-18 10:58:28] Evaluated non-recursive predicate ContainsTypeMismatch::MismatchedContainerAccess#ac8b7648@79993c9t in 0ms (size: 1350).
Evaluated relational algebra for predicate ContainsTypeMismatch::MismatchedContainerAccess#ac8b7648@79993c9t with tuple counts:
        3699   ~3%    {6} r1 = JOIN `_#Expr::Call.getCallee/0#dispred#3c1718adMerge_#Expr::Call.getCallee/0#dispred#3c1718adMerge_10#join__#shared` WITH `Expr::Call.getCallee/0#dispred#3c1718ad` ON FIRST 1 OUTPUT Lhs.4, Lhs.1, Lhs.2, Lhs.3, Lhs.0, Rhs.1
        3699   ~0%    {6}    | JOIN WITH `Member::Member.getDeclaringType/0#dispred#6084de84` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5
        3699   ~0%    {6}    | JOIN WITH `Type::RefType.getSourceDeclaration/0#dispred#770ab75c` ON FIRST 1 OUTPUT Lhs.5, Lhs.3, Lhs.1, Lhs.2, Lhs.4, Rhs.1
        3699   ~4%    {5}    | JOIN WITH `Member::Callable.getParameter/1#dispred#58097e89` ON FIRST 2 OUTPUT Rhs.2, Lhs.2, Lhs.3, Lhs.4, Lhs.5
        3699   ~1%    {5}    | JOIN WITH `Variable::Parameter.getType/0#dispred#bfa3c0f9` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4
                  
        3486   ~0%    {4} r2 = JOIN r1 WITH JDK::TypeObject#5026c17b ON FIRST 1 OUTPUT Lhs.4, Lhs.1, Lhs.2, Lhs.3
         730   ~0%    {1}    | JOIN WITH `Type::RefType.hasQualifiedName/2#dispred#459e386f` ON FIRST 3 OUTPUT Lhs.3
                  
        3486   ~5%    {4} r3 = JOIN r1 WITH JDK::TypeObject#5026c17b ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.3, Lhs.4
        3486   ~0%    {3}    | JOIN WITH `#Type::RefType.hasQualifiedName/2#dispred#459e386fMerge_120#join_rhs` ON FIRST 2 OUTPUT Lhs.3, Rhs.2, Lhs.2
         620   ~0%    {1}    | JOIN WITH `doublyBoundedFastTC:#Type::RefType.getASourceSupertype/0#dispred#418e5974Merge:_##Type::RefType.getASourceSupertype/0#dispred#418e5974MergePlus#bf#sinkBound#4#2#3#2#2#3#2#2#3_##Ty__#higher_order_body:##Type::RefType.getASourceSupertype/0#dispred#418e5974MergePlus#bf#sinkBound#3` ON FIRST 2 OUTPUT Lhs.2
                  
        1350   ~0%    {1} r4 = r2 UNION r3
                      return r4

Before:

[2025-07-18 10:58:29] Evaluated non-recursive predicate ContainsTypeMismatch::MismatchedContainerAccess.getReceiverElementType/1#dispred#217c793b@ea461e9b in 28ms (size: 1350).
Evaluated relational algebra for predicate ContainsTypeMismatch::MismatchedContainerAccess.getReceiverElementType/1#dispred#217c793b@ea461e9b with tuple counts:
             13   ~0%    {5} r1 = CONSTANT(string, string, string, int, int)["contains(java.lang.Object)","java.util","Collection",0,0;...]
          20968   ~0%    {5}    | JOIN WITH `#Member::Callable.getSignature/0#dispred#6167942cMerge_10#join_rhs` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4
           3699   ~0%    {5}    | JOIN WITH `#Expr::Call.getCallee/0#dispred#3c1718adMerge_10#join_rhs` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4
           2765   ~0%    {5}    | JOIN WITH ContainsTypeMismatch::MismatchedContainerAccess#ac8b7648 ON FIRST 1 OUTPUT Lhs.0, Lhs.1, Lhs.2, Lhs.3, Lhs.4
           2765   ~0%    {6}    | JOIN WITH `Expr::Call.getCallee/0#dispred#3c1718ad` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.0
           2765   ~1%    {6}    | JOIN WITH `Member::Member.getDeclaringType/0#dispred#6084de84` ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Rhs.1
                     
           2765   ~0%    {5} r2 = JOIN r1 WITH `#Type::RefType.hasQualifiedName/2#dispred#459e386fMerge_120#join_rhs` ON FIRST 2 OUTPUT Lhs.5, Rhs.2, Lhs.2, Lhs.3, Lhs.4
            730   ~0%    {5}    | JOIN WITH `Type::RefType.getSourceDeclaration/0#dispred#770ab75c` ON FIRST 2 OUTPUT Lhs.0, Lhs.1, Lhs.2, Lhs.3, Lhs.4
                     
           2765   ~0%    {5} r3 = JOIN r1 WITH `#Type::RefType.hasQualifiedName/2#dispred#459e386fMerge_120#join_rhs` ON FIRST 2 OUTPUT Rhs.2, Lhs.2, Lhs.3, Lhs.4, Lhs.5
        5073554   ~1%    {6}    | JOIN WITH `#Type::RefType.getSourceDeclaration/0#dispred#770ab75cMerge_10#join_rhs` ON FIRST 1 OUTPUT Lhs.4, Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.0
           1348   ~0%    {5}    | JOIN WITH `doublyBoundedFastTC:#Type::RefType.getASourceSupertype/0#dispred#418e5974Merge:_##Type::RefType.getASourceSupertype/0#dispred#418e5974MergePlus#bf#sourceBound#4#2#2#3#2#2#2#4_##Ty__#higher_order_body:##Type::RefType.getASourceSupertype/0#dispred#418e5974MergePlus#bf#sinkBound#4#3` ON FIRST 2 OUTPUT Lhs.0, Lhs.5, Lhs.2, Lhs.3, Lhs.4
                     
           2078  ~54%    {5} r4 = r2 UNION r3
           2078  ~52%    {3}    | JOIN WITH `Collections::indirectlyInstantiates/4#e3fb5c16` ON FIRST 3 OUTPUT Lhs.4, Lhs.3, Rhs.3
                         return r4

After:

[2025-07-18 11:03:59] Evaluated non-recursive predicate ContainsTypeMismatch::MismatchedContainerAccess.getReceiverElementType/1#dispred#217c793b@f927a29q in 2ms (size: 1350).
Evaluated relational algebra for predicate ContainsTypeMismatch::MismatchedContainerAccess.getReceiverElementType/1#dispred#217c793b@f927a29q with tuple counts:
           13   ~0%    {5} r1 = CONSTANT(string, string, string, int, int)["contains(java.lang.Object)","java.util","Collection",0,0;...]
        20968   ~0%    {5}    | JOIN WITH `#Member::Callable.getSignature/0#dispred#6167942cMerge_10#join_rhs` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4
         3699   ~0%    {5}    | JOIN WITH `#Expr::Call.getCallee/0#dispred#3c1718adMerge_10#join_rhs` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4
         2765   ~0%    {5}    | JOIN WITH ContainsTypeMismatch::MismatchedContainerAccess#ac8b7648 ON FIRST 1 OUTPUT Lhs.0, Lhs.1, Lhs.2, Lhs.3, Lhs.4
         2765   ~0%    {6}    | JOIN WITH `Expr::Call.getCallee/0#dispred#3c1718ad` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.0
         2765   ~0%    {6}    | JOIN WITH `Member::Member.getDeclaringType/0#dispred#6084de84` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5
                   
         2765   ~0%    {7} r2 = JOIN r1 WITH `Type::RefType.getSourceDeclaration/0#dispred#770ab75c` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.0
          730   ~0%    {5}    | JOIN WITH `Type::RefType.hasQualifiedName/2#dispred#459e386f` ON FIRST 3 OUTPUT Lhs.6, Lhs.0, Lhs.3, Lhs.4, Lhs.5
                   
         2765   ~0%    {7} r3 = JOIN r1 WITH `Type::RefType.getSourceDeclaration/0#dispred#770ab75c` ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.0, Rhs.1
         2765   ~0%    {6}    | JOIN WITH `#Type::RefType.hasQualifiedName/2#dispred#459e386fMerge_120#join_rhs` ON FIRST 2 OUTPUT Lhs.6, Rhs.2, Lhs.2, Lhs.3, Lhs.4, Lhs.5
          620   ~0%    {5}    | JOIN WITH `doublyBoundedFastTC:#Type::RefType.getASourceSupertype/0#dispred#418e5974Merge:_##Type::RefType.getASourceSupertype/0#dispred#418e5974MergePlus#bf#sinkBound#4#3#2#2#3#2#2#3_##Type__#higher_order_body#1:##Type::RefType.getASourceSupertype/0#dispred#418e5974MergePlus#bf#sinkBound#4#6` ON FIRST 2 OUTPUT Lhs.5, Lhs.1, Lhs.2, Lhs.3, Lhs.4
                   
         1350   ~0%    {5} r4 = r2 UNION r3
         1350   ~0%    {3}    | JOIN WITH `Collections::indirectlyInstantiates/4#e3fb5c16` ON FIRST 3 OUTPUT Lhs.4, Lhs.3, Rhs.3
                       return r4

Commit 3: The inlined haveIntersection really needs both arguments bound in order to perform properly - hence why it's inlined. With a bindingset and inline_late we can actually ensure this.
Before:

[2025-07-18 11:07:43] Evaluated non-recursive predicate ConfusingOverloading::potentiallyConfusingTypesRefTypes/2#df374734#bb@e60feekv in 12ms (size: 319).
Evaluated relational algebra for predicate ConfusingOverloading::potentiallyConfusingTypesRefTypes/2#df374734#bb@e60feekv with tuple counts:
          24440  ~0%    {1} r1 = JOIN `project##Variable::Parameter.getType/0#dispred#bfa3c0f9Merge` WITH Type::RefType#d8df7f7d ON FIRST 1 OUTPUT Lhs.0
            830  ~0%    {2}    | JOIN WITH `ConfusingOverloading::paramTypePair/2#9f9a834c_10#join_rhs` ON FIRST 1 OUTPUT Rhs.1, Lhs.0
            790  ~0%    {2}    | JOIN WITH Type::RefType#d8df7f7d ON FIRST 1 OUTPUT Lhs.0, Lhs.1
            752  ~0%    {2}    | AND NOT `ConfusingOverloading::potentiallyConfusingTypesSimple/2#9c414149`(FIRST 2)
            752  ~0%    {2}    | JOIN WITH `project##Variable::Parameter.getType/0#dispred#bfa3c0f9Merge` ON FIRST 1 OUTPUT Lhs.0, Lhs.1
            752  ~0%    {3}    | JOIN WITH `cached_Type::erase/1#afa87d84` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.0
        1863914  ~0%    {3}    | JOIN WITH `Type::erasedHaveIntersection/2#a066b803` ON FIRST 1 OUTPUT Lhs.1, Rhs.1, Lhs.2
            319  ~0%    {2}    | JOIN WITH `cached_Type::erase/1#afa87d84` ON FIRST 2 OUTPUT Lhs.2, Lhs.0
                        return r1

After (now inlined into potentiallyConfusingTypes):

[2025-07-18 11:14:37] Evaluated non-recursive predicate ConfusingOverloading::potentiallyConfusingTypes/2#2ca3f84a#bb@fb4163j4 in 1ms (size: 109).
Evaluated relational algebra for predicate ConfusingOverloading::potentiallyConfusingTypes/2#2ca3f84a#bb@fb4163j4 with tuple counts:
           43     ~0%    {2} r1 = SCAN `ConfusingOverloading::potentiallyConfusingTypesSimple/2#9c414149` OUTPUT In.1, In.0
           43     ~0%    {2}    | JOIN WITH `project##Variable::Parameter.getType/0#dispred#bfa3c0f9Merge` ON FIRST 1 OUTPUT Lhs.1, Lhs.0
           43     ~0%    {2}    | JOIN WITH `project##Variable::Parameter.getType/0#dispred#bfa3c0f9Merge` ON FIRST 1 OUTPUT Lhs.0, Lhs.1
                     
                         {2} r2 = REWRITE `ConfusingOverloading::paramTypePair/2#9f9a834c` WITH TEST InOut.0 = InOut.1
           39     ~1%    {1}    | SCAN OUTPUT In.0
           39     ~1%    {1}    | STREAM DEDUP
           39     ~1%    {1}    | JOIN WITH `project##Variable::Parameter.getType/0#dispred#bfa3c0f9Merge` ON FIRST 1 OUTPUT Lhs.0
           34     ~0%    {1}    | JOIN WITH Type::RefType#d8df7f7d ON FIRST 1 OUTPUT Lhs.0
           34     ~1%    {2}    | JOIN WITH `cached_Type::erase/1#afa87d84` ON FIRST 1 OUTPUT Lhs.0, Rhs.1
           34     ~1%    {3}    | JOIN WITH `cached_Type::erase/1#afa87d84` ON FIRST 1 OUTPUT Lhs.1, Rhs.1, Lhs.0
           34     ~1%    {2}    | JOIN WITH `Type::erasedHaveIntersection/2#a066b803` ON FIRST 2 OUTPUT Lhs.2, Lhs.2
                         {2}    | AND NOT `ConfusingOverloading::potentiallyConfusingTypesSimple/2#9c414149`(FIRST 2)
            0     ~0%    {2}    | SCAN OUTPUT In.0, In.0
                     
          869     ~0%    {2} r3 = SCAN `ConfusingOverloading::paramTypePair/2#9f9a834c` OUTPUT In.1, In.0
          869     ~0%    {2}    | JOIN WITH `project##Variable::Parameter.getType/0#dispred#bfa3c0f9Merge` ON FIRST 1 OUTPUT Lhs.1, Lhs.0
          805     ~0%    {2}    | JOIN WITH Type::RefType#d8df7f7d ON FIRST 1 OUTPUT Lhs.1, Lhs.0
          790     ~0%    {2}    | JOIN WITH Type::RefType#d8df7f7d ON FIRST 1 OUTPUT Lhs.1, Lhs.0
          790     ~0%    {3}    | JOIN WITH `cached_Type::erase/1#afa87d84` ON FIRST 1 OUTPUT Lhs.1, Lhs.0, Rhs.1
          790     ~0%    {4}    | JOIN WITH `cached_Type::erase/1#afa87d84` ON FIRST 1 OUTPUT Lhs.2, Rhs.1, Lhs.0, Lhs.1
                     
          357     ~0%    {2} r4 = JOIN r3 WITH `Type::erasedHaveIntersection/2#a066b803` ON FIRST 2 OUTPUT Lhs.2, Lhs.3
           46     ~2%    {2}    | JOIN WITH `#ConfusingOverloading::hasSubtypeOrInstantiation/2#6e757869Plus#bf` ON FIRST 2 OUTPUT Lhs.1, Lhs.0
           12     ~0%    {2}    | AND NOT `ConfusingOverloading::potentiallyConfusingTypesSimple/2#9c414149`(FIRST 2)
           12     ~0%    {2}    | JOIN WITH `project##Variable::Parameter.getType/0#dispred#bfa3c0f9Merge` ON FIRST 1 OUTPUT Lhs.0, Lhs.1
                     
          357     ~0%    {2} r5 = JOIN r3 WITH `Type::erasedHaveIntersection/2#a066b803` ON FIRST 2 OUTPUT Lhs.3, Lhs.2
                     
           46     ~0%    {2} r6 = JOIN r5 WITH `#ConfusingOverloading::hasSubtypeOrInstantiation/2#6e757869Plus#bf` ON FIRST 2 OUTPUT Lhs.0, Lhs.1
           12     ~0%    {2}    | AND NOT `ConfusingOverloading::potentiallyConfusingTypesSimple/2#9c414149`(FIRST 2)
           12     ~0%    {2}    | JOIN WITH `project##Variable::Parameter.getType/0#dispred#bfa3c0f9Merge` ON FIRST 1 OUTPUT Lhs.0, Lhs.1
                     
          319     ~0%    {2} r7 = r5 AND NOT `ConfusingOverloading::potentiallyConfusingTypesSimple/2#9c414149`(FIRST 2)
          319     ~0%    {2}    | JOIN WITH `project##Variable::Parameter.getType/0#dispred#bfa3c0f9Merge` ON FIRST 1 OUTPUT Lhs.0, Lhs.1
        74981     ~7%    {3}    | JOIN WITH `#ConfusingOverloading::hasSubtypeOrInstantiation/2#6e757869Plus#bf` ON FIRST 1 OUTPUT Lhs.1, Rhs.1, Lhs.0
         1622  ~2354%    {2}    | JOIN WITH `#ConfusingOverloading::hasSubtypeOrInstantiation/2#6e757869Plus#bf` ON FIRST 2 OUTPUT Lhs.2, Lhs.0
                     
         1689  ~1440%    {2} r8 = r1 UNION r2 UNION r4 UNION r6 UNION r7
                         return r8

@Copilot Copilot AI review requested due to automatic review settings July 18, 2025 09:56
@aschackmull aschackmull added the no-change-note-required This PR does not need a change note label Jul 18, 2025
@aschackmull aschackmull requested a review from a team as a code owner July 18, 2025 09:56
@github-actions github-actions bot added the Java label Jul 18, 2025
Copilot
Copilot AI reviewed Jul 18, 2025
View reviewed changes
Copy link
Contributor

@Copilot Copilot AI left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Pull Request Overview

This pull request optimizes join-order performance in Java CodeQL queries by refactoring several predicates to improve query execution efficiency. The changes were identified through join-order badness metrics and focus on reducing intermediate result set sizes during query evaluation.

Key changes include:

  • Restructuring generic type parameter substitution logic to join on multiple columns simultaneously
  • Reordering type declaration and supertype traversal operations for better join selectivity
  • Adding binding constraints and inline pragmas to ensure proper predicate evaluation order

Reviewed Changes

Copilot reviewed 3 out of 3 changed files in this pull request and generated no comments.

File Description
java/ql/src/Likely Bugs/Collections/ContainsTypeMismatch.ql Reorders getSourceDeclaration() and getASourceSupertype*() calls to improve join performance
java/ql/lib/semmle/code/java/Type.qll Adds binding constraints and inline_late pragmas to haveIntersection predicate with helper predicate
java/ql/lib/semmle/code/java/Generics.qll Extracts unificationTargetsParameterized predicate and refactors hasParameterSubstitution to join on multiple columns
Comments suppressed due to low confidence (1)

java/ql/lib/semmle/code/java/Type.qll:1275

  • [nitpick] The predicate name 'erasedHaveIntersectionFilter' is unclear about its purpose. Consider renaming to 'erasedHaveIntersectionBound' or 'erasedHaveIntersectionConstrained' to better reflect that it's a binding-constrained wrapper around erasedHaveIntersection.
private predicate erasedHaveIntersectionFilter(RefType t1, RefType t2) {

michaelnebel
michaelnebel approved these changes Jul 18, 2025
View reviewed changes
Copy link
Contributor

@michaelnebel michaelnebel left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks plausible to me!

owen-mc
owen-mc approved these changes Jul 18, 2025 •
edited
Loading
View reviewed changes
@aschackmull
Copy link
Contributor Author

Dca looks good.

@aschackmull aschackmull merged commit d64a936 into github:main Jul 18, 2025
19 checks passed
@aschackmull aschackmull deleted the java/joinorders1 branch July 18, 2025 12:54
@aschackmull aschackmull mentioned this pull request Jul 18, 2025
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

Copilot code review Copilot Copilot left review comments

@michaelnebel michaelnebel michaelnebel approved these changes

@owen-mc owen-mc owen-mc approved these changes

Assignees
No one assigned
Labels
Java no-change-note-required This PR does not need a change note
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@aschackmull @michaelnebel @owen-mc