Improve cursor BBM sub-batch queries (!235758) · Merge requests · GitLab.org / GitLab

What does this MR do and why?

Improve cursor BBM sub-batch queries

Fixes the row-comparison folding inefficiency described in #599681 (closed). For cursor-based batched background migrations with a multi-column cursor, each sub-batch query previously had three row-style predicates stacked on the same cursor tuple:

WHERE (cursor_cols) >= start_cursor   -- from base_relation
  AND (cursor_cols) <= end_cursor     -- from base_relation
  AND (cursor_cols) >  prev_end       -- from Iterator

PostgreSQL cannot fold two row-constructor lower bounds against each other — _bt_preprocess_keys treats RowCompareExpr as opaque (see nbtpreprocesskeys.c). The planner picks one row-compare as the access predicate and applies the other during the index walk, so every sub-batch re-walks the index from start_cursor. For single-column cursors this is not a problem; for multi-column cursors it costs more.

This MR introduces Gitlab::Database::Batch::InclusiveCursorIterator, a thin wrapper around Pagination::Keyset::Iterator that runs the first sub-batch as a one-shot inclusive query ((cols) >= start_cursor) and hands phase 2 off to a vanilla Iterator seeded with phase 1's last yielded row. Result: every sub-batch query has exactly one row-style lower bound on the cursor columns, which the planner can fold cleanly with the upper bound into a single B-tree range.

BatchedMigrationJob#base_relation now holds only the upper bound (<= end_cursor); the lower bound moves to the wrapper.

References

Issue: #599681 (closed)

Screenshots or screen recordings

N/A — database framework change, no UI.

How to set up and validate locally

1. Verify the wrapper is wired into the canonical multi-column-cursor BBM

In bin/rails console:

range = MergeRequestDiffCommit.connection.exec_query(<<~SQL).first
  SELECT MIN(merge_request_diff_id) AS min, MAX(merge_request_diff_id) AS max FROM merge_request_diff_commits
SQL

migration = Gitlab::BackgroundMigration::BackfillMergeRequestDiffCommitsToPartitioned.new(
  start_cursor: [range['min'], 0],
  end_cursor:   [range['max'], 0],
  batch_table: 'merge_request_diff_commits',
  batch_column: 'id',
  sub_batch_size: 10,
  pause_ms: 100,
  connection: ApplicationRecord.connection
)

iter = migration.send(:sub_batch_relation)
puts iter.class
# => Gitlab::Database::Batch::InclusiveCursorIterator

Inspect per-sub-batch SQL shape

batch_num = 0
iter.each_batch(of: 10, load_batch: false) do |relation|
  batch_num += 1
  sql = relation.to_sql
  puts "[batch ##{batch_num}]"
  puts sql
  puts "  >= on tuple: #{sql.include?(') >= (') ? 'YES' : 'no'}"
  puts "  > on tuple:  #{sql =~ /\) > \(/ ? 'YES' : 'no'}"
  break if batch_num >= 4
end

Expected:

Batch #1: >= on tuple: YES, > on tuple: no (phase 1)
Batches #2.4: >= on tuple: no, > on tuple: YES (phase 2)
No batch ever shows BOTH YES — confirms the bug pattern is gone.

EXPLAIN ANALYZE on Database Lab

Query A (OLD, the bug)

View: https://console.postgres.ai/gitlab/gitlab-production-main/sessions/51694/commands/152590

SELECT *
  FROM merge_request_diff_commits
  WHERE (merge_request_diff_id, relative_order) >= (50000000, 0)
    AND (merge_request_diff_id, relative_order) <= (50050100, 0)
    AND (merge_request_diff_id, relative_order) >  (50050000, 0)
  ORDER BY merge_request_diff_id, relative_order
  LIMIT 1;

 Limit  (cost=0.71..1.51 rows=1 width=143) (actual time=87.845..87.847 rows=1 loops=1)
   Buffers: shared hit=461 read=1817
   ->  Index Scan using merge_request_diff_commits_pkey on public.merge_request_diff_commits  (cost=0.71..1216340240.11 rows=1527334601 width=143) (actual time=87.842..87.843 rows=1 loops=1)
         Index Cond: ((ROW(merge_request_diff_commits.merge_request_diff_id, merge_request_diff_commits.relative_order) >= ROW(50000000, 0)) AND (ROW(merge_request_diff_commits.merge_request_diff_id, merge_request_diff_commits.relative_order) <= ROW(50050100, 0)) AND (ROW(merge_request_diff_commits.merge_request_diff_id, merge_request_diff_commits.relative_order) > ROW(50050000, 0)))
         Buffers: shared hit=461 read=1817
