You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@shardingsphere.apache.org by zh...@apache.org on 2026/04/02 08:03:11 UTC

(shardingsphere) branch master updated: Introduce selectable full-matrix algorithms for E2E SQL and add pairwise Stage 2 optimization (#38583)

This is an automated email from the ASF dual-hosted git repository.

zhonghongsheng pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/shardingsphere.git


The following commit(s) were added to refs/heads/master by this push:
     new e85af9bd631 Introduce selectable full-matrix algorithms for E2E SQL and add pairwise Stage 2 optimization (#38583)
e85af9bd631 is described below

commit e85af9bd6313f0dd87b204cdb485af56be45a131
Author: Hongsheng Zhong <zh...@apache.org>
AuthorDate: Thu Apr 2 16:03:03 2026 +0800

    Introduce selectable full-matrix algorithms for E2E SQL and add pairwise Stage 2 optimization (#38583)
    
    * workflows: add selectable full-matrix algorithms for e2e-sql
    
    * workflows: extend e2e-sql matrix script tests for algorithm modes
    
    * workflows: speed up e2e-sql pairwise matrix generation in bash
    
    * workflows: initialize pairwise arrays to avoid unbound variable on runner
    
    * workflows: document pairwise matrix algorithm implementation details
    
    * workflows: output full-matrix-algorithm on no-relevant-change early exit
    
    * workflows: expose full-smoke overlap and estimated stage2 jobs
    
    * workflows: report two-stage total jobs and effective reduction ratio
    
    * workflows: extend e2e sql matrix breakdown tests
---
 .github/workflows/e2e-sql.yml                      |  21 ++
 .../scripts/e2e-sql/generate-e2e-sql-matrix.sh     | 286 ++++++++++++++++++---
 .../e2e-sql/test-generate-e2e-sql-matrix.sh        | 180 ++++++++-----
 3 files changed, 396 insertions(+), 91 deletions(-)

diff --git a/.github/workflows/e2e-sql.yml b/.github/workflows/e2e-sql.yml
index 51d64e6ca92..d7441e2b3df 100644
--- a/.github/workflows/e2e-sql.yml
+++ b/.github/workflows/e2e-sql.yml
@@ -23,6 +23,16 @@ on:
     paths-ignore:
       - '**/*.md'
   workflow_dispatch:
+    inputs:
+      full_matrix_algorithm:
+        description: Full matrix generation algorithm
+        required: false
+        default: auto
+        type: choice
+        options:
+          - auto
+          - cartesian
+          - pairwise
 
 concurrency:
   group: e2e-${{ github.workflow }}-${{ github.ref }}
@@ -50,6 +60,11 @@ jobs:
       matrix: ${{ steps.generate-matrix.outputs.matrix }}
       has-jobs: ${{ steps.generate-matrix.outputs.has-jobs }}
       need-proxy-image: ${{ steps.generate-matrix.outputs.need-proxy-image }}
+      full-matrix-algorithm: ${{ steps.generate-matrix.outputs.full-matrix-algorithm }}
+      full-smoke-overlap-count: ${{ steps.generate-matrix.outputs.full-smoke-overlap-count }}
+      estimated-stage2-jobs: ${{ steps.generate-matrix.outputs.estimated-stage2-jobs }}
+      total-two-stage-jobs: ${{ steps.generate-matrix.outputs.total-two-stage-jobs }}
+      effective-reduction-ratio: ${{ steps.generate-matrix.outputs.effective-reduction-ratio }}
       filter-json: ${{ steps.generate-matrix.outputs.filter-json }}
     steps:
       - uses: actions/checkout@v6.0.1
@@ -77,6 +92,7 @@ jobs:
           FILTER_CORE_INFRA: ${{ steps.filter.outputs.core_infra }}
           FILTER_TEST_FRAMEWORK: ${{ steps.filter.outputs.test_framework }}
           FILTER_POM_CHANGES: ${{ steps.filter.outputs.pom_changes }}
+          FULL_MATRIX_ALGORITHM_INPUT: ${{ github.event_name == 'workflow_dispatch' && github.event.inputs.full_matrix_algorithm || 'auto' }}
         run: |
           filters=$(jq -cn \
             --arg adapter_proxy          "$FILTER_ADAPTER_PROXY" \
@@ -105,6 +121,11 @@ jobs:
           echo "smoke-matrix=${{ steps.generate-matrix.outputs.smoke-matrix }}"
           echo "has-jobs=${{ steps.generate-matrix.outputs.has-jobs }}"
           echo "need-proxy-image=${{ steps.generate-matrix.outputs.need-proxy-image }}"
+          echo "full-matrix-algorithm=${{ steps.generate-matrix.outputs.full-matrix-algorithm }}"
+          echo "full-smoke-overlap-count=${{ steps.generate-matrix.outputs.full-smoke-overlap-count }}"
+          echo "estimated-stage2-jobs=${{ steps.generate-matrix.outputs.estimated-stage2-jobs }}"
+          echo "total-two-stage-jobs=${{ steps.generate-matrix.outputs.total-two-stage-jobs }}"
+          echo "effective-reduction-ratio=${{ steps.generate-matrix.outputs.effective-reduction-ratio }}"
           echo "filter-json=${{ steps.generate-matrix.outputs.filter-json }}"
 
   prepare-e2e-artifacts:
diff --git a/.github/workflows/resources/scripts/e2e-sql/generate-e2e-sql-matrix.sh b/.github/workflows/resources/scripts/e2e-sql/generate-e2e-sql-matrix.sh
index 2fb161a5fd1..94da7fbf9cc 100755
--- a/.github/workflows/resources/scripts/e2e-sql/generate-e2e-sql-matrix.sh
+++ b/.github/workflows/resources/scripts/e2e-sql/generate-e2e-sql-matrix.sh
@@ -17,35 +17,29 @@
 #
 
 # Usage: generate-e2e-sql-matrix.sh '<json-with-all-18-filter-labels>'
-# Output: writes smoke-matrix=<JSON>, full-matrix=<JSON>, matrix=<JSON>(alias for full), has-jobs=<true|false>, and need-proxy-image=<true|false> to $GITHUB_OUTPUT
+# Environment:
+#   FULL_MATRIX_ALGORITHM_INPUT: auto|cartesian|pairwise (optional, default auto)
+# Output: writes smoke-matrix=<JSON>, full-matrix=<JSON>, matrix=<JSON>(alias for full), has-jobs=<true|false>, need-proxy-image=<true|false>,
+#         full-matrix-algorithm=<cartesian|pairwise|auto>, full-smoke-overlap-count=<N>, estimated-stage2-jobs=<N>,
+#         total-two-stage-jobs=<N>, and effective-reduction-ratio=<0..1> to $GITHUB_OUTPUT
 
 set -euo pipefail
 
 FILTERS_JSON="$1"
 
-get_filter() {
-  echo "$FILTERS_JSON" | jq -r ".$1"
-}
-
 # Read all 18 filter labels
-adapter_proxy=$(get_filter adapter_proxy)
-adapter_jdbc=$(get_filter adapter_jdbc)
-mode_standalone=$(get_filter mode_standalone)
-mode_cluster=$(get_filter mode_cluster)
-mode_core=$(get_filter mode_core)
-database_mysql=$(get_filter database_mysql)
-database_postgresql=$(get_filter database_postgresql)
-feature_sharding=$(get_filter feature_sharding)
-feature_encrypt=$(get_filter feature_encrypt)
-feature_readwrite_splitting=$(get_filter feature_readwrite_splitting)
-feature_shadow=$(get_filter feature_shadow)
-feature_mask=$(get_filter feature_mask)
-feature_broadcast=$(get_filter feature_broadcast)
-feature_distsql=$(get_filter feature_distsql)
-feature_sql_federation=$(get_filter feature_sql_federation)
-core_infra=$(get_filter core_infra)
-test_framework=$(get_filter test_framework)
-pom_changes=$(get_filter pom_changes)
+IFS=$'\t' read -r \
+  adapter_proxy adapter_jdbc mode_standalone mode_cluster mode_core \
+  database_mysql database_postgresql \
+  feature_sharding feature_encrypt feature_readwrite_splitting feature_shadow feature_mask \
+  feature_broadcast feature_distsql feature_sql_federation \
+  core_infra test_framework pom_changes <<< "$(echo "$FILTERS_JSON" | jq -r '[
+    .adapter_proxy, .adapter_jdbc, .mode_standalone, .mode_cluster, .mode_core,
+    .database_mysql, .database_postgresql,
+    .feature_sharding, .feature_encrypt, .feature_readwrite_splitting, .feature_shadow, .feature_mask,
+    .feature_broadcast, .feature_distsql, .feature_sql_federation,
+    .core_infra, .test_framework, .pom_changes
+  ] | @tsv')"
 
 ALL_SCENARIOS=$(jq -cn '[
   "empty_rules", "distsql_rdl", "passthrough",
@@ -107,6 +101,156 @@ build_matrix() {
     '
 }
 
+build_pairwise_matrix() {
+  # Algorithm note:
+  # This implementation is NOT ACTS/IPOG itself. It is a deterministic greedy
+  # 2-way covering strategy with mandatory scenario anchors:
+  #   1) Start from constrained candidate jobs (existing include/exclude rules).
+  #   2) Preselect additional-options jobs (to preserve required special cases).
+  #   3) Select one anchor job per scenario.
+  #   4) Greedily add the job that covers the most uncovered parameter pairs.
+  #
+  # This approach follows public combinatorial-testing principles and does not
+  # copy ACTS implementation code.
+  # References:
+  # - NIST combinatorial testing project (ACTS/IPOG background):
+  #   https://csrc.nist.gov/projects/automated-combinatorial-testing-for-software
+  # - Interaction rule overview:
+  #   https://csrc.nist.gov/projects/automated-combinatorial-testing-for-software/combinatorial-methods-in-testing/interactions-involved-in-software-failures
+  # - Greedy set-cover approximation idea (well-known heuristic):
+  #   https://en.wikipedia.org/wiki/Set_cover_problem
+  local candidate_matrix="$1"
+  local scenario_list_json="$2"
+  local job_file selected_file
+  job_file=$(mktemp)
+  selected_file=$(mktemp)
+  echo "$candidate_matrix" | jq -r '
+    .include[] |
+    [
+      ([
+        ("am:" + .adapter + "|" + .mode),
+        ("ad:" + .adapter + "|" + .database),
+        ("md:" + .mode + "|" + .database),
+        ("as:" + .adapter + "|" + .scenario),
+        ("ms:" + .mode + "|" + .scenario),
+        ("ds:" + .database + "|" + .scenario)
+      ] | join(",")),
+      ((if .adapter == "proxy" then 4 else 0 end) + (if .mode == "Cluster" then 2 else 0 end) + (if .database == "MySQL" then 1 else 0 end) + (if .["additional-options"] == "" then 1 else 0 end) | tostring),
+      .scenario,
+      (if .["additional-options"] != "" then "true" else "false" end),
+      (tojson)
+    ] | @tsv
+  ' > "$job_file"
+  declare -a jobs job_scores job_scenarios job_has_additional selected_indexes selected_flags
+  declare -a job_pair_1 job_pair_2 job_pair_3 job_pair_4 job_pair_5 job_pair_6
+  jobs=()
+  job_scores=()
+  job_scenarios=()
+  job_has_additional=()
+  selected_indexes=()
+  selected_flags=()
+  job_pair_1=()
+  job_pair_2=()
+  job_pair_3=()
+  job_pair_4=()
+  job_pair_5=()
+  job_pair_6=()
+  local pairs score scenario has_additional job_json idx
+  local pair1 pair2 pair3 pair4 pair5 pair6
+  local best_idx best_score candidate_score candidate_new
+  local pick_idx pick_new pick_score required_scenario new_pairs
+  local _pair
+  local covered_pairs_blob
+  covered_pairs_blob=$'\n'
+  while IFS=$'\t' read -r pairs score scenario has_additional job_json; do
+    IFS=',' read -r pair1 pair2 pair3 pair4 pair5 pair6 <<< "$pairs"
+    idx="${#jobs[@]}"
+    jobs[$idx]="$job_json"
+    job_scores[$idx]="$score"
+    job_scenarios[$idx]="$scenario"
+    job_has_additional[$idx]="$has_additional"
+    selected_flags[$idx]=0
+    job_pair_1[$idx]="$pair1"
+    job_pair_2[$idx]="$pair2"
+    job_pair_3[$idx]="$pair3"
+    job_pair_4[$idx]="$pair4"
+    job_pair_5[$idx]="$pair5"
+    job_pair_6[$idx]="$pair6"
+  done < "$job_file"
+  if [ "${#jobs[@]}" -eq 0 ]; then
+    rm -f "$job_file" "$selected_file"
+    echo '{"include":[]}'
+    return
+  fi
+  add_selected_index() {
+    local idx="$1"
+    local _pair
+    [ "${selected_flags[$idx]}" -eq 1 ] && return
+    selected_flags[$idx]=1
+    selected_indexes+=("$idx")
+    for _pair in "${job_pair_1[$idx]}" "${job_pair_2[$idx]}" "${job_pair_3[$idx]}" "${job_pair_4[$idx]}" "${job_pair_5[$idx]}" "${job_pair_6[$idx]}"; do
+      case "$covered_pairs_blob" in
+        *$'\n'"$_pair"$'\n'*) ;;
+        *) covered_pairs_blob+="${_pair}"$'\n' ;;
+      esac
+    done
+  }
+  count_new_pairs() {
+    local idx="$1"
+    new_pairs=0
+    local _pair
+    for _pair in "${job_pair_1[$idx]}" "${job_pair_2[$idx]}" "${job_pair_3[$idx]}" "${job_pair_4[$idx]}" "${job_pair_5[$idx]}" "${job_pair_6[$idx]}"; do
+      case "$covered_pairs_blob" in
+        *$'\n'"$_pair"$'\n'*) ;;
+        *) new_pairs=$((new_pairs + 1)) ;;
+      esac
+    done
+  }
+  for idx in "${!jobs[@]}"; do
+    if [ "${job_has_additional[$idx]}" = "true" ]; then
+      add_selected_index "$idx"
+    fi
+  done
+  while IFS= read -r required_scenario; do
+    best_idx=-1
+    best_score=-1
+    for idx in "${!jobs[@]}"; do
+      [ "${job_scenarios[$idx]}" = "$required_scenario" ] || continue
+      candidate_score="${job_scores[$idx]}"
+      if [ "$best_idx" -lt 0 ] || [ "$candidate_score" -gt "$best_score" ] || { [ "$candidate_score" -eq "$best_score" ] && [ "$idx" -lt "$best_idx" ]; }; then
+        best_idx="$idx"
+        best_score="$candidate_score"
+      fi
+    done
+    [ "$best_idx" -lt 0 ] || add_selected_index "$best_idx"
+  done < <(echo "$scenario_list_json" | jq -r '.[]')
+  while true; do
+    pick_idx=-1
+    pick_new=0
+    pick_score=-1
+    for idx in "${!jobs[@]}"; do
+      [ "${selected_flags[$idx]}" -eq 1 ] && continue
+      count_new_pairs "$idx"
+      candidate_new="$new_pairs"
+      [ "$candidate_new" -gt 0 ] || continue
+      candidate_score="${job_scores[$idx]}"
+      if [ "$pick_idx" -lt 0 ] || [ "$candidate_new" -gt "$pick_new" ] || { [ "$candidate_new" -eq "$pick_new" ] && [ "$candidate_score" -gt "$pick_score" ]; } || { [ "$candidate_new" -eq "$pick_new" ] && [ "$candidate_score" -eq "$pick_score" ] && [ "$idx" -lt "$pick_idx" ]; }; then
+        pick_idx="$idx"
+        pick_new="$candidate_new"
+        pick_score="$candidate_score"
+      fi
+    done
+    [ "$pick_idx" -lt 0 ] && break
+    add_selected_index "$pick_idx"
+  done
+  for idx in "${selected_indexes[@]}"; do
+    echo "${jobs[$idx]}" >> "$selected_file"
+  done
+  pairwise_matrix=$(jq -sc '{include: .}' "$selected_file")
+  rm -f "$job_file" "$selected_file"
+  echo "$pairwise_matrix"
+}
+
 log_counts() {
   local name="$1"
   local matrix_json="$2"
@@ -121,12 +265,22 @@ if [ "$core_infra" = "true" ] || [ "$test_framework" = "true" ] || [ "$pom_chang
   echo "::notice::Base filters triggered (core_infra=$core_infra, test_framework=$test_framework, pom_changes=$pom_changes)"
 fi
 
-# Handle workflow_dispatch: run full tests when manually triggered
+manual_dispatch=false
 if [ "${GITHUB_EVENT_NAME:-}" = "workflow_dispatch" ]; then
-  any_base_change=true
-  echo "::notice::workflow_dispatch detected, enabling full test matrix"
+  manual_dispatch=true
+  echo "::notice::workflow_dispatch detected"
 fi
 
+requested_full_matrix_algorithm="${FULL_MATRIX_ALGORITHM_INPUT:-auto}"
+case "$requested_full_matrix_algorithm" in
+  auto|cartesian|pairwise)
+    ;;
+  *)
+    echo "::warning::Invalid FULL_MATRIX_ALGORITHM_INPUT=$requested_full_matrix_algorithm, fallback to auto"
+    requested_full_matrix_algorithm="auto"
+    ;;
+esac
+
 # Check whether any relevant dimension changed at all
 any_relevant_change=false
 if [ "$feature_sharding" = "true" ] || [ "$feature_encrypt" = "true" ] || \
