如何用Linq优化跨两表区间匹配查询的性能？

现有两张数据表，需求是从departmentValues表中筛选出所有落在relation_values表任意区间内的值：

• departmentValues表：存储单个部门值，最多可包含1000条数据（实际场景已达4000条），示例数据：

DepartmentValues
---------------
1
2
3
...

• relation_values表：存储部门区间，包含deptfrom（起始部门）和deptto（结束部门）字段，示例数据：

relation_values
---------------
deptfrom | deptto
-----------------
1        | 2
3        | 45
34       | 67
...

当前采用双层嵌套循环实现，代码如下：

foreach (var item in DepartmentValues)
{
    foreach(var relval in relationValues)
    {
        int chkDeptFrom = string.Compare(item, relval.relation_value_from); ;
        int chkDeptTo = string.Compare(item, relval.relation_value_to);

        if (chkDeptFrom >= 0 && chkDeptTo <= 0)
        {
            values.Add(item);
        }
    }
}

该实现的时间复杂度为O(M*N)（M为departmentValues数据量，N为relation_values数据量），当M达到4000时，重复比较次数剧增，导致性能显著下降。

方案1：替换字符串比较为数值比较 #

部门值为数字格式，字符串比较的开销远高于数值比较。先将所有值转换为int类型后再做区间判断：

// 预先转换区间为数值类型
var numericRanges = relationValues.Select(r => new 
{
    From = int.Parse(r.relation_value_from),
    To = int.Parse(r.relation_value_to)
}).ToList();

// 转换部门值并筛选
var values = DepartmentValues
    .Select(int.Parse)
    .Where(dept => numericRanges.Any(range => dept >= range.From && dept <= range.To))
    .Select(dept => dept.ToString())
    .ToList();

优势：数值比较速度比字符串提升数倍，同时用LINQ简化代码结构，可读性更好。

方案2：排序区间+二分查找，将复杂度降至O(M*logN) #

若relation_values的区间数量较多，先对区间按From升序排序，再用二分查找快速定位可能匹配的区间，减少无效比较：

// 转换并排序区间
var sortedRanges = relationValues
    .Select(r => new { From = int.Parse(r.relation_value_from), To = int.Parse(r.relation_value_to) })
    .OrderBy(r => r.From)
    .ToList();

var values = new List<string>();
foreach (var item in DepartmentValues)
{
    int dept = int.Parse(item);
    int left = 0, right = sortedRanges.Count - 1;
    bool isMatch = false;
    
    while (left <= right)
    {
        int mid = (left + right) / 2;
        var range = sortedRanges[mid];
        
        if (range.From > dept)
        {
            right = mid - 1;
        }
        else
        {
            if (dept <= range.To)
            {
                isMatch = true;
                break;
            }
            left = mid + 1;
        }
    }
    
    if (isMatch)
    {
        values.Add(item);
    }
}

优势：二分查找的logN远小于线性遍历的N，区间数量越大，性能提升越明显。

方案3：合并重叠/连续区间，减少区间总数 #

如果relation_values存在大量重叠或连续区间，先合并这些区间，进一步降低比较次数：

// 转换、排序并合并区间
var sortedRanges = relationValues
    .Select(r => new { From = int.Parse(r.relation_value_from), To = int.Parse(r.relation_value_to) })
    .OrderBy(r => r.From)
    .ToList();

var mergedRanges = new List<(int From, int To)>();
foreach (var range in sortedRanges)
{
    if (mergedRanges.Count == 0)
    {
        mergedRanges.Add((range.From, range.To));
        continue;
    }
    
    var last = mergedRanges.Last();
    if (range.From <= last.To + 1) // 重叠或连续则合并
    {
        mergedRanges.RemoveAt(mergedRanges.Count - 1);
        mergedRanges.Add((last.From, Math.Max(last.To, range.To)));
    }
    else
    {
        mergedRanges.Add((range.From, range.To));
    }
}

// 筛选部门值
var values = DepartmentValues
    .Select(int.Parse)
    .Where(dept => mergedRanges.Any(r => dept >= r.From && dept <= r.To))
    .Select(dept => dept.ToString())
    .ToList();

优势：合并后区间数量大幅减少，后续无论是线性遍历还是二分查找的效率都会进一步提升。

方案4：数据库层面直接筛选（若数据存储在数据库） #

如果两张表的数据来自数据库，直接用SQL语句让数据库引擎处理查询是最优方案，数据库会自动利用索引优化：

SELECT dv.DepartmentValues
FROM departmentValues dv
WHERE EXISTS (
    SELECT 1 
    FROM relation_values rv
    WHERE dv.DepartmentValues BETWEEN rv.deptfrom AND rv.deptto
)

优势：数据库查询优化器会自动处理区间匹配，比内存中处理效率高得多，尤其适合大数据量场景。

内容的提问来源于stack exchange，提问作者ann mary