Settings: seq_page_cost = '4', effective_cache_size = '472585MB', jit = 'off', random_page_cost = '1.5', work_mem = '230MB'

Query B (NEW phase 1)

View: https://console.postgres.ai/gitlab/gitlab-production-main/sessions/51694/commands/152591

SELECT *
  FROM merge_request_diff_commits
  WHERE (merge_request_diff_id, relative_order) >= (50000000, 0)
    AND (merge_request_diff_id, relative_order) <= (50050100, 0)
  ORDER BY merge_request_diff_id, relative_order
  LIMIT 1;

 Limit  (cost=0.71..1.51 rows=1 width=143) (actual time=0.025..0.026 rows=1 loops=1)
   Buffers: shared hit=6
   ->  Index Scan using merge_request_diff_commits_pkey on public.merge_request_diff_commits  (cost=0.71..1263200099.09 rows=1591242220 width=143) (actual time=0.024..0.024 rows=1 loops=1)
         Index Cond: ((ROW(merge_request_diff_commits.merge_request_diff_id, merge_request_diff_commits.relative_order) >= ROW(50000000, 0)) AND (ROW(merge_request_diff_commits.merge_request_diff_id, merge_request_diff_commits.relative_order) <= ROW(50050100, 0)))
         Buffers: shared hit=6
Settings: jit = 'off', random_page_cost = '1.5', work_mem = '230MB', seq_page_cost = '4', effective_cache_size = '472585MB'

Query C (NEW phase 2)

View: https://console.postgres.ai/gitlab/gitlab-production-main/sessions/51694/commands/152592

SELECT *
  FROM merge_request_diff_commits
  WHERE (merge_request_diff_id, relative_order) >  (50050000, 0)
    AND (merge_request_diff_id, relative_order) <= (50050100, 0)
  ORDER BY merge_request_diff_id, relative_order
  LIMIT 1;

 Limit  (cost=0.71..1.51 rows=1 width=143) (actual time=0.226..0.226 rows=1 loops=1)
   Buffers: shared hit=5 read=1
   ->  Index Scan using merge_request_diff_commits_pkey on public.merge_request_diff_commits  (cost=0.71..1263169228.92 rows=1591203291 width=143) (actual time=0.224..0.224 rows=1 loops=1)
         Index Cond: ((ROW(merge_request_diff_commits.merge_request_diff_id, merge_request_diff_commits.relative_order) > ROW(50050000, 0)) AND (ROW(merge_request_diff_commits.merge_request_diff_id, merge_request_diff_commits.relative_order) <= ROW(50050100, 0)))
         Buffers: shared hit=5 read=1
Settings: seq_page_cost = '4', effective_cache_size = '472585MB', jit = 'off', random_page_cost = '1.5', work_mem = '230MB'

Summary

All three queries return the same single row from the same logical range, only the predicates differ.

Query	Buffers (hit + read)	Disk reads	Time
A ( OLD form)	2,278 (461 + 1,817)	1,817 pages	87.85 ms
B ( NEW phase 1)	6	0	0.026 ms
C (NEW phase 2)	6	1	0.226 ms

OLD reads ~380× more buffers and runs ~388× slower than NEW phase 2. The extra ~2,272 buffers are index leaf pages PostgreSQL walked from start_cursor (50000000, 0) past prev_end_cursor (50050000, 0) before finding the first row also satisfying the strict lower bound. This is a known PostgreSQL planner limitation: when multiple row-constructor comparison predicates appear on the same column tuple, the planner cannot fold them against each other

4. Specs

bundle exec rspec spec/lib/gitlab/database/batch/inclusive_cursor_iterator_spec.rb
bundle exec rspec spec/lib/gitlab/background_migration/batched_migration_job_spec.rb

The new unit spec covers the wrapper in isolation (13 examples: validation, yield order/completeness, boundary inclusion, edge cases, SQL shape, phase 1→2 cursor handoff). The integration test in batched_migration_job_spec.rb exercises the fix end-to-end through BatchedMigrationJob#each_sub_batch and asserts no sub-batch SQL stacks >= and > on the cursor tuple.

MR acceptance checklist

Evaluate this MR against the MR acceptance checklist. It helps you analyze changes to reduce risks in quality, performance, reliability, security, and maintainability.

Edited May 13, 2026 by Imanpal Singh