@@ -141,12 +295,18 @@ if [ "$feature_sharding" = "true" ] || [ "$feature_encrypt" = "true" ] || \
   echo "::notice::At least one relevant filter is true, will generate jobs based on dimensions and scenarios"
 fi
 
+if [ "$manual_dispatch" = "true" ]; then
+  any_relevant_change=true
+  echo "::notice::workflow_dispatch enforces relevant-change path"
+fi
+
 if [ "$any_relevant_change" = "false" ]; then
   echo "matrix={\"include\":[]}" >> "$GITHUB_OUTPUT"
   echo "has-jobs=false" >> "$GITHUB_OUTPUT"
   echo "need-proxy-image=false" >> "$GITHUB_OUTPUT"
   echo "smoke-matrix={\"include\":[]}" >> "$GITHUB_OUTPUT"
   echo "full-matrix={\"include\":[]}" >> "$GITHUB_OUTPUT"
+  echo "full-matrix-algorithm=auto" >> "$GITHUB_OUTPUT"
   echo "::notice::No relevant filters triggered, skipping job generation"
   exit 0
 fi
@@ -281,7 +441,25 @@ if [ "$any_feature_triggered" = "true" ]; then
   echo "::notice::Feature filters triggered, including all adapters, modes, and databases"
 fi
 
