时间戳

首页 > 解决方案 > 有效的哈希或代表一组记录的东西

sql - 有效的哈希或代表一组记录的东西

问题描述

想象一下 SQL Server 中具有以下列的表（这是一种简化）：

ID: int
Dimension1: int
Dimension2: int
Dimension3: string
Dimension4: string
...
Dimension30: string

表可以变得很大（数百万条记录）。我们经常做这样的查询：

select ID from Table where Dimension1 = 1 and Dimension2 = 2

SQL Server 很容易迷失在这样的标准中并选择错误的查询计划 => 性能问题。

我想知道是否有一些智能哈希函数或类似的东西可以像这样有效地在表中搜索？也就是说，当我们想要查找所有带有Dimension1和Dimension2标准的记录时，我们过滤一些单一的并且能够理解要返回的记录。

标签： sqlsql-serveralgorithmdata-structureshash

解决方案

如果你真的经常这样做并且你有一些内存可用并且你能够捕捉到对 dim1 和 dim2 的所有更改，那么你可以在外部进行。

完全未经测试的代码 C++ 代码

using DimType = int;
using DimVec = std::vector<DimType>;
DimVec dim1, dim2; // prefilled and sorted
using intVit = DimVec ::const_iterator; 

// in case we don´t have std::span
using spanV = std::pair<intVit, intVit>; 

spanV FindValue(const DimType& vec, DimType value) {
  // is_sorted(vec)
  return {std::lower_bound(vec.begin(), vec.end(), value),
          std::upper_bound(vec.begin(), vec.end(), value) };
}

DimVec Intersection(spanV set1, spanV set2) {
  // is_sorted(set1) && is_sorted(set2)
  DimVec res;
  res.resize(std::min(set1.size()), set2.size());
  auto last=std::set_intersection (set1.first, set1.second, set2.first, set2.second, res.begin());

  v.resize(last-res.begin()); 

  return res;
}

DimVec Intersection(const DimVec& set1, DimVec& set2, DimType value1, DimType value2) {
  return Intersection(FindValue(set1, value1), FindValue(set2, value2));
}

添加模板以进行概括。

FindValue 是 O(lg N)，set_intersection 是 O(N)。

推荐阅读