C#에서 거대한 목록을 필터링하는 가장 좋은 방법은 무엇입니까?

Question

우리는 Entity Framework를 통해 SQL Server DB에 연결되는 ASP.NET MVC 웹 응용 프로그램을 보유하고 있습니다. 이 응용 프로그램의 주요 작업 중 하나는 사용자가 아카이브 값을 보유하고있는 거대한 데이터베이스 테이블을 빠르게 검색하고 필터링 할 수 있도록 허용하는 것입니다.

테이블 구조는 매우 간단합니다 : Timestamp (DateTime), StationId (int), DatapointId (int), Value (double). 이 테이블은 10 억에서 1 억 개의 행을 포함합니다. DB 테이블을 커버 인덱스 등으로 최적화했지만, DatapointId, StationId, Time, Skipping으로 필터링 할 때 사용자 경험이 상당히 뒤떨어져 페이지에 표시하고 싶은 부분 만 가져 왔습니다.

우리는 서버에 많은 RAM이 있기 때문에 웹 응용 프로그램이 시작될 때 전체 보관 테이블을 List<ArchiveRow>에로드 한 다음이 목록에서 데이터를 가져올 수 있다고 생각했습니다. 데이터베이스로 왕복하는 대신에 이것은 매우 효과적입니다. 전체 아카이브 테이블 (현재 약 1 천만 항목)을 목록에로드하는 데 약 9 초가 걸립니다.

public class ArchiveResponse { 
    public int Length { get; set; } 
    public int numShown { get; set; } 
    public int numFound { get; set; } 
    public int numTotal { get; set; } 
    public List<ArchiveRow> Rows { get; set; } 
} 

따라 : 나는 지금 LINQ 쿼리와 함께 목록에서 원하는 데이터를 얻을 때

public class ArchiveRow { 
    public int s { get; set; } 
    public int d { get; set; } 
    public DateTime t { get; set; } 
    public double v { get; set; } 
}  

, 그것은 이미 빠르게입니다 ArchiveRow은 다음과 같습니다 간단한 객체이다 DB를 쿼리하지만 여러 기준으로 필터링 할 때 여전히 매우 느립니다. 예를 들어 하나의 StationId와 12 DatapointIds로 필터링하면 25 행의 창을 검색하는 데 약 5 초가 걸립니다. 나는 이미 Where으로 필터링을 조인 (join)을 사용하는 것으로 바꾸었지만, 여전히 개선의 여지가 있다고 생각합니다. 메모리 소비를 가능한 한 낮게 유지하면서 이러한 캐싱 메커니즘을 구현하는 더 나은 방법이 있습니까? 이 목적에 더 적합한 다른 컬렉션 유형이 있습니까?

// Total number of entries in archive cache 
var numTotal = ArchiveCache.Count(); 

// Initial Linq query 
ParallelQuery<ArchiveCacheValue> query = ArchiveCache.AsParallel(); 

// The request may contain StationIds that the user is interested in, 
// so here's the filtering by StationIds with a join: 
if (request.StationIds.Count > 0) 
{ 
    query = from a in ArchiveCache.AsParallel() 
      join b in request.StationIds.AsParallel() 
      on a.StationId equals b 
      select a; 
} 

// The request may contain DatapointIds that the user is interested in, 
// so here's the filtering by DatapointIds with a join: 
if (request.DatapointIds.Count > 0) 
{ 
    query = from a in query.AsParallel() 
      join b in request.DatapointIds.AsParallel() 
      on a.DataPointId equals b 
      select a; 
} 

// Number of matching entries after filtering and before windowing 
int numFound = query.Count(); 

// Pagination: Select only the current window that needs to be shown on the page 
var result = query.Skip(request.Start == 0 ? 0 : request.Start - 1).Take(request.Length); 

// Number of entries on the current page that will be shown 
int numShown = result.Count(); 

