Doris json_search was quadratic on arrays. I sent the fix upstream.

At work we search JSON columns in Apache Doris. One query had a single row that took 18.5 seconds. The document was about 2 MB: 17 arrays, each with 18,272 strings.

2 MB is not big. Something was doing far more work than the document size explained.

Reproducing it without our data

I did not want to debug on customer rows, so I made a synthetic one. An array of N strings, searched for a pattern that never matches, so the whole array gets walked:

select json_search(
  cast(concat('["', group_concat(cast(number as string), '","'), '"]') as json),
  'one', '%zzq%')
from numbers('number'='40000');

Run on stock 4.1.4.1:

Double the input, roughly quadruple the time. And the same number of members in an object stays flat at 0.02 s. So it was not JSON parsing, and it was not the pattern match. It was arrays specifically.

Why arrays and not objects

json_search walks the document recursively. For arrays, the loop looked like this:

for (int i = 0; i < array->numElem(); ++i) {
    ...
    const auto* child_element = array->get(i);

That reads fine. The problem is how Doris stores JSON. JSONB packs array elements back to back, each with its own length, and there is no offset table. To find element 5,000 you have to start at element 0 and hop forward 5,000 times.

Both calls in that loop do exactly that:

• numElem() walks the whole payload to count elements.
• get(i) walks i elements to find the one you asked for.

Both run on every iteration. One pass over the array becomes n walks of length n. Objects already used a forward iterator, which is why they were fine.

The fix

JSONB already has the right primitive: ArrayVal::begin() and end(), a forward iterator that hops from one element to the next using the stored length. I used it, and kept a separate running counter for the one place that needs a position, the $[i] leg of the path that json_search returns:

int index = 0;
for (auto it = array->begin(); it < array->end(); ++it, ++index) {
    auto leg = std::make_unique<leg_info>(nullptr, 0, index, ARRAY_CODE);
    cur_path->add_leg_to_leg_vector(std::move(leg));
    find |= find_matches(&*it, one_match, state, cur_path, matches);

The iterator is for moving. The counter is for naming. Elements are visited in the same order and get the same indices as before, so results are identical. Only the cost changed.

< instead of !=

My C++ habit for iterator loops is it != end. I used it < end() here on purpose. The old loop was bounded by a pointer check against the end of the payload. If an element's stored length were ever corrupt, != can step past the end and never match. < stops. The data is validated before it gets here, so this is belt and braces, but it keeps the old bound instead of quietly removing it.

The same bug was in two more places

Once I knew what to look for, I grepped for the pattern. It was in:

• write_json_value, behind json_insert, json_replace and json_set.
• array_contains_value and array_contains_array, behind json_contains. These already hoisted numElem() out of the loop, so they looked fine. get(i) inside was still O(i).

Fixing only the function from the bug report would have left the other four with the same cliff. The PR changes all of them, with the same iterator pattern.

Landing it

I opened it against apache/doris from a fork. The contribution flow has a few project-specific steps: a title format of [type](module) summary, the repo's PR template, and a committer has to approve the CI workflow before run buildall will trigger the real test pipeline. It went through review and was merged: apache/doris#69059.

Existing coverage already exercised these paths: array path cases in json_search.groovy, test_json_function.groovy, test_json_contains_numeric_equality.groovy, and the json_contains cases in the BE unit tests. Since results do not change, I did not add new tests.

What I take from it

When a function is slow on large inputs and fast on equally large inputs of a different shape, the shape is the bug. Compare the fast path and the slow path of the same operation, and look at what each one asks the container to do.

And when you find a pattern, grep for it before you open the PR.