-echo "::notice::any_base_change=$any_base_change, any_feature_triggered=$any_feature_triggered, dimensions adapters=$adapters modes=$modes databases=$databases"
+if [ "$manual_dispatch" = "true" ]; then
+  adapters=$ALL_ADAPTERS
+  modes=$ALL_MODES
+  databases=$ALL_DATABASES
+  echo "::notice::workflow_dispatch uses all adapters, modes, and databases"
+fi
+
+effective_full_matrix_algorithm="$requested_full_matrix_algorithm"
+if [ "$effective_full_matrix_algorithm" = "auto" ]; then
+  if [ "$manual_dispatch" = "true" ]; then
+    effective_full_matrix_algorithm="cartesian"
+  elif [ "$any_base_change" = "true" ] || [ "$any_feature_triggered" = "true" ]; then
+    effective_full_matrix_algorithm="pairwise"
+  else
+    effective_full_matrix_algorithm="cartesian"
+  fi
+fi
+
+echo "::notice::any_base_change=$any_base_change, any_feature_triggered=$any_feature_triggered, dimensions adapters=$adapters modes=$modes databases=$databases, full-matrix-algorithm(requested=$requested_full_matrix_algorithm,effective=$effective_full_matrix_algorithm)"
 
 # Generate smoke-matrix from default or feature-mapped smoke scenarios, and DO NOT add the extra passthrough job
 if [ "$any_feature_triggered" = "true" ]; then
