Skip to content

[fix](rle) Fix infinite loop when a repeated run reaches 2^30 values - #69100

Merged
gavinchou merged 1 commit into
apache:masterfrom
liaoxin01:fix-rle-repeat-run-overflow-master
Oct 16, 2026
Merged

gavinchou merged 1 commit into
apache:masterfrom
liaoxin01:fix-rle-repeat-run-overflow-master

Conversation

@liaoxin01

Copy link
Copy Markdown
Contributor

What problem does this PR solve?

Problem Summary:

RleEncoder::FlushRepeatedRun() wrote repeat_count_ << 1 into an int32_t. repeat_count_ was an int, so a repeated run of 2^30 or more values overflowed the indicator into a negative number. BitWriter::PutVlqInt() then took that as an int32_t and shifted it right arithmetically:

inline void BitWriter::PutVlqInt(int32_t v) {
    while ((v & 0xFFFFFF80) != 0L) {
        PutAligned<uint8_t>((v & 0x7F) | 0x80, 1);
        v >>= 7;
    }
    PutAligned<uint8_t>(v & 0x7F, 1);
}

An arithmetic right shift of a negative value converges to -1 and stays there, and -1 & 0xFFFFFF80 is non-zero, so the loop never exits. It appends 0xFF to the output buffer forever, pinning a core at 100% and growing the buffer without bound.

How it was hit

A base compaction in a production cluster wedged on a table with many nullable text columns. Two BaseCompactionT threads sat in this stack for over a month:

#0  inline_memcpy (size=348057208)
#2  doris::faststring::GrowArray (newcapacity=502825728)
#4  doris::BitWriter::GetNextBytePtr (num_bytes=1)
#5  doris::BitWriter::PutAligned<unsigned char> (val=255 '\377')
#6  doris::BitWriter::PutVlqInt (v=-1)              bit_stream_utils.inline.h:91
#7  doris::RleEncoder<bool>::FlushRepeatedRun       rle_encoding.h:499
#9  doris::segment_v2::NullBitmapBuilder::finish
#11 doris::segment_v2::ScalarColumnWriter::finish
#15 doris::Merger::vertical_compact_one_group (is_key=false, max_rows_per_segment=1073741824)
#20 doris::CloudBaseCompaction::execute_compact

v=-1 together with val=255 pins it down exactly: the loop is emitting 0xFF with v stuck at -1.

Two existing behaviours combined to produce a 2^30-value run:

  • Vertical compaction derives the segment row limit from vertical_compaction_max_segment_size / avg_bytes_per_row (Compaction::get_avg_segment_rows()). For this table the average row size integer-divided to 0, so the divisor degenerated to 1 and the limit became the config default 1073741824 = 2^30 rows — visible as max_rows_per_segment=1073741824 in the stack above.
  • ScalarColumnWriter::append_nulls() never checks whether the page is full, unlike append_data(), and NULLs never reach the page builder. So an all-NULL column accumulated a single null-bitmap run spanning the whole 2^30-row segment in one page.

Because the stuck tasks kept the base compaction slots occupied (max_base_compaction_task_num_per_disk defaults to 2), _generate_cloud_compaction_tasks() computed base_n = 0 and stopped picking any tablet, so no base compaction ran on that backend again and compaction scores climbed to the cap across the instance.

What this PR changes

  1. PutVlqInt() takes uint32_t. A logical shift always converges to 0, so the loop terminates for every possible input. This is the backstop that makes a hang impossible regardless of what callers pass.

  2. repeat_count_ widened to int64_t, and long runs are split. Runs longer than MAX_VALUES_PER_REPEATED_RUN (2^30 - 1) are emitted as several back-to-back repeated runs of the same value. Readers already merge adjacent runs carrying the same value (RleDecoder::GetNextRun), so splitting is invisible to them. The cap keeps the indicator inside int32_t's positive range — exactly the range previous versions could encode — so output stays byte-identical for every run length that used to work, and no reader change is needed.

  3. faststring::reserve() grows geometrically via the existing GrowToAtLeast() instead of reallocating to exactly the requested capacity. BitWriter reserves a handful of bytes at a time, so exact growth reallocated and memcpy'd the entire buffer every 8 bytes, making an n-byte append cost O(n^2). This is what turned the infinite loop into a thread stuck in memcpy with a ~500MB buffer, and it slows down every other large RLE buffer as well. Measured: reaching 1 MiB now takes 26 reallocations instead of ~131,000.

