데이터베이스 검색으로 두 세트 간의 교차 크기로 정렬 된 결과가 표시됩니다.

Question

검색 세트와 교차하는 세트를 데이터베이스에서 검색하고 싶습니다. 결과가 교차로의 크기 순서대로 나에게 돌려 주어지기를 바란다.

데이터베이스 행의 집합은 약 10,000 개입니다. 검색 세트의 순서는 약 500입니다. 데이터베이스의 행 수는 약 1,000,000입니다.

예제 쿼리 :

 
search_set = [ This set has 500 id's ] 

SELECT rows WHERE "find_set" INTERSECTS "search_set" 
    ORDER BY "size of the intersection" 

예 데이타베이스 : 나는이 쿼리가 걸릴 것으로 예상 얼마나 캠

 
index   find_set 
1    [set with 10,000 ids] 
2    [set with 5,000 ids] 
... 
1,000,000  [set with 15,000 ids] 

• ?
• 내가 사용해야하는 특정 데이터베이스 또는 데이터베이스 라이브러리가 있습니까?
• 사전 처리가 필요합니까?
• 데이터베이스가 이러한 유형의 쿼리를 어떻게 구현합니까? 그들은 "search_set"에서 500 개의 id 각각에 대해 하나의 검색을 수행합니까?
• 이 유형의 문제와 해결 방법에 대해 알아야 할 다른 사항은 무엇입니까?

감사합니다.

Answer 1

이 쿼리의 성능은 데이터베이스 최적화 엔진과 쿼리 수행 방법에 따라 크게 달라집니다.

우선 데이터베이스에는 일반적으로 열에 15,000 개의 ID가있는 테이블이 없습니다. 대신 다음 표와 같은 것이 필요합니다.

set 
--- 
id 

set_entry 
----------- 
id 
set_id 
entry 

첫 번째 표에는 백만 개의 행이 있습니다. 두 번째는 100 억에 가깝습니다. set_entry.entry에 대한 색인을 작성하십시오.

일반적으로 쿼리를 정렬하는 가장 좋은 방법은 행 집합이 쿼리 집합의 값인 일종의 임시 테이블을 만드는 것입니다. 다음과 같은 쿼리를 실행 :

SELECT set_entry.id, COUNT(*) 
FROM set_entry 
    JOIN query_entry 
    ON set_entry.entry = query_entry.entry 
GROUP BY set_entry.id 
ORDER BY count(*) DESC 

당신이 당신의 각 요소에 대해이 인덱스에 대한 조회를 할 일치하는 모든 행을 철수 한 다음에 그룹화 작업을 진행해야한다는 것입니다 원하는 쿼리 계획 교차하는 각 세트에 대해 얼마나 많은가 있는지 파악하십시오. 첫 번째 단계에서는 500 개의 조회를 수행 한 다음 0 ~ 5 억 개의 행을 취소합니다. 500 만 달러를 돌려주고 있다고 가정 해 봅시다. 그룹화 작업은 해시를 작성하거나 데이터를 정렬하여 수행 할 수 있습니다 (데이터베이스는 어느 방식 으로든 수행 할 수 있음). 두 작업 모두 충분히 빠릅니다.

많은 알 수없는 부분이 있지만이 계획은 몇 초 정도 걸릴 수 있습니다.

뭘에주의 할 것은이 같은 쿼리입니다 : 대부분의 데이터베이스 엔진이 보는 내 경험에

SELECT set_entry.id, COUNT(*) 
FROM set_entry 
WHERE entry IN (id1, id2, ....) 
GROUP BY set_entry.id 
ORDER BY count(*) DESC 

, 그들은 인덱스를 사용할 수 없다는 것을 결정한다. 대신 그들은 set_entry (100 억 개의 행이 있음)을 모두 스캔하고 각각 500 개의 요소 세트를 스캔하여 페어 와이즈 비교를 수행합니다.이것은 약 5 조쌍의 쌍 비교의 초기 단계를 의미합니다. 이 계획은 CPU를 몇 시간 동안 바쁘게 유지합니다.