@@ -300,7 +478,10 @@ SMOKE_MATRIX=$(build_matrix "$adapters" "$modes" "$databases" "$smoke_scenarios_
 log_counts "smoke-matrix" "$SMOKE_MATRIX"
 
 # Build full-matrix scenarios
-if [ "$any_base_change" = "true" ]; then
+if [ "$manual_dispatch" = "true" ]; then
+  full_scenarios_json="$ALL_SCENARIOS"
+  echo "::notice::full-matrix reason=workflow-dispatch, use all scenarios: $full_scenarios_json"
+elif [ "$any_base_change" = "true" ]; then
   full_scenarios_json="$ALL_SCENARIOS"
   echo "::notice::full-matrix reason=base-change, use all scenarios: $full_scenarios_json"
 else
@@ -314,17 +495,57 @@ else
   fi
 fi
 
-FULL_MATRIX=$(build_matrix "$adapters" "$modes" "$databases" "$full_scenarios_json" true)
+FULL_MATRIX_CANDIDATE=$(build_matrix "$adapters" "$modes" "$databases" "$full_scenarios_json" true)
+FULL_MATRIX_CANDIDATE_COUNT=$(echo "$FULL_MATRIX_CANDIDATE" | jq '.include | length')
+if [ "$effective_full_matrix_algorithm" = "pairwise" ]; then
+  if [ "$FULL_MATRIX_CANDIDATE_COUNT" -le 20 ]; then
+    FULL_MATRIX="$FULL_MATRIX_CANDIDATE"
+    echo "::notice::full-matrix pairwise skipped due to small candidate set: candidate=$FULL_MATRIX_CANDIDATE_COUNT"
+  else
+    FULL_MATRIX=$(build_pairwise_matrix "$FULL_MATRIX_CANDIDATE" "$full_scenarios_json")
+    echo "::notice::full-matrix reduction applied: candidate=$FULL_MATRIX_CANDIDATE_COUNT, reduced=$(echo "$FULL_MATRIX" | jq '.include | length')"
+  fi
+else
+  FULL_MATRIX="$FULL_MATRIX_CANDIDATE"
+fi
 log_counts "full-matrix" "$FULL_MATRIX"
 
 # Determine whether there are any jobs at all (based on full-matrix)
 FULL_JOB_COUNT=$(echo "$FULL_MATRIX" | jq '.include | length')
+SMOKE_JOB_COUNT=$(echo "$SMOKE_MATRIX" | jq '.include | length')
+FULL_SMOKE_OVERLAP_COUNT=$(jq -n --argjson full "$FULL_MATRIX" --argjson smoke "$SMOKE_MATRIX" '
+  [
+    $full.include[] as $job |
+    select(
+      [$smoke.include[] | select(
+        .adapter == $job.adapter and
+        .mode == $job.mode and
+        .database == $job.database and
+        .scenario == $job.scenario and
+        .["additional-options"] == $job["additional-options"]
+      )] | length > 0
+    )
+  ] | length
+')
+ESTIMATED_STAGE2_JOBS=$((FULL_JOB_COUNT - FULL_SMOKE_OVERLAP_COUNT))
+TOTAL_TWO_STAGE_JOBS=$((SMOKE_JOB_COUNT + ESTIMATED_STAGE2_JOBS))
+if [ "$FULL_MATRIX_CANDIDATE_COUNT" -eq 0 ]; then
+  EFFECTIVE_REDUCTION_RATIO="0"
+else
+  EFFECTIVE_REDUCTION_RATIO=$(jq -cn --argjson candidate "$FULL_MATRIX_CANDIDATE_COUNT" --argjson total "$TOTAL_TWO_STAGE_JOBS" '1 - ($total / $candidate)')
+fi
+echo "::notice::matrix-breakdown full=$FULL_JOB_COUNT smoke=$SMOKE_JOB_COUNT overlap=$FULL_SMOKE_OVERLAP_COUNT estimated-stage2=$ESTIMATED_STAGE2_JOBS total-two-stage=$TOTAL_TWO_STAGE_JOBS effective-reduction-ratio=$EFFECTIVE_REDUCTION_RATIO"
 if [ "$FULL_JOB_COUNT" -eq 0 ]; then
   echo "smoke-matrix=$(echo "$SMOKE_MATRIX" | jq -c .)" >> "$GITHUB_OUTPUT"
   echo "full-matrix={\"include\":[]}" >> "$GITHUB_OUTPUT"
   echo "matrix={\"include\":[]}" >> "$GITHUB_OUTPUT"
   echo "has-jobs=false" >> "$GITHUB_OUTPUT"
   echo "need-proxy-image=false" >> "$GITHUB_OUTPUT"
+  echo "full-matrix-algorithm=$effective_full_matrix_algorithm" >> "$GITHUB_OUTPUT"
+  echo "full-smoke-overlap-count=0" >> "$GITHUB_OUTPUT"
+  echo "estimated-stage2-jobs=0" >> "$GITHUB_OUTPUT"
+  echo "total-two-stage-jobs=0" >> "$GITHUB_OUTPUT"
+  echo "effective-reduction-ratio=0" >> "$GITHUB_OUTPUT"
   echo "::notice::No jobs generated after applying all filters and rules, skipping job execution"
   exit 0
 fi
@@ -338,6 +559,11 @@ echo "full-matrix=$(echo "$FULL_MATRIX" | jq -c .)" >> "$GITHUB_OUTPUT"
 echo "matrix=$(echo "$FULL_MATRIX" | jq -c .)" >> "$GITHUB_OUTPUT"
 echo "has-jobs=true" >> "$GITHUB_OUTPUT"
 echo "need-proxy-image=$NEED_PROXY_IMAGE" >> "$GITHUB_OUTPUT"
-echo "::notice::Generated $(echo "$SMOKE_MATRIX" | jq '.include | length') smoke jobs and $(echo "$FULL_MATRIX" | jq '.include | length') full jobs. Proxy image needed: $NEED_PROXY_IMAGE"
+echo "full-matrix-algorithm=$effective_full_matrix_algorithm" >> "$GITHUB_OUTPUT"
+echo "full-smoke-overlap-count=$FULL_SMOKE_OVERLAP_COUNT" >> "$GITHUB_OUTPUT"
+echo "estimated-stage2-jobs=$ESTIMATED_STAGE2_JOBS" >> "$GITHUB_OUTPUT"
+echo "total-two-stage-jobs=$TOTAL_TWO_STAGE_JOBS" >> "$GITHUB_OUTPUT"
+echo "effective-reduction-ratio=$EFFECTIVE_REDUCTION_RATIO" >> "$GITHUB_OUTPUT"
+echo "::notice::Generated $SMOKE_JOB_COUNT smoke jobs, $FULL_JOB_COUNT full jobs, overlap=$FULL_SMOKE_OVERLAP_COUNT, estimated stage2 jobs=$ESTIMATED_STAGE2_JOBS, total two-stage jobs=$TOTAL_TWO_STAGE_JOBS, effective reduction ratio=$EFFECTIVE_REDUCTION_RATIO. Proxy image needed: $NEED_PROXY_IMAGE"
 
 exit 0
diff --git a/.github/workflows/resources/scripts/e2e-sql/test-generate-e2e-sql-matrix.sh b/.github/workflows/resources/scripts/e2e-sql/test-generate-e2e-sql-matrix.sh
index f5326519e8e..ec76158b984 100644
--- a/.github/workflows/resources/scripts/e2e-sql/test-generate-e2e-sql-matrix.sh
+++ b/.github/workflows/resources/scripts/e2e-sql/test-generate-e2e-sql-matrix.sh
@@ -43,9 +43,10 @@ build_filters() {
 run_script() {
   local filters="$1"
   local event_name="${2:-pull_request}"
+  local full_matrix_algorithm_input="${3:-auto}"
   local output_file
   output_file=$(mktemp)
-  GITHUB_OUTPUT="$output_file" GITHUB_EVENT_NAME="$event_name" \
+  GITHUB_OUTPUT="$output_file" GITHUB_EVENT_NAME="$event_name" FULL_MATRIX_ALGORITHM_INPUT="$full_matrix_algorithm_input" \
     bash "$TARGET_SCRIPT" "$filters" > /dev/null 2>&1
   local rc=$?
   cat "$output_file"
@@ -78,6 +79,15 @@ assert_eq() {
   fi
 }
 
+assert_not_empty() {
+  local desc="$1" actual="$2"
+  if [ -n "$actual" ]; then
+    pass "$desc"
+  else
+    fail "$desc" "expected non-empty value"
+  fi
+}
+
 assert_all_scenarios() {
   local desc="$1" matrix_json="$2"
   local expected actual
@@ -132,10 +142,37 @@ assert_all_dimensions() {
   assert_eq "$label: has both databases" "2" "$(echo "$matrix_json" | jq '[.include[].database] | unique | length')"
 }
 
+assert_less_than() {
+  local desc="$1" actual="$2" upper_bound="$3"
+  if [ "$actual" -lt "$upper_bound" ]; then
+    pass "$desc"
+  else
+    fail "$desc" "actual='$actual' is not less than upper_bound='$upper_bound'"
+  fi
+}
+
+assert_matrix_breakdown_consistency() {
+  local desc="$1" outputs="$2"
+  local smoke_matrix full_matrix overlap stage2 total
+  local smoke_count full_count expected_stage2 expected_total
+  smoke_matrix=$(get_output "$outputs" "smoke-matrix")
+  full_matrix=$(get_output "$outputs" "full-matrix")
+  overlap=$(get_output "$outputs" "full-smoke-overlap-count")
+  stage2=$(get_output "$outputs" "estimated-stage2-jobs")
+  total=$(get_output "$outputs" "total-two-stage-jobs")
+  smoke_count=$(echo "$smoke_matrix" | jq '.include | length')
+  full_count=$(echo "$full_matrix" | jq '.include | length')
+  expected_stage2=$((full_count - overlap))
+  expected_total=$((smoke_count + stage2))
+  assert_eq "$desc: stage2=full-overlap" "$expected_stage2" "$stage2"
+  assert_eq "$desc: total=smoke+stage2" "$expected_total" "$total"
+}
+
 # Common assertions for full-trigger tests (base change / workflow_dispatch)
 assert_full_trigger() {
-  local label="$1" outputs="$2"
+  local label="$1" outputs="$2" expected_algorithm="$3"
   assert_eq "$label: has-jobs" "true" "$(get_output "$outputs" "has-jobs")"
+  assert_eq "$label: full-matrix-algorithm" "$expected_algorithm" "$(get_output "$outputs" "full-matrix-algorithm")"
   local smoke_matrix
   smoke_matrix=$(get_output "$outputs" "smoke-matrix")
   assert_scenarios "$label: smoke-matrix uses default scenarios" "$smoke_matrix" '["db","tbl"]'
@@ -145,6 +182,11 @@ assert_full_trigger() {
   assert_no_excludes "$label: full-matrix has no excluded combinations" "$full_matrix"
   assert_extra_passthrough_job "$label: full-matrix has extra passthrough job" "$full_matrix"
   assert_eq "$label: need-proxy-image" "true" "$(get_output "$outputs" "need-proxy-image")"
+  assert_not_empty "$label: full-smoke-overlap-count exists" "$(get_output "$outputs" "full-smoke-overlap-count")"
+  assert_not_empty "$label: estimated-stage2-jobs exists" "$(get_output "$outputs" "estimated-stage2-jobs")"
+  assert_not_empty "$label: total-two-stage-jobs exists" "$(get_output "$outputs" "total-two-stage-jobs")"
+  assert_not_empty "$label: effective-reduction-ratio exists" "$(get_output "$outputs" "effective-reduction-ratio")"
+  assert_matrix_breakdown_consistency "$label: matrix-breakdown consistency" "$outputs"
 }
 
 # ---------- prerequisite check ----------
@@ -175,17 +217,20 @@ assert_eq "#1: has-jobs" "false" "$(get_output "$outputs" "has-jobs")"
 echo ""
 echo "--- #2: core_infra=true ---"
 outputs=$(run_script "$(build_filters core_infra=true)")
-assert_full_trigger "#2" "$outputs"
+assert_full_trigger "#2" "$outputs" "pairwise"
+assert_less_than "#2: pairwise full-matrix is reduced" "$(echo "$(get_output "$outputs" "full-matrix")" | jq '.include | length')" "119"
 
 echo ""
 echo "--- #3: test_framework=true ---"
 outputs=$(run_script "$(build_filters test_framework=true)")
-assert_full_trigger "#3" "$outputs"
+assert_full_trigger "#3" "$outputs" "pairwise"
+assert_less_than "#3: pairwise full-matrix is reduced" "$(echo "$(get_output "$outputs" "full-matrix")" | jq '.include | length')" "119"
 
 echo ""
 echo "--- #4: pom_changes=true ---"
 outputs=$(run_script "$(build_filters pom_changes=true)")
-assert_full_trigger "#4" "$outputs"
+assert_full_trigger "#4" "$outputs" "pairwise"
+assert_less_than "#4: pairwise full-matrix is reduced" "$(echo "$(get_output "$outputs" "full-matrix")" | jq '.include | length')" "119"
 
 # ============================================================
 # B. workflow_dispatch
@@ -196,7 +241,18 @@ echo "=== B. workflow_dispatch ==="
 echo ""
 echo "--- #5: workflow_dispatch ---"
 outputs=$(run_script "$(build_filters)" "workflow_dispatch")
-assert_full_trigger "#5" "$outputs"
+assert_full_trigger "#5" "$outputs" "cartesian"
+
+echo ""
+echo "--- #6: workflow_dispatch with pairwise ---"
+outputs=$(run_script "$(build_filters)" "workflow_dispatch" "pairwise")
+assert_full_trigger "#6" "$outputs" "pairwise"
+assert_less_than "#6: workflow_dispatch pairwise full-matrix is reduced" "$(echo "$(get_output "$outputs" "full-matrix")" | jq '.include | length')" "119"
+
+echo ""
+echo "--- #7: workflow_dispatch with invalid algorithm falls back to auto(cartesian) ---"
+outputs=$(run_script "$(build_filters)" "workflow_dispatch" "invalid")
+assert_full_trigger "#7" "$outputs" "cartesian"
 
 # ============================================================
 # C. Dimension reduction
@@ -205,47 +261,47 @@ echo ""
 echo "=== C. Dimension reduction ==="
 
 echo ""
-echo "--- #6: adapter_proxy only ---"
+echo "--- #8: adapter_proxy only ---"
 outputs=$(run_script "$(build_filters adapter_proxy=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_all_field_eq "#6: smoke all adapter=proxy" "$smoke" "adapter" "proxy"
+assert_all_field_eq "#8: smoke all adapter=proxy" "$smoke" "adapter" "proxy"
 
 echo ""
-echo "--- #7: adapter_jdbc only ---"
+echo "--- #9: adapter_jdbc only ---"
 outputs=$(run_script "$(build_filters adapter_jdbc=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_all_field_eq "#7: smoke all adapter=jdbc" "$smoke" "adapter" "jdbc"
-assert_eq "#7: need-proxy-image" "false" "$(get_output "$outputs" "need-proxy-image")"
+assert_all_field_eq "#9: smoke all adapter=jdbc" "$smoke" "adapter" "jdbc"
+assert_eq "#9: need-proxy-image" "false" "$(get_output "$outputs" "need-proxy-image")"
 
 echo ""
-echo "--- #8: database_mysql only ---"
+echo "--- #10: database_mysql only ---"
 outputs=$(run_script "$(build_filters database_mysql=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_all_field_eq "#8: smoke all database=MySQL" "$smoke" "database" "MySQL"
+assert_all_field_eq "#10: smoke all database=MySQL" "$smoke" "database" "MySQL"
 
 echo ""
-echo "--- #9: database_postgresql only ---"
+echo "--- #11: database_postgresql only ---"
 outputs=$(run_script "$(build_filters database_postgresql=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_all_field_eq "#9: smoke all database=PostgreSQL" "$smoke" "database" "PostgreSQL"
+assert_all_field_eq "#11: smoke all database=PostgreSQL" "$smoke" "database" "PostgreSQL"
 
 echo ""
-echo "--- #10: mode_standalone only ---"
+echo "--- #12: mode_standalone only ---"
 outputs=$(run_script "$(build_filters mode_standalone=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_all_field_eq "#10: smoke all mode=Standalone" "$smoke" "mode" "Standalone"
+assert_all_field_eq "#12: smoke all mode=Standalone" "$smoke" "mode" "Standalone"
 
 echo ""
-echo "--- #11: mode_cluster only ---"
+echo "--- #13: mode_cluster only ---"
 outputs=$(run_script "$(build_filters mode_cluster=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_all_field_eq "#11: smoke all mode=Cluster" "$smoke" "mode" "Cluster"
+assert_all_field_eq "#13: smoke all mode=Cluster" "$smoke" "mode" "Cluster"
 
 echo ""
-echo "--- #12: mode_core only ---"
+echo "--- #14: mode_core only ---"
 outputs=$(run_script "$(build_filters mode_core=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_eq "#12: smoke has both modes" "2" "$(echo "$smoke" | jq '[.include[].mode] | unique | length')"
+assert_eq "#14: smoke has both modes" "2" "$(echo "$smoke" | jq '[.include[].mode] | unique | length')"
 
 # ============================================================
 # D. Feature scenario mapping
@@ -254,81 +310,83 @@ echo ""
 echo "=== D. Feature scenario mapping ==="
 
 echo ""
-echo "--- #13: feature_sharding ---"
+echo "--- #15: feature_sharding ---"
 outputs=$(run_script "$(build_filters feature_sharding=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_scenarios "#13: sharding smoke scenarios" "$smoke" '["db","tbl"]'
+assert_scenarios "#15: sharding smoke scenarios" "$smoke" '["db","tbl"]'
 full=$(get_output "$outputs" "full-matrix")
 expected_sharding='["db","tbl","dbtbl_with_readwrite_splitting","dbtbl_with_readwrite_splitting_and_encrypt","sharding_and_encrypt","sharding_and_shadow","sharding_encrypt_shadow","mask_sharding","mask_encrypt_sharding","db_tbl_sql_federation"]'
-assert_scenarios "#13: sharding scenarios" "$full" "$expected_sharding"
-assert_all_dimensions "#13" "$full"
+assert_scenarios "#15: sharding scenarios" "$full" "$expected_sharding"
+assert_all_dimensions "#15" "$full"
+assert_eq "#15: full-matrix-algorithm" "pairwise" "$(get_output "$outputs" "full-matrix-algorithm")"
 
 echo ""
-echo "--- #14: feature_encrypt ---"
+echo "--- #16: feature_encrypt ---"
 outputs=$(run_script "$(build_filters feature_encrypt=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_scenarios "#14: encrypt smoke scenarios" "$smoke" '["encrypt"]'
+assert_scenarios "#16: encrypt smoke scenarios" "$smoke" '["encrypt"]'
 full=$(get_output "$outputs" "full-matrix")
 expected_encrypt='["encrypt","dbtbl_with_readwrite_splitting_and_encrypt","sharding_and_encrypt","encrypt_and_readwrite_splitting","encrypt_shadow","sharding_encrypt_shadow","mask_encrypt","mask_encrypt_sharding"]'
-assert_scenarios "#14: encrypt scenarios" "$full" "$expected_encrypt"
-assert_all_dimensions "#14" "$full"
+assert_scenarios "#16: encrypt scenarios" "$full" "$expected_encrypt"
+assert_all_dimensions "#16" "$full"
+assert_eq "#16: full-matrix-algorithm" "pairwise" "$(get_output "$outputs" "full-matrix-algorithm")"
 
 echo ""
-echo "--- #15: feature_readwrite_splitting ---"
+echo "--- #17: feature_readwrite_splitting ---"
 outputs=$(run_script "$(build_filters feature_readwrite_splitting=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_scenarios "#15: readwrite_splitting smoke scenarios" "$smoke" '["readwrite_splitting"]'
+assert_scenarios "#17: readwrite_splitting smoke scenarios" "$smoke" '["readwrite_splitting"]'
 full=$(get_output "$outputs" "full-matrix")
 expected_rws='["readwrite_splitting","dbtbl_with_readwrite_splitting","dbtbl_with_readwrite_splitting_and_encrypt","encrypt_and_readwrite_splitting","readwrite_splitting_and_shadow"]'
-assert_scenarios "#15: readwrite_splitting scenarios" "$full" "$expected_rws"
-assert_all_dimensions "#15" "$full"
+assert_scenarios "#17: readwrite_splitting scenarios" "$full" "$expected_rws"
+assert_all_dimensions "#17" "$full"
 
 echo ""
-echo "--- #16: feature_shadow ---"
+echo "--- #18: feature_shadow ---"
 outputs=$(run_script "$(build_filters feature_shadow=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_scenarios "#16: shadow smoke scenarios" "$smoke" '["shadow"]'
+assert_scenarios "#18: shadow smoke scenarios" "$smoke" '["shadow"]'
 full=$(get_output "$outputs" "full-matrix")
 expected_shadow='["shadow","encrypt_shadow","readwrite_splitting_and_shadow","sharding_and_shadow","sharding_encrypt_shadow"]'
-assert_scenarios "#16: shadow scenarios" "$full" "$expected_shadow"
-assert_all_dimensions "#16" "$full"
+assert_scenarios "#18: shadow scenarios" "$full" "$expected_shadow"
+assert_all_dimensions "#18" "$full"
 
 echo ""
-echo "--- #17: feature_mask ---"
+echo "--- #19: feature_mask ---"
 outputs=$(run_script "$(build_filters feature_mask=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_scenarios "#17: mask smoke scenarios" "$smoke" '["mask"]'
+assert_scenarios "#19: mask smoke scenarios" "$smoke" '["mask"]'
 full=$(get_output "$outputs" "full-matrix")
 expected_mask='["mask","mask_encrypt","mask_sharding","mask_encrypt_sharding"]'
-assert_scenarios "#17: mask scenarios" "$full" "$expected_mask"
-assert_all_dimensions "#17" "$full"
+assert_scenarios "#19: mask scenarios" "$full" "$expected_mask"
+assert_all_dimensions "#19" "$full"
 
 echo ""
-echo "--- #18: feature_distsql ---"
+echo "--- #20: feature_distsql ---"
 outputs=$(run_script "$(build_filters feature_distsql=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_scenarios "#18: distsql smoke scenarios" "$smoke" '["distsql_rdl"]'
+assert_scenarios "#20: distsql smoke scenarios" "$smoke" '["distsql_rdl"]'
 full=$(get_output "$outputs" "full-matrix")
-assert_scenarios "#18: distsql scenarios" "$full" '["distsql_rdl"]'
-assert_all_dimensions "#18" "$full"
+assert_scenarios "#20: distsql scenarios" "$full" '["distsql_rdl"]'
+assert_all_dimensions "#20" "$full"
 
 echo ""
-echo "--- #19: feature_sql_federation ---"
+echo "--- #21: feature_sql_federation ---"
 outputs=$(run_script "$(build_filters feature_sql_federation=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_scenarios "#19: sql_federation smoke scenarios" "$smoke" '["db_tbl_sql_federation"]'
+assert_scenarios "#21: sql_federation smoke scenarios" "$smoke" '["db_tbl_sql_federation"]'
 full=$(get_output "$outputs" "full-matrix")
-assert_scenarios "#19: sql_federation scenarios" "$full" '["db_tbl_sql_federation"]'
-assert_all_dimensions "#19" "$full"
+assert_scenarios "#21: sql_federation scenarios" "$full" '["db_tbl_sql_federation"]'
+assert_all_dimensions "#21" "$full"
 
 echo ""
-echo "--- #20: feature_broadcast ---"
+echo "--- #22: feature_broadcast ---"
 outputs=$(run_script "$(build_filters feature_broadcast=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_scenarios "#20: broadcast smoke scenarios" "$smoke" '["empty_rules"]'
+assert_scenarios "#22: broadcast smoke scenarios" "$smoke" '["empty_rules"]'
 full=$(get_output "$outputs" "full-matrix")
-assert_scenarios "#20: broadcast scenarios" "$full" '["empty_rules"]'
-assert_all_dimensions "#20" "$full"
+assert_scenarios "#22: broadcast scenarios" "$full" '["empty_rules"]'
+assert_all_dimensions "#22" "$full"
 
 # ============================================================
 # E. Mixed dimensions
@@ -337,32 +395,32 @@ echo ""
 echo "=== E. Mixed dimensions ==="
 
 echo ""
-echo "--- #21: base change overrides dimension filters ---"
+echo "--- #23: base change overrides dimension filters ---"
 outputs_mixed=$(run_script "$(build_filters adapter_proxy=true mode_standalone=true database_mysql=true core_infra=true)")
 outputs_base=$(run_script "$(build_filters core_infra=true)")
-assert_eq "#21: same full-matrix as core_infra only" \
+assert_eq "#23: same full-matrix as core_infra only" \
   "$(get_output "$outputs_base" "full-matrix")" \
   "$(get_output "$outputs_mixed" "full-matrix")"
-assert_eq "#21: same smoke-matrix as core_infra only" \
+assert_eq "#23: same smoke-matrix as core_infra only" \
   "$(get_output "$outputs_base" "smoke-matrix")" \
   "$(get_output "$outputs_mixed" "smoke-matrix")"
 
 echo ""
-echo "--- #22: feature trigger overrides dimension filters ---"
+echo "--- #24: feature trigger overrides dimension filters ---"
 outputs_mixed=$(run_script "$(build_filters adapter_jdbc=true feature_sharding=true)")
 outputs_feature=$(run_script "$(build_filters feature_sharding=true)")
-assert_eq "#22: same full-matrix as feature_sharding only" \
+assert_eq "#24: same full-matrix as feature_sharding only" \
   "$(get_output "$outputs_feature" "full-matrix")" \
   "$(get_output "$outputs_mixed" "full-matrix")"
-assert_eq "#22: same smoke-matrix as feature_sharding only" \
+assert_eq "#24: same smoke-matrix as feature_sharding only" \
   "$(get_output "$outputs_feature" "smoke-matrix")" \
   "$(get_output "$outputs_mixed" "smoke-matrix")"
 
 echo ""
-echo "--- #23: mixed features merge smoke scenarios ---"
+echo "--- #25: mixed features merge smoke scenarios ---"
 outputs=$(run_script "$(build_filters feature_sharding=true feature_encrypt=true)")
 smoke=$(get_output "$outputs" "smoke-matrix")
-assert_scenarios "#23: smoke scenarios are merged and deduplicated" "$smoke" '["db","encrypt","tbl"]'
+assert_scenarios "#25: smoke scenarios are merged and deduplicated" "$smoke" '["db","encrypt","tbl"]'
 
 # ============================================================
 # Summary