Deliberately not in this PR, each worth its own change:

  • ScalarColumnWriter::append_nulls() still lets a page grow without bound.
  • Compaction::get_avg_segment_rows() still degenerates to the configured byte size when the average row size rounds down to zero.

Release note

Fix a BE hang in RLE encoding when a column produces a run of 2^30 or more identical values (for example an all-NULL column in a very large segment), which could permanently stall base compaction on that backend.

Check List (For Author)

  • Test
    • Unit Test

New tests:

Test Covers
TestRle.TestRepeatedRunExceedingIndicatorRange Run lengths around and far beyond 2^30 encode compactly and decode back to the original length
TestBitStreamUtil.TestPutVlqIntRoundTrip PutVlqInt round-trips every uint32_t, including values >= 2^31 that used to hang
FaststringTest.TestReserve_ExponentiallyExpand reserve() does not reallocate on every call

Verified that the new tests actually catch the bug: built the exact repro (RleEncoder<bool>::Put(true, 1 << 30) followed by Flush()) against unpatched master and it never returns (killed by timeout); with this patch it completes and emits 8 bytes. All pre-existing tests in rle_encoding_test, bit_stream_utils_test and faststring_test pass (29 tests, with LOOP_LESS_OR_MORE forced to the slow/thorough branch).

Also confirmed no format regression: a short run encoded via Put(v) in a loop and via Put(v, n) in one call still produce byte-identical output.

  • Behavior changed:

    • No. Encoded output is unchanged for every run length that previously encoded correctly; only run lengths that used to hang now produce (correct, readable) output.
  • Does this need documentation?

    • No.

RleEncoder::FlushRepeatedRun() wrote `repeat_count_ << 1` into an int32_t.
`repeat_count_` was an int, so a repeated run of 2^30 or more values made the
indicator overflow into a negative number. BitWriter::PutVlqInt() then took
that as an int32_t and shifted it right arithmetically:

    while ((v & 0xFFFFFF80) != 0L) {
        PutAligned<uint8_t>((v & 0x7F) | 0x80, 1);
        v >>= 7;
    }

An arithmetic shift of a negative value converges to -1 and stays there, and
-1 & 0xFFFFFF80 is non-zero, so the loop never exits. It appends 0xFF to the
output buffer forever, pinning a core at 100% and growing the buffer without
bound.

This was hit in production by a base compaction on a table with many nullable
columns. Vertical compaction derives the segment row limit from
`vertical_compaction_max_segment_size / avg_bytes_per_row`; for this table the
average row size integer-divided to 0, so the limit degenerated to the config
default of 1073741824 = 2^30 rows. ScalarColumnWriter::append_nulls() does not
check whether the page is full (unlike append_data(), and nulls never reach the
page builder), so an all-NULL column accumulated a single null-bitmap run of
2^30 rows in one page. Flushing that page wedged the compaction thread forever.
Because the base compaction slot stayed occupied, no base compaction was
scheduled on that backend again.

Three fixes:

1. Take `uint32_t` in PutVlqInt(). A logical shift always converges to 0, so
   the loop terminates for every input. This is the backstop that makes a hang
   impossible regardless of what callers pass.

2. Widen `repeat_count_` to int64_t and split runs longer than
   MAX_VALUES_PER_REPEATED_RUN (2^30 - 1) into several back-to-back repeated
   runs of the same value. Readers already merge adjacent runs carrying the
   same value (RleDecoder::GetNextRun), so splitting is invisible to them. The
   cap keeps the indicator inside int32_t's positive range, which is exactly
   the range previous versions could encode, so output stays byte-identical for
   every run length that used to work.

