# UNDF: UNDF-2026-000000447
# kylin-0001: JdbcJobScheduler — List<String>.contains in stream filter → O(J²)

## Classification
- **Severity**: MEDIUM
- **CWE**: CWE-407 (Algorithmic Complexity — Inefficient Algorithmic Complexity)
- **Component**: `src/core-job/src/main/java/org/apache/kylin/job/scheduler/JdbcJobScheduler.java`
- **Method**: `releaseJobLock()` (internal scheduler loop)

## Defect

In `releaseJobLock()` (approximate method name from context around line 410–432):

```java
List<String> jobInfoIds = jobs.stream()
        .map(JobInfo::getJobId)
        .collect(Collectors.toList());                                 // <-- ArrayList

List<String> toRemoveLocks = Lists.newArrayList(jobIds).stream()
        .filter(jobId -> !jobInfoIds.contains(jobId))                  // <-- O(J) List.contains
        .collect(Collectors.toList());
```

`jobInfoIds` is collected into an `ArrayList<String>`. The stream filter calls
`jobInfoIds.contains(jobId)` once per element of `jobIds`. Both lists grow with the number of
in-flight jobs. Total: **O(J²)** where J = number of job IDs.

This scheduler loop runs on a recurring timer. Under high-throughput build workloads (large Kylin
clusters doing continuous incremental cube builds), J can grow into the hundreds per batch, causing
quadratic behavior in the scheduler hot path.

## Root Cause

`Collectors.toList()` produces an `ArrayList`. The calling code immediately uses it for membership
tests only. No `Set` conversion was applied.

## Fix

Collect into a `HashSet` (or convert before use):

```java
// Before:
List<String> jobInfoIds = jobs.stream()
        .map(JobInfo::getJobId)
        .collect(Collectors.toList());

// After:
Set<String> jobInfoIds = jobs.stream()
        .map(JobInfo::getJobId)
        .collect(Collectors.toCollection(HashSet::new));
```

## Complexity

| Before | After |
|--------|-------|
| O(J²) per scheduler tick | O(J) per scheduler tick |

With J=200 jobs per batch: Before = 40 000 comparisons. After = 200. **200× reduction**.

## Patch

```diff
--- a/src/core-job/src/main/java/org/apache/kylin/job/scheduler/JdbcJobScheduler.java
+++ b/src/core-job/src/main/java/org/apache/kylin/job/scheduler/JdbcJobScheduler.java
@@ -415,7 +415,8 @@ public class JdbcJobScheduler {
         filter.setJobIds(jobIds);
         List<JobInfo> jobs = jobContext.getJobInfoMapper().selectByJobFilter(filter);
-        List<String> jobInfoIds = jobs.stream().map(JobInfo::getJobId).collect(Collectors.toList());
+        // Use HashSet for O(1) membership test in stream filter below
+        Set<String> jobInfoIds = jobs.stream().map(JobInfo::getJobId)
+                .collect(Collectors.toCollection(HashSet::new));
         List<String> toRemoveLocks = Lists.newArrayList(jobIds).stream()
                 .filter(jobId -> !jobInfoIds.contains(jobId))
                 .collect(Collectors.toList());
```