// Build a response object, serialize it to Json and return to client 
// Note: The projection with the Rows is not a bottleneck, it is only done to 
// shorten 'StationId' to 's' etc. At this point there are only 25 to 50 rows, 
// so that is no problem and happens in way less than 1 ms 
ArchiveResponse myResponse = new ArchiveResponse(); 
myResponse.Length = request.Length; 
myResponse.numShown = numShown; 
myResponse.numFound = numFound; 
myResponse.numTotal = numTotal; 
myResponse.Rows = result.Select(x => new archRow() { s = x.StationId, d = x.DataPointId, t = x.DateValue, v = x.Value }).ToList(); 

return JsonSerializer.ToJsonString(myResponse); 

좀 더 자세한 사항 : 방송국의 수가 50-5 사이에 일반적으로 무언가가, 거의 이상 (50)이다

그래서 여기가 필터와 ArchiveCache 목록에서 관련 데이터를 가져 오는 코드입니다 datapoints의 수는 < 7000입니다. 웹 응용 프로그램은 web.config에 <gcAllowVeryLargeObjects enabled="true" />으로 64 비트로 설정됩니다.

정말 개선 및 권장 사항을 기다리고 있습니다. 어쩌면 배열이나 비슷한 것을 기반으로 완전히 다른 접근 방식이 있습니다. 더 좋은 방법을 수행합니다 없이 linq?

Answer 1

이 특정 쿼리 유형으로 저장소를 조정할 수 있습니다. 나는 그것을 측정 한

bool hasStations = request.StationIds.Length > 0; 
bool hasDatapoints = request.DatapointIds.Length > 0;    
int numFound = 0; 
List<ArchiveCacheValue> result; 
if (hasDatapoints && hasStations) { 
    // special case - filter by both 
    result = new List<ArchiveCacheValue>(); 
    // store station filter in hash set 
    var stationsFilter = new HashSet<int>(request.StationIds); 
    // first filter by datapoints, because you have more different datapoints than stations 
    foreach (var datapointId in request.DatapointIds.OrderBy(c => c)) {      
     foreach (var item in ArchiveCacheByDatapoint[datapointId]) {       
      if (stationsFilter.Contains(item.StationId)) { 
       // both datapoint and station matches filter - found item 
       numFound++; 
       if (numFound >= request.Start && result.Count < request.Length) { 
        // add to result list if matches paging criteria 
        result.Add(item); 
       } 
      } 
     } 
    } 
} 
else if (hasDatapoints) {     
    var query = Enumerable.Empty<ArchiveCacheValue>();     
    foreach (var datapoint in request.DatapointIds.OrderBy(c => c)) 
    { 
     var list = ArchiveCacheByDatapoint[datapoint]; 
     numFound += list.Count; 
     query = query.Concat(list); 
    } 
    // execute query just once 
    result = query.Skip(request.Start).Take(request.Length).ToList(); 
} 
else if (hasStations) {     
    var query = Enumerable.Empty<ArchiveCacheValue>(); 
    foreach (var station in request.StationIds.OrderBy(c => c)) 
    { 
     var list = ArchiveCacheByStation[station]; 
     numFound += list.Count; 
     query = query.Concat(list); 
    } 
    // execute query just once 
    result = query.Skip(request.Start).Take(request.Length).ToList(); 
} 
else { 
    // no need to do Count() 
    numFound = ArchiveCache.Count; 
    // no need to Skip\Take here really, ArchiveCache is list\array 
    // so you can use indexes which will be faster 
    result = ArchiveCache.Skip(request.Start).Take(request.Length).ToList(); 
} 

// Number of entries on the current page that will be shown 
int numShown = result.Count; 

내 컴퓨터에 그것까지 가끔 (이 1ms에서 실행 :

ArchiveCacheByDatapoint = ArchiveCache.GroupBy(c => c.DataPointId) 
      .ToDictionary(c => c.Key, c => c.ToList()); 
ArchiveCacheByStation = ArchiveCache.GroupBy(c => c.StationId) 
      .ToDictionary(c => c.Key, c => c.ToList()); 

그런 다음 쿼리에 그 사전을 사용 : 먼저, 메모리 아카이브에서 사전을 만들 10ms)에 대해 1 억 항목에 대해 시도한 모든 유형의 쿼리 (섹션 만 사용, 데이터 포인트는 섹션 및 데이터 포인트 모두 사용).

Answer 2

