sum, count, avg와 같은 SQL 함수에 내장 된 Timecomplexity

Question

수, 합계, 평균 또는 mysql, sql 서버의 내장 "수학"함수와 같은 함수의 시간 복잡도는 얼마입니까? 오라클과 다른 사람?

sum (myColumn)을 호출하는 것이 Linear라고 생각할 것입니다.

하지만 count (1)은 아닙니다. 어떻게 그리고 왜 실시간 복잡성이 무엇입니까?

완벽한 세계에서 나는 합계, 평균 및 수를 O (1)로하고 싶습니다. 하지만 우리는 그 중 하나에 살지 않습니다.

Answer 1

SQL에서 집계의 수학 함수 복잡성은 완전히 부작용입니다. 실제로 중요한 것은 데이터 액세스 복잡도 (테이블 스캔, 인덱스 범위 스캔, 인덱스 찾기 등)와 읽는 페이지 수를 선택하는 것입니다. 각 집계의 내부에는 약간의 차이가있을 수 있지만 모두 동일한 방식으로 작동합니다 (상태를 유지하고 각 입력 값에 대해 집계를 계산합니다). 집계가 두 번 입력되므로 두 번 봅니다. 모든 O (n)을 내부 구현으로 사용합니다. 여기서 'n'은 집계에 공급되는 레코드 수입니다 (필연적으로 테이블의 레코드 수는 아닙니다!).

일부 집계에는 내부 바로 가기가 있습니다. COUNT (*) 은 가능한 경우 일부 시스템의 메타 데이터에서 개수를 반환합니다.

Answer 2

참고 : 이것은 SQL 쿼리 계획자가 작동하는 방식에 대한 내 이해를 기반으로 한 추측이며 완전히 정확하지 않을 수 있습니다.

나는 모든 집계 함수 또는 적어도 위에서 언급 한 "수학"이 O (n)이어야한다고 생각합니다.

1. 하면이 술어 및 필터 Join 술어와 일치하는 행을 가져 오기
2. 는 GROUP BY 절에 따라 행 그룹을 만듭니다 (예 : "WHERE 절") 다음과 같이 쿼리는 대략 실행됩니다. GROUP BY가없는 쿼리에 대해 단일 행 그룹이 생성됩니다.
3. 각 행 그룹에 대해 그룹의 행에 집계 함수를 적용합니다. SUM, AVG, MIN, MAX 및 CONCAT과 같은 숫자가 아닌 함수와 같은 경우 간단한 O (n) 알고리즘이 있으며 사용되는 것으로 판단됩니다. HAVING 술어가 존재하는 경우, 필터 출력 행 집계 기능 않더라도, 그러나,이 술어를

참고하여 단계 # 2

에서 생성 된 각각의 행 그룹의 설정 출력에 하나 개의 행을 만들어 O (n), 조작이 아닐 수도 있습니다. 데카르트자가 테이블에 조인하는 쿼리를 작성하면 초기 행 세트를 생성하기 위해 O (n * n) 최소값을 보게됩니다 (1 단계). 행 그룹 (2 단계)을 생성하기위한 정렬은 O (ng n) 일 수 있으며 정렬 작업 (메모리 내 작업과 반대)으로 디스크 저장소가 필요할 수 있으므로 사용자의 쿼리가 제대로 수행되지 않을 수 있습니다 많은 행을 조작.

Answer 3

큰 데이터웨어 하우스 스타일 쿼리의 경우 주요 데이터베이스가 작업을 병렬 처리 할 수 ​​있으므로 여러 CPU가 작업을 수행 할 수 있습니다. 병렬 스레드를 조정하는 데 드는 비용이 여러 CPU를 사용하는 이점을 상쇄하므로 매우 선형 적이 지 않은 임계점이 있습니다.

Answer 4

mysql, sql server, oracle 및 기타에 내장 된 "수학"함수의 수, 합계, 평균 또는 기타와 같은 함수의 시간 복잡도는 얼마나됩니까?GROUP BYMyISAM없이 함께 MySQL에서

• , COUNT(*)이다 O(1) (상수)

  이것은 테이블의 메타 데이터에 저장된다. GROUP BY없이 인덱스 식 모든 시스템에서

• , MAX 및 MIN는 O(log(n)) (로그)이다.

  단일 검색으로 페치됩니다.

• 집계 기능 GROUP BY 또는 GROUP BY없이 사용되는 경우,이 GROUP BYSORT를 사용하는 경우 HASH

• 집계 기능 O(n log(n))이다 사용 O(n) (선형)이다.

모든 값을 가져와 계산하고 상태 변수 (해시 테이블에 저장 될 수 있음)에 저장해야합니다.

또한 SORT을 사용할 때 정렬해야합니다.