hailcpy opened a new pull request, #69059:
URL: https://github.com/apache/doris/pull/69059
### What problem does this PR solve?
Issue Number: None
Related PR: None
Problem Summary:
`json_search()` takes quadratic time on JSON arrays. A real 2 MB document
with 17 arrays of 18,272 strings each takes 18.5 s to search a single row.
Reproduce on 4.1.4.1. Objects of the same size stay flat:
```sql
select json_search(
cast(concat('["', group_concat(cast(number as string), '","'), '"]') as
json),
'one', '%zzq%')
from numbers('number'='40000');
```
| array elements | time |
|---:|---:|
| 5,000 | 0.13 s |
| 10,000 | 0.35 s |
| 20,000 | 1.33 s |
| 40,000 | 5.24 s |
| object, 40,000 members | 0.02 s |
Root cause: `FunctionJsonSearch::find_matches` walks arrays by index:
```cpp
for (int i = 0; i < array->numElem(); ++i) {
...
const auto* child_element = array->get(i);
```
JSONB arrays are packed with variable-length values and no offset table, so
`ArrayVal::numElem()` and `ArrayVal::get(idx)` each scan the payload from the
start. Both run on every iteration, which makes each array O(n²). Objects
already use `ObjectVal`'s forward iterator and stay linear.
Fix: iterate arrays with `ArrayVal::begin()/end()`, the forward iterator the
JSONB format already provides, and keep a running index for the `$[i]` path
leg. The same index loop appears in two other places, and this PR fixes them
too:
- `write_json_value` in `function_jsonb.cpp` (`json_insert` / `json_replace`
/ `json_set`)
- `jsonb_detail::array_contains_value` / `array_contains_array` in
`jsonb_document.h` (`json_contains`). These already hoist `numElem()`, but
`get(i)` is still O(i).
Elements are visited in the same order and get the same indices, so results
do not change. The loops stop at `it < end()` rather than `it != end()`, so a
malformed element length cannot walk past the array payload. This keeps the
`pch < fence` bound that `numElem()`/`get()` used.
### Release note
Improve performance of `json_search`, `json_contains`, `json_insert`,
`json_replace` and `json_set` on large JSON arrays; array traversal is now
linear instead of quadratic.
### Check List (For Author)
- Test <!-- At least one of them must be included. -->
- [ ] Regression test
- [ ] Unit Test
- [ ] Manual test (add detailed scripts or steps below)
- [x] No need to test or manual test. Explain why:
- [ ] This is a refactor/code format and no logic has been changed.
- [x] Previous test can cover this change.
- [ ] No code files have been changed.
- [ ] Other reason <!-- Add your reason? -->
Array paths and results are already covered by
`query_p0/sql_functions/json_functions/json_search.groovy` (nested arrays such
as `$[1][0].B`), `test_json_function.groovy`,
`test_json_contains_numeric_equality.groovy` and the `json_contains` cases in
`be/test/exprs/function/function_jsonb_test.cpp`. I did not build this patch
locally; I'd appreciate a `run buildall`. The timings above come from an
unpatched 4.1.4.1 cluster.
- Behavior changed:
- [x] No.
- [ ] Yes. <!-- Explain the behavior change -->
- Does this need documentation?
- [x] No.
- [ ] Yes. <!-- Add document PR link here. eg:
https://github.com/apache/doris-website/pull/1214 -->
### Check List (For Reviewer who merge this PR)
- [ ] Confirm the release note
- [ ] Confirm test cases
- [ ] Confirm document
- [ ] Add branch pick label <!-- Add branch pick label that this PR should
merge into -->
🤖 Generated with [Claude Code](https://claude.com/claude-code)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