3. Make faststring::reserve() grow geometrically via GrowToAtLeast() instead of
   reallocating to exactly the requested capacity. BitWriter reserves a few
   bytes at a time, so exact growth reallocated and memcpy'd the whole buffer
   every 8 bytes, making an n-byte append cost O(n^2). This is what turned the
   infinite loop into a thread stuck in memcpy with a ~500MB buffer, and it
   slows down every other large RLE buffer too.

Not addressed here, worth separate changes: append_nulls() still lets a page
grow without bound, and get_avg_segment_rows() still degenerates to the
configured byte size when the average row size rounds down to zero.
@hello-stephen

Copy link
Copy Markdown
Contributor

Thank you for your contribution to Apache Doris.
Don't know what should be done next? See How to process your PR.

Please clearly describe your PR:

  1. What problem was fixed (it's best to include specific error reporting information). How it was fixed.
  2. Which behaviors were modified. What was the previous behavior, what is it now, why was it modified, and what possible impacts might there be.
  3. What features were added. Why was this function added?
  4. Which code was refactored and why was this part of the code refactored?
  5. Which functions were optimized and what is the difference before and after the optimization?

@liaoxin01

Copy link
Copy Markdown
Contributor Author

/review

@liaoxin01

Copy link
Copy Markdown
Contributor Author

run buildall

@github-actions github-actions Bot left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

Reviewed all seven changed files at 7bbe72075926a5d7d3cece71c59576fbe9cf5d1f, including upstream storage writers, downstream readers, shared buffer callers, and tests. No actionable defect was found. No existing inline findings require carrying forward. No additional user focus was supplied.

The review converged in 1 round: the complete-review agent and both independent risk reviewers returned NO_NEW_VALUABLE_FINDINGS; the main review verified their evidence and completed the final sweep. There are no unresolved candidates or uncovered changed files.

The triggering flow was traced through ScalarColumnWriter::append_nulls -> NullBitmapBuilder -> RleEncoder::Put/Flush -> BitWriter -> faststring -> OwnedSlice, then page readers using RleDecoder. The two risk questions were resolved: bounded adjacent repeated runs preserve the existing reader grammar, and geometric reserve reuses the existing tracked allocation/ownership/ASAN path without a demonstrated caller regression.

Critical checkpoint conclusions:

  1. Goal and evidence: unsigned VLQ shifting terminates within five bytes; widened counts and runs capped at 2^30-1 address the reported hang. Added boundary tests target this mechanism; their execution was not independently verified.
  2. Scope and reuse: changes are focused on encoding overflow, incremental buffer growth, and their tests; reserve reuses GrowToAtLeast.
  3. Concurrency: no new threads, shared state, locks, or lock-order changes. Encoder and buffer state remain caller-owned.
  4. Lifecycle: Flush/Clear/build/reset/destruction preserve ownership. The new constexpr constant introduces no dynamic or cross-translation-unit initialization.
  5. Configuration: no configuration changes.
  6. Compatibility: previously valid repeated runs retain their bytes. Larger runs use existing adjacent-run syntax with indicators <=0x7FFFFFFE; inspected scalar and batch readers accept these. The changed inline signature and encoder layout are internal.
  7. Thrift/protobuf: no field or enum changes.
  8. Parallel paths: inspected bulk and single-value writes, nullable and scalar RLE pages, Get/GetNextRun/Skip/RewindOne/get_values, batch readers, and page seek/read paths; no parallel fix was missing.
  9. Conditions and errors: the split loop has a concrete overflow rationale and makes bounded progress. Existing error propagation and state assertions are unchanged.
  10. Test coverage: new tests cover large runs around the cap and above INT32_MAX, VLQ boundaries through UINT32_MAX, and geometric reserve. Existing tests cover mixed/literal transitions, zero-length writes, bit widths, and bulk/incremental equivalence. Huge false/multibyte runs and partial/skip/rewind/mixed-tail combinations are not newly tested; static inspection found no failure in those paths. No end-to-end test was added.
  11. Test results: no golden files changed. New expectations are consistent by inspection; author-reported test results are not execution evidence from this review.
  12. Observability: no new distributed or asynchronous workflow needs additional logging or metrics.
  13. Transactions and persistence: no EditLog, version visibility, delete bitmap, commit, replay, or failover protocol changes. Stored RLE compatibility was checked separately above.
  14. Data writes and atomicity: page finish/publication and crash/error handling are unchanged; split counts preserve values without adding a publication path.
  15. FE/BE variables: no transmitted variables or send sites changed.
  16. Performance and memory: splitting costs O(number of capped runs), with only a few runs for uint32-limited segments. Geometric reserve removes quadratic copying; actual capacity stays tracked and is carried into OwnedSlice for freeing. Additional retained capacity is the intended growth tradeoff.
  17. Other BE obligations: no new dependency, libc API, PCH entry, explicit instantiation, or test inclusion of source .cpp files. The pure-text build-support/check-build-hygiene.sh check passed all header, pairing, and unity-skip gates.

Validation was static: no Doris build, unit/regression test, sanitizer run, released-binary compatibility run, or empirical benchmark was executed, and no source file was modified. These are validation limits; all assigned code-review scope and risk dispositions are complete.

Review converged after 1 round(s).

@hello-stephen

Copy link
Copy Markdown
Contributor
TPC-H: Total hot run time: 29600 ms
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit 7bbe72075926a5d7d3cece71c59576fbe9cf5d1f, data reload: false

------ Round 1 ----------------------------------
============================================
q1	17625	5602	5552	5552
q2	2132	329	251	251
q3	10204	1396	844	844
q4	4677	481	346	346
q5	7434	814	535	535
q6	194	195	162	162
q7	787	815	623	623
q8	9288	1399	1071	1071
q9	5521	4298	4302	4298
q10	6814	1306	1023	1023
q11	442	258	236	236
q12	643	418	288	288
q13	18070	3541	3012	3012
q14	275	269	256	256
q15	q16	739	725	695	695
q17	1203	751	570	570
q18	7215	6243	6157	6157
q19	1101	963	622	622
q20	388	345	223	223
q21	5125	2541	2628	2541
q22	419	356	295	295
Total cold run time: 100296 ms
Total hot run time: 29600 ms

----- Round 2, with runtime_filter_mode=off -----
============================================
q1	6480	6480	6478	6478
q2	755	598	585	585
q3	5520	5724	5224	5224
q4	2334	2164	1593	1593
q5	5842	5750	5675	5675
q6	263	213	155	155
q7	2370	1967	1931	1931
q8	3167	2827	2835	2827
q9	8163	7943	7599	7599
q10	3651	3613	3269	3269
q11	603	427	381	381
q12	667	698	512	512
q13	3292	3682	3056	3056
q14	288	284	270	270
q15	q16	679	693	627	627
q17	7930	6992	6883	6883
q18	13243	12227	13154	12227
q19	932	805	804	804
q20	2204	2179	1952	1952
q21	5926	4716	4841	4716
q22	520	462	449	449
Total cold run time: 74829 ms
Total hot run time: 67213 ms

@hello-stephen

Copy link
Copy Markdown
Contributor
TPC-DS: Total hot run time: 152213 ms
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit 7bbe72075926a5d7d3cece71c59576fbe9cf5d1f, data reload: false

query5	4313	568	463	463
query6	431	209	200	200
query7	4824	448	230	230
query8	325	171	158	158
query9	8741	3960	3919	3919
query10	453	315	285	285
query11	5968	3804	3518	3518
query12	146	91	88	88
query13	1255	454	313	313
query14	6077	4051	3758	3758
query14_1	3562	3516	3523	3516
query15	215	205	178	178
query16	949	457	437	437
query17	871	663	538	538
query18	2408	428	316	316
query19	202	168	140	140
query20	87	88	85	85
query21	215	142	115	115
query22	13131	13091	12839	12839
query23	13586	12976	12382	12382
query23_1	12677	12567	12624	12567
query24	7110	855	471	471
query24_1	474	481	489	481
query25	547	431	362	362
query26	1299	260	143	143
query27	2759	446	279	279
query28	4591	1981	1966	1966
query29	1568	619	486	486
query30	302	215	182	182
query31	1001	926	794	794
query32	142	89	88	88
query33	525	297	232	232
query34	887	854	498	498
query35	759	761	624	624
query36	872	804	719	719
query37	127	99	88	88
query38	1790	1766	1688	1688
query39	801	815	746	746
query39_1	740	728	748	728
query40	212	114	99	99
query41	67	64	63	63
query42	86	84	81	81
query43	370	382	330	330
query44	1302	690	698	690
query45	184	177	162	162
query46	867	964	559	559
query47	2947	2964	2954	2954
query48	301	300	220	220
query49	562	404	283	283
query50	672	276	212	212
query51	10753	10547	10472	10472
query52	79	83	70	70
query53	184	206	149	149
query54	262	216	196	196
query55	68	62	62	62
query56	219	226	203	203
query57	1602	1593	1558	1558
query58	279	260	240	240
query59	2139	2144	1959	1959
query60	288	274	233	233
query61	154	148	147	147
query62	391	341	287	287
query63	212	161	168	161
query64	2732	931	776	776
query65	3298	3224	3243	3224
query66	1770	411	296	296
query67	20201	20284	19928	19928
query68	2923	1011	613	613
query69	382	292	248	248
query70	849	785	789	785
query71	284	231	208	208
query72	2776	2612	2303	2303
query73	514	566	294	294
query74	4599	4473	4315	4315
query75	2342	2307	1945	1945
query76	2295	1018	609	609
query77	345	375	282	282
query78	9664	9631	9127	9127
query79	968	841	522	522
query80	536	435	332	332
query81	523	318	271	271
query82	576	136	112	112
query83	295	194	190	190
query84	303	126	102	102
query85	820	448	371	371
query86	319	237	230	230
query87	2031	1966	1853	1853
query88	3631	2726	2706	2706
query89	342	298	254	254
query90	1893	192	176	176
query91	161	144	122	122
query92	89	90	87	87
query93	1015	980	585	585
query94	441	328	287	287
query95	582	428	336	336
query96	680	526	229	229
query97	2488	2444	2356	2356
query98	162	153	151	151
query99	783	763	655	655
Total cold run time: 234343 ms
Total hot run time: 152213 ms

@hello-stephen

Copy link
Copy Markdown
Contributor
ClickBench: Total hot run time: 24.65 s
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/clickbench-tools
ClickBench test result on commit 7bbe72075926a5d7d3cece71c59576fbe9cf5d1f, data reload: false

query1	0.00	0.00	0.00
query2	0.10	0.05	0.06
query3	0.27	0.12	0.12
query4	1.61	0.12	0.12
query5	0.24	0.22	0.24
query6	1.17	0.69	0.69
query7	0.04	0.01	0.00
query8	0.05	0.04	0.04
query9	0.41	0.35	0.34
query10	0.57	0.56	0.55
query11	0.22	0.14	0.14
query12	0.18	0.15	0.14
query13	0.48	0.49	0.50
query14	1.03	1.02	1.00
query15	0.64	0.62	0.62
query16	0.35	0.35	0.35
query17	1.09	1.15	1.11
query18	0.23	0.22	0.22
query19	2.06	2.01	1.94
query20	0.02	0.02	0.01
query21	15.49	0.24	0.15
query22	4.52	0.06	0.05
query23	16.27	0.32	0.12
query24	2.96	0.59	0.53
query25	0.13	0.06	0.04
query26	1.60	0.27	0.15
query27	0.04	0.03	0.05
query28	2.17	0.61	0.41
query29	12.47	4.23	3.31
query30	0.29	0.15	0.14
query31	2.77	0.58	0.34
query32	3.23	0.61	0.52
query33	3.25	3.17	3.18
query34	15.55	4.02	3.40
query35	3.33	3.34	3.38
query36	0.55	0.43	0.43
query37	0.10	0.07	0.07
query38	0.05	0.04	0.04
query39	0.04	0.03	0.03
query40	0.19	0.15	0.14
query41	0.08	0.03	0.03
query42	0.04	0.03	0.03
query43	0.04	0.04	0.03
Total cold run time: 95.92 s
Total hot run time: 24.65 s

@hello-stephen

Copy link
Copy Markdown
Contributor

BE UT Coverage Report

Increment line coverage 100.00% (13/13) 🎉

Increment coverage report
Complete coverage report

Category Coverage
Function Coverage 66.16% (31590/47751)
Line Coverage 50.97% (333545/654386)
Region Coverage 46.27% (269415/582292)
Branch Coverage 47.91% (126429/263889)

@hello-stephen

Copy link
Copy Markdown
Contributor

BE Regression && UT Coverage Report

Increment line coverage 100.00% (13/13) 🎉

Increment coverage report
Complete coverage report

Category Coverage
Function Coverage 77.00% (35591/46223)
Line Coverage 62.30% (403117/647015)
Region Coverage 58.63% (339984/579843)
Branch Coverage 59.58% (156733/263060)

@gavinchou
gavinchou merged commit 76bd6f0 into apache:master Oct 16, 2026
40 checks passed
@github-actions

Copy link
Copy Markdown
Contributor

PR approved by anyone and no changes requested.

@github-actions github-actions Bot added the approved Indicates a PR has been approved by one committer. label Oct 16, 2026
@github-actions

Copy link
Copy Markdown
Contributor

PR approved by at least one committer and no changes requested.

github-actions Bot pushed a commit that referenced this pull request Oct 16, 2026
…69100)