array 또는 에 해당 값을 저장하면 모든 데이터가 연속 메모리에 저장됩니다. 이렇게하면 locality of reference의 이점 (L1 캐시를 효율적으로 사용)이 크게 도움이됩니다.그리고 list (포인터/참조)의 오버 헤드도 피할 수 있습니다.

- (. 업데이트 IOW의 C# List<> 여기없는 포인터 오버 헤드 List가) C++ vector (즉, 배열과 동일하고, C# LinkedList이 C++ list .. 조금 혼란과 동일처럼 내가 C# List의 빠른 검색을했다가 보이는)

구조체를 가능한 작게 만드십시오. 가능하면 uint32 또는 심지어 uint16을 사용하십시오. datetime은 32 비트이고 double (값에 따라 다름) 대신 float 일 수도 있습니다. 또한 가장 넓은 값을 먼저 구조체에 넣으십시오 (보다 나은 정렬을 위해).

심지어 무차별 접근 (전체 배열 스캐닝, 100MB 연속 메모리)은 1 초 미만으로 잘 끝납니다.

더욱 최적화하려면 이진 검색을 수행 할 수 있도록 데이터를 정렬하거나 데이터베이스에서 정렬하여 검색하고 결과 집합의 값을 서로 가깝게 유지하십시오. 예 : sort on StationId, DataPointId.

데이터가 커지면 동일한 구조를 디스크 (바이너리 파일)에 저장하고 메모리 매핑을 통해 액세스 할 수 있습니다.

또한 처음 25 개 항목 만 검사하면됩니다. 그런 다음 해당 세션/쿼리에 대해 마지막으로 확인 된 위치를 저장할 수 있으며 다음 페이지를 요청하면 다음 25 개 항목부터 시작합니다. 또한 전체 결과 집합을 저장하는 데 필요한 메모리를 절약 할 수 있습니다.

스테이션 수가 적고 데이터가 StationId에 정렬 된 경우 시작 위치가 각각 StationId 인 작은 목록이나 점프 테이블 (가져 오는 동안)을 유지하고 바로 데이터 위치를 검색 할 수 있습니다 그 역.

는

---

이 목록에 (현재 약 1,000 만 항목) 전체 아카이브 테이블을로드하는 데 약 9 초 정도 걸립니다.

이 작업을 이미 수행하지 않은 경우에만 다중 재 할당을 피하기 위해 목록에 초기 Capacity을 설정해야합니다.

Answer 3

EVK의 대답은 그냥 어쩌면 그들이 이미 속도를 높일 것입니다 제거, 원래의 코드에 매우 최적화되지 않은 것을 지적하고 싶었던 것, 좋은 최적화가 있습니다

을 당신은 인 - 메모리 쿼리를 수행 세 번!

// execute query first time 
int numFound = query.Count(); 

var result = query.Skip(request.Start == 0 ? 0 : request.Start - 1).Take(request.Length); 

// executing query second time! 
int numShown = result.Count(); 

// executing query third time!  
// result.Select [...] .ToList() 

당신은 정말 결과의 계산 및 페이지 매김을 할 다음은 하면 어떻게해야하고.

Answer 4

다른 최적화. linq join을 메모리에 사용하는 것은 그렇게 효율적이지 않습니다.

그래서 request.StationIds과 request.DatapointIds에 합류하는 대신 해시 세트를 통해 해시 세트를 만들고 간단한 포함을 사용합니다. 이 같은.250 MS MaxDegreeOfParallelism = 2 모두와 평행 버전에 대한

- 9M 기록과 30 개 스테이션 ID의 sequental 방식에서 실행

if (request.StationIds.Count > 0) 
{ 
    var stationIdSet = new HashSet<int>(request.StationIds); 
    query = (from a in ArchiveCache 
      stationIdSet.Contains(a.StationId) 
      select a); 
       // .AsParallel() 
       // .MaxDegreeOfParallelism(...); 
} 

는 아웃 대략 150 조인 수행 (조인 및 해시) 은으로 악화되었습니다.

참고 : : AsParallel은 간단한 작업을 위해 오버 헤드를 걸고 있습니다. 이러한 작업은 최상의 옵션이 아닐 수 있습니다.