### What problem does this PR solve?

Problem Summary:

`RleEncoder::FlushRepeatedRun()` wrote `repeat_count_ << 1` into an
`int32_t`. `repeat_count_` was an `int`, so a repeated run of 2^30 or
more values overflowed the indicator into a negative number.
`BitWriter::PutVlqInt()` then took that as an `int32_t` and shifted it
right arithmetically:

```cpp
inline void BitWriter::PutVlqInt(int32_t v) {
    while ((v & 0xFFFFFF80) != 0L) {
        PutAligned<uint8_t>((v & 0x7F) | 0x80, 1);
        v >>= 7;
    }
    PutAligned<uint8_t>(v & 0x7F, 1);
}
```

An arithmetic right shift of a negative value converges to `-1` and
stays there, and `-1 & 0xFFFFFF80` is non-zero, so **the loop never
exits**. It appends `0xFF` to the output buffer forever, pinning a core
at 100% and growing the buffer without bound.

#### How it was hit

A base compaction in a production cluster wedged on a table with many
nullable `text` columns. Two `BaseCompactionT` threads sat in this stack
for over a month:

```
#0  inline_memcpy (size=348057208)
#2  doris::faststring::GrowArray (newcapacity=502825728)
#4  doris::BitWriter::GetNextBytePtr (num_bytes=1)
#5  doris::BitWriter::PutAligned<unsigned char> (val=255 '\377')
#6  doris::BitWriter::PutVlqInt (v=-1)              bit_stream_utils.inline.h:91
#7  doris::RleEncoder<bool>::FlushRepeatedRun       rle_encoding.h:499
#9  doris::segment_v2::NullBitmapBuilder::finish
#11 doris::segment_v2::ScalarColumnWriter::finish
#15 doris::Merger::vertical_compact_one_group (is_key=false, max_rows_per_segment=1073741824)
#20 doris::CloudBaseCompaction::execute_compact
```

`v=-1` together with `val=255` pins it down exactly: the loop is
emitting `0xFF` with `v` stuck at `-1`.

Two existing behaviours combined to produce a 2^30-value run:

- Vertical compaction derives the segment row limit from
`vertical_compaction_max_segment_size / avg_bytes_per_row`
([`Compaction::get_avg_segment_rows()`](https://github.com/apache/doris/blob/master/be/src/olap/compaction.cpp)).
For this table the average row size integer-divided to `0`, so the
divisor degenerated to `1` and the limit became the config default
`1073741824` = 2^30 rows — visible as `max_rows_per_segment=1073741824`
in the stack above.
- `ScalarColumnWriter::append_nulls()` never checks whether the page is
full, unlike `append_data()`, and NULLs never reach the page builder. So
an all-NULL column accumulated a single null-bitmap run spanning the
whole 2^30-row segment in one page.

Because the stuck tasks kept the base compaction slots occupied
(`max_base_compaction_task_num_per_disk` defaults to 2),
`_generate_cloud_compaction_tasks()` computed `base_n = 0` and stopped
picking any tablet, so **no base compaction ran on that backend again**
and compaction scores climbed to the cap across the instance.

### What this PR changes

1. **`PutVlqInt()` takes `uint32_t`.** A logical shift always converges
to 0, so the loop terminates for every possible input. This is the
backstop that makes a hang impossible regardless of what callers pass.

2. **`repeat_count_` widened to `int64_t`, and long runs are split.**
Runs longer than `MAX_VALUES_PER_REPEATED_RUN` (2^30 - 1) are emitted as
several back-to-back repeated runs of the same value. Readers already
merge adjacent runs carrying the same value (`RleDecoder::GetNextRun`),
so splitting is invisible to them. The cap keeps the indicator inside
`int32_t`'s positive range — exactly the range previous versions could
encode — so **output stays byte-identical for every run length that used
to work**, and no reader change is needed.

3. **`faststring::reserve()` grows geometrically** via the existing
`GrowToAtLeast()` instead of reallocating to exactly the requested
capacity. `BitWriter` reserves a handful of bytes at a time, so exact
growth reallocated and memcpy'd the entire buffer every 8 bytes, making
an n-byte append cost O(n^2). This is what turned the infinite loop into
a thread stuck in `memcpy` with a ~500MB buffer, and it slows down every
other large RLE buffer as well. Measured: reaching 1 MiB now takes 26
reallocations instead of ~131,000.

Deliberately **not** in this PR, each worth its own change:
- `ScalarColumnWriter::append_nulls()` still lets a page grow without
bound.
- `Compaction::get_avg_segment_rows()` still degenerates to the
configured byte size when the average row size rounds down to zero.

### Release note

Fix a BE hang in RLE encoding when a column produces a run of 2^30 or
more identical values (for example an all-NULL column in a very large
segment), which could permanently stall base compaction on that backend.

### Check List (For Author)

- Test
    - [x] Unit Test

New tests:

| Test | Covers |
|---|---|
| `TestRle.TestRepeatedRunExceedingIndicatorRange` | Run lengths around
and far beyond 2^30 encode compactly and decode back to the original
length |
| `TestBitStreamUtil.TestPutVlqIntRoundTrip` | `PutVlqInt` round-trips
every `uint32_t`, including values `>= 2^31` that used to hang |
| `FaststringTest.TestReserve_ExponentiallyExpand` | `reserve()` does
not reallocate on every call |

Verified that the new tests actually catch the bug: built the exact
repro (`RleEncoder<bool>::Put(true, 1 << 30)` followed by `Flush()`)
against unpatched master and it never returns (killed by timeout); with
this patch it completes and emits 8 bytes. All pre-existing tests in
`rle_encoding_test`, `bit_stream_utils_test` and `faststring_test` pass
(29 tests, with `LOOP_LESS_OR_MORE` forced to the slow/thorough branch).

Also confirmed no format regression: a short run encoded via `Put(v)` in
a loop and via `Put(v, n)` in one call still produce byte-identical
output.

- Behavior changed:
- [x] No. Encoded output is unchanged for every run length that
previously encoded correctly; only run lengths that used to hang now
produce (correct, readable) output.

- Does this need documentation?
    - [x] No.

Co-authored-by: Xin Liao <[email protected]>
yiguolei pushed a commit that referenced this pull request Oct 16, 2026
…2^30 values #69100 (#69193)

Cherry-picked from #69100

Co-authored-by: Xin Liao <[email protected]>
Co-authored-by: Xin Liao <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

approved Indicates a PR has been approved by one committer. dev/4.2.0-merged reviewed

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants