데이터베이스 조인은 언제 그리고 왜 비용이 많이 듭니까?

https://stackoverflow.com/questions/173726

05-07-2019
|

문제

저는 데이터베이스에 대해 조사 중이며 관계형 DB의 몇 가지 제한 사항을 살펴보고 있습니다.

큰 테이블의 조인이 매우 비싸다는 것을 알고 있지만 그 이유를 완전히 모르겠습니다.조인 작업을 실행하기 위해 DBMS는 무엇을 해야 합니까? 병목 현상이 발생하는 곳은 어디입니까?
비정규화가 이러한 비용을 극복하는 데 어떻게 도움이 될 수 있습니까?다른 최적화 기술(예: 인덱싱)은 어떻게 도움이 됩니까?

개인적인 경험을 환영합니다!리소스에 대한 링크를 게시하려면 Wikipedia를 피하세요.나는 그것을 어디서 찾을 수 있는지 이미 알고 있습니다.

이와 관련하여 BigTable, SimpleDB와 같은 클라우드 서비스 데이터베이스에서 사용하는 비정규화된 접근 방식이 궁금합니다.보다 이 질문.

해결책

성능 향상을 위해 비정규화를 수행하시겠습니까?설득력 있게 들리지만 물을 담지 않습니다.

Ted Codd 박사와 함께 관계형 데이터 모델의 최초 제안자인 Chris Date는 정규화에 반대하는 잘못된 주장에 인내심이 부족하여 과학적 방법을 사용하여 체계적으로 이를 무너뜨렸습니다.그는 대규모 데이터베이스를 갖고 있고 테스트를 거쳤습니다. 이러한 주장.

내 생각엔 그 사람이 그걸 쓴 것 같아 관계형 데이터베이스 저술 1988-1991 하지만 이 책은 나중에 6판으로 출간되었습니다. 데이터베이스 시스템 소개, 이는 그만큼 데이터베이스 이론과 설계에 대한 결정적인 텍스트입니다. 제가 집필 중인 제8판이며 앞으로 수십 년 동안 계속 인쇄될 것입니다.크리스 데이트(Chris Date)는 우리 대부분이 여전히 맨발로 뛰어다니던 시절 이 분야의 전문가였습니다.

그는 다음과 같은 사실을 발견했습니다.

그 중 일부는 특별한 경우에 해당합니다.
그들 모두는 일반적인 사용에 대한 비용을 지불하지 않습니다
다른 특별한 경우에는 모두 훨씬 더 나쁩니다.

이 모든 것은 작업 세트의 크기를 완화하는 것으로 돌아옵니다.올바르게 설정된 인덱스와 적절하게 선택된 키를 포함하는 조인은 결과를 크게 잘라내기 때문에 비용이 많이 들지 않고 저렴합니다. ~ 전에 행이 구체화됩니다.

결과를 구체화하려면 작업에서 가장 비용이 많이 드는 대량 디스크 읽기 작업이 필요합니다.대조적으로 조인을 수행하려면 논리적으로 열쇠.실제로는 키 값도 가져오지 않습니다.키 해시 값은 조인 비교에 사용되어 다중 열 조인 비용을 완화하고 문자열 비교와 관련된 조인 비용을 근본적으로 줄입니다.캐시에 훨씬 더 적합할 뿐만 아니라 수행할 디스크 읽기도 훨씬 줄어듭니다.

또한, 좋은 최적화 프로그램은 가장 제한적인 조건을 선택하고 조인을 수행하기 전에 이를 적용하여 카디널리티가 높은 인덱스에서 조인의 높은 선택성을 매우 효과적으로 활용합니다.

물론 이러한 유형의 최적화는 비정규화된 데이터베이스에도 적용될 수 있습니다. 원하다 스키마를 비정규화하기 위해 일반적으로 인덱스를 설정할 때 카디널리티에 대해 생각하지 않습니다.

테이블 스캔(조인을 생성하는 과정에서 테이블의 모든 행을 검사하는 것)은 실제로 거의 발생하지 않는다는 점을 이해하는 것이 중요합니다.쿼리 최적화 프로그램은 다음 중 하나 이상이 유지되는 경우에만 테이블 스캔을 선택합니다.

관계에 200개 미만의 행이 있습니다(이 경우 스캔 비용이 더 저렴해집니다).
조인 열에 적합한 인덱스가 없습니다. (이러한 열에 조인하는 것이 의미가 있다면 왜 인덱스가 생성되지 않습니까?고쳐라)
열을 비교하려면 유형 강제가 필요합니다(WTF?!고치거나 집에 가세요) ADO.NET 문제에 대한 최종 참고 사항을 참조하세요.
비교 인수 중 하나가 표현식입니다(인덱스 없음).

작업을 수행하는 것은 수행하지 않는 것보다 비용이 더 많이 듭니다.그러나, 잘못된 무의미한 디스크 I/O를 강제로 수행한 다음 실제로 필요한 조인을 수행하기 전에 찌꺼기를 버리는 작업은 많이 더 비싼."잘못된" 연산이 미리 계산되고 인덱스가 현명하게 적용된 경우에도 상당한 페널티가 남아 있습니다.수반되는 업데이트 예외에도 불구하고 조인을 미리 계산하기 위한 비정규화는 특정 조인에 대한 약속입니다.필요한 경우 다른 참여하세요. 그 약속에는 대가가 따르게 됩니다 큰.

세상이 변화하고 있다는 사실을 누군가 나에게 상기시키고 싶다면, 더 거친 하드웨어에 있는 더 큰 데이터 세트가 Date의 연구 결과 확산을 과장한다는 사실을 알게 될 것입니다.

청구 시스템이나 정크 메일 생성기 작업을 하고(부끄럽습니다) 비정규화가 더 빠르다는 사실을 알고 있다고 분개하여 키보드에 손을 대고 있는 여러분 모두에게 죄송합니다. 하지만 여러분은 특별한 환경 중 하나에 살고 있습니다. 사례 - 구체적으로 처리하는 사례 모두 데이터의 순서대로.일반적인 경우는 아니고 당신은 ~이다 당신의 전략에 정당화됩니다.

당신은 ~ 아니다 그것을 잘못 일반화하는 것은 정당하다.데이터 웨어하우징 시나리오에서 적절한 비정규화 사용에 대한 자세한 내용은 참고 섹션의 끝 부분을 참조하세요.

나도 대답하고 싶다

조인은 립글로스가 포함된 데카르트 제품일 뿐입니다.

정말 헛소리가 많아요.제한사항은 가능한 한 빨리 적용되며, 가장 제한적인 사항이 먼저 적용됩니다.당신은 이론을 읽었지만 이해하지 못했습니다.조인은 치료됨 "술어가 적용되는 데카르트 곱"으로 오직 쿼리 최적화 프로그램에 의해.이는 기호 분해를 용이하게 하기 위한 기호 표현(실제로 정규화)입니다. 따라서 최적화 프로그램은 모든 동등한 변환을 생성하고 비용과 선택성에 따라 순위를 매겨 최상의 쿼리 계획을 선택할 수 있습니다.

데카르트 곱을 생성하는 최적화 프로그램을 얻을 수 있는 유일한 방법은 조건자를 제공하지 못하는 것입니다. SELECT * FROM A,B

노트

David Aldridge는 몇 가지 중요한 추가 정보를 제공합니다.

실제로 인덱스 및 테이블 스캔 외에도 다양한 전략이 있으며 최신 최적화 프로그램은 실행 계획을 생성하기 전에 이러한 전략을 모두 희생합니다.

실용적인 조언:외래 키로 사용할 수 있으면 색인을 생성하여 색인 전략은 다음과 같습니다. 사용 가능 옵티마이저에게.

나는 MSSQL 옵티마이저보다 더 똑똑했습니다.두 가지 버전이 전에 변경되었습니다.이제는 일반적으로 가르칩니다. 나.이는 매우 실제적인 의미에서 규칙 기반 시스템이 효과적일 만큼 충분히 폐쇄된 영역에서 매우 영리한 많은 사람들의 모든 지혜를 성문화하는 전문가 시스템입니다.

"Bollocks"는 재치가 없었을 수도 있습니다.나는 덜 거만해지라는 요청을 받았고 수학은 거짓말을 하지 않는다는 것을 상기시켰다.이는 사실이지만 수학적 모델의 모든 의미를 문자 그대로 받아들여야 하는 것은 아닙니다.음수의 제곱근은 부조리한 부분을 주의 깊게 조사하는 것을 피하고 방정식을 해석하기 전에 모두 취소했는지 확인하는 경우 매우 편리합니다.

내가 그토록 야만적으로 대답한 이유는 그 말에 나온 말이 다음과 같았기 때문입니다.

조인 ~이다 데카르트 제품...

원래 의도한 내용은 아닐 수도 있지만 ~이다 쓰여진 내용은 절대적으로 사실이 아닙니다.데카르트 곱은 관계입니다.조인은 함수입니다.보다 구체적으로 말하면 조인은 관계 값 함수입니다.빈 술어를 사용하면 데카르트 곱이 생성되고 이를 확인하는 것은 데이터베이스 쿼리 엔진에 대한 정확성 검사 중 하나이지만 교실 밖에서는 실질적인 가치가 없기 때문에 실제로 제약 없는 조인을 작성하는 사람은 없습니다.

나는 독자들이 모델과 모델링된 것을 혼동하는 고대의 함정에 빠지는 것을 원하지 않기 때문에 이것을 불렀습니다.모델은 편리한 조작을 위해 의도적으로 단순화된 근사치입니다.

테이블 스캔 조인 전략 선택에 대한 기준은 데이터베이스 엔진마다 다를 수 있습니다.이는 트리 노드 채우기 비율, 키-값 크기 및 알고리즘의 미묘함과 같은 여러 구현 결정의 영향을 받지만 광범위하게 말하면 고성능 인덱싱의 실행 시간은 케이 통나무 N + 씨.C 용어는 대부분 설정 시간으로 구성된 고정 오버헤드이며 곡선 모양은 선형 검색에 비해 보상을 받을 수 없음을 의미합니다. N 수백에 있습니다.

때로는 비정규화가 좋은 생각일 때도 있습니다.

비정규화는 특정 조인 전략에 대한 약속입니다.앞서 언급했듯이 이는 방해가 됩니다. 다른 합류 전략.그러나 디스크 공간이 풍부하고 예측 가능한 액세스 패턴이 있으며 대부분 또는 전부를 처리하려는 경향이 있는 경우 조인을 미리 계산하는 것이 매우 가치 있을 수 있습니다.

또한 작업에서 일반적으로 사용하는 액세스 경로를 파악하고 해당 액세스 경로에 대한 모든 조인을 미리 계산할 수도 있습니다.이는 데이터 웨어하우스의 전제입니다. 적어도 전문 용어 준수를 위해서가 아니라 자신이 하는 일을 왜 하는지 아는 사람들이 데이터 웨어하우스를 구축한 경우에는 그렇습니다.

적절하게 설계된 데이터 웨어하우스는 정규화된 트랜잭션 처리 시스템의 대량 변환을 통해 주기적으로 생성됩니다.이러한 운영 데이터베이스와 보고 데이터베이스의 분리는 OLTP와 OLAP(온라인 트랜잭션 처리, 즉 데이터 입력 및 온라인 분석 처리, 즉 보고) 간의 충돌을 제거하는 매우 바람직한 효과를 갖습니다.

여기서 중요한 점은 주기적인 업데이트와 별개로 데이터 웨어하우스는 읽기 전용.이로 인해 업데이트 예외 문제에 대한 의문이 제기됩니다.

OLTP 데이터베이스(데이터 입력이 발생하는 데이터베이스)를 비정규화하는 실수를 저지르지 마십시오.청구 실행 속도가 더 빠를 수 있지만 그렇게 하면 업데이트 예외가 발생합니다.리더스 다이제스트에서 귀하에게 자료 전송을 중단시키려고 시도한 적이 있습니까?

요즘 디스크 공간이 저렴하니, 몸을 녹이세요.그러나 비정규화는 데이터 웨어하우스의 일부일 뿐입니다.미리 계산된 롤업 값에서 훨씬 더 큰 성능 향상이 파생됩니다.월별 합계, 그런 것입니다.그것은 언제나 작업 세트를 줄이는 것에 대해.

유형 불일치로 인한 ADO.NET 문제

varchar 유형의 인덱싱된 열을 포함하는 SQL Server 테이블이 있고 AddWithValue를 사용하여 이 열에 대한 쿼리를 제한하는 매개 변수를 전달한다고 가정합니다.C# 문자열은 유니코드이므로 유추된 매개 변수 유형은 VARCHAR과 일치하지 않는 NVARCHAR입니다.

VARCHAR에서 NVARCHAR로의 변환은 확장 변환이므로 암시적으로 발생합니다. 하지만 인덱싱에 작별을 고하고 그 이유를 알아보세요.

"디스크 적중 횟수 계산"(Rick James)

모든 것이 RAM에 캐시되어 있는 경우 JOINs 오히려 저렴해요.즉, 정규화에는 그다지 많은 것이 없습니다. 성능 저하.

"정규화된" 스키마로 인해 JOINs 디스크에 많은 영향을 주지만 동등한 "비정규화된" 스키마가 디스크에 영향을 미칠 필요가 없으면 비정규화가 성능 경쟁에서 승리합니다.

원저자의 코멘트:최신 데이터베이스 엔진은 조인 작업 중 캐시 누락을 최소화하기 위해 액세스 순서를 구성하는 데 매우 능숙합니다.위의 내용은 사실이지만 대규모 데이터에서 조인이 문제가 될 정도로 비용이 많이 든다는 의미로 오해될 수 있습니다.이는 경험이 부족한 개발자의 잘못된 의사결정으로 이어질 수 있습니다.

다른 팁

대부분의 의견 제시자가 주목하지 않는 것은 복잡한 RDBM에서 이용할 수있는 광범위한 결합 방법론이며, 거절자는 거절 된 데이터를 유지하는 데 더 높은 비용을 불러 일으킨다는 것입니다. 모든 조인이 인덱스를 기반으로하는 것은 아니며 데이터베이스에는 조인 비용을 줄이기위한 참여를위한 최적화 된 알고티브와 방법론이 많이 있습니다.

어쨌든, 결합 비용은 그 유형과 몇 가지 다른 요소에 따라 다릅니다. 전혀 비싸지 않아도됩니다. 몇 가지 예입니다.

벌크 데이터가 동등한 해시 조인은 실제로 매우 저렴하며 해시 테이블을 메모리에서 캐시 할 수없는 경우에만 비용이 중요해집니다. 색인이 필요하지 않습니다. 결합 된 데이터 세트 사이의 equi 파티셔닝은 큰 도움이 될 수 있습니다.
Sort-Merge Join의 비용은 병합보다는 종류의 비용에 의해 주도됩니다. 인덱스 기반 액세스 방법은 종류의 비용을 거의 제거 할 수 있습니다.
인덱스에 중첩 루프 조인 비용은 B-Tree 지수의 높이와 테이블 블록 자체의 액세스에 의해 구동됩니다. 빠르지 만 벌크 결합에는 적합하지 않습니다.
클러스터를 기반으로 한 중첩 루프 결합은 훨씬 저렴하며 합류 행당 논리적 IO의 요구가 적습니다. 결합 된 테이블이 동일한 클러스터에 있으면 결합 된 행의 코 로케이션을 통해 결합이 매우 저렴 해집니다.

데이터베이스는 가입하도록 설계되었으며 결합 메커니즘을 잘못 이해하지 않는 한 일반적으로 수행하는 방식이 매우 유연하며 일반적으로 매우 유연합니다.

전체 질문은 잘못된 전제에 근거한 것이라고 생각합니다. 큰 테이블에 합류합니다 ~ 아니다 반드시 비싸다. 사실로, 효율적으로 합류하는 것은 관계형 데이터베이스가 존재하는 주된 이유 중 하나입니다. 조금도. 큰에 합류합니다 세트 종종 비싸지 만 큰 표 B의 전체 내용과 큰 테이블 A의 전체 내용을 결합하고 싶지는 않습니다. 대신, 쿼리를 작성합니다. 중요한 행만 각 테이블의 사용이 사용되고 조인에 의해 보관 된 실제 세트는 더 작게 남아 있습니다.

또한 Peter Wone이 언급 한 효율성이있어 최종 결과 세트가 구체화 될 때까지 각 레코드의 중요한 부분 만 메모리에 필요합니다. 또한 많은 결합이있는 큰 쿼리에서 일반적으로 작은 테이블 세트로 시작하고 큰 테이블 세트로 시작하여 메모리에 보관 된 세트가 가능한 한 더 작게 유지되도록합니다.

제대로 수행하면 결합은 일반적으로입니다 가장 좋은 방법은 많은 양의 데이터를 비교, 결합 또는 필터링합니다.

병목 현상은 거의 없습니다 언제나 디스크 I/O, 그리고 더 구체적으로 - 임의의 디스크 I/O (비교하면 순차적 판독 값은 상당히 빠르며 읽기 미리 전략으로 캐시 할 수 있음).

가입 ~할 수 있다 무작위로 추구하는 것 - 큰 테이블의 작은 부분을 읽는다면. 그러나 쿼리 최적화기는이를 찾고, 그것이 더 좋을 것이라고 생각되면 순차 테이블 스캔 (불필요한 행을 폐기)으로 전환합니다.

단일 피형화 된 테이블은 비슷한 문제가 있습니다. 행은 크기 때문에 단일 데이터 페이지에 적합하지 않습니다. 다른 것과 멀리 떨어져있는 행이 필요하고 큰 행 크기가 더 멀리 떨어져 있으면 더 임의의 I/O가 있습니다. 다시, 테이블 스캔은 이것을 피해야 할 수 있습니다. 그러나 이번에는 테이블 스캔이 큰 행 크기로 인해 더 많은 데이터를 읽어야합니다. 당신이 있다는 사실을 추가하십시오 데이터 복사 단일 위치에서 여러 위치에 이르기까지 RDBMS에는 훨씬 더 읽을 수 있습니다 (및 캐시).

2 개의 테이블을 사용하면 2 개의 클러스터 된 인덱스를 얻을 수 있으며 일반적으로 더 많은 색인 (삽입/업데이트 오버 헤드가 적기 때문에)이 성능을 크게 증가시킬 수 있으므로 (주로, 인덱스가 작고, 디스크 오프 오프 디스크가 빠르게 읽을 수 있기 때문입니다. (또는 캐시가 저렴하고) 디스크에서 읽어야 할 테이블 행의 양을 줄입니다).

결합 된 유일한 오버 헤드는 일치하는 행을 파악하는 것입니다. SQL Server는 주로 데이터 세트 크기를 기반으로 3 가지 유형의 조인을 사용하여 일치하는 행을 찾습니다. Optimizer가 잘못된 결합 유형을 선택하면 (부정확 한 통계, 부적절한 인덱스 또는 최적화 버그 또는 에지 케이스로 인해) 쿼리 시간에 크게 영향을 줄 수 있습니다.

루프 조인은 (적어도 1) 소형 데이터 세트의 경우 크게 저렴합니다.
병합 조인은 먼저 두 데이터 세트의 일종이 필요합니다. 그러나 인덱스 된 열에 가입하면 인덱스가 이미 정렬되어 더 이상 작업을 수행 할 필요가 없습니다. 그렇지 않으면 정렬에 일부 CPU 및 메모리 오버 헤드가 있습니다.
해시 조인에는 메모리 (해시 가능)와 CPU (해시를 구축하기 위해) 모두 메모리가 필요합니다. 다시, 이것은 디스크 I/O와 관련하여 상당히 빠릅니다. 하지만, Hashtable을 저장하기에 RAM이 충분하지 않은 경우 SQL Server는 TempDB를 사용하여 해시 테이블 및 발견 행의 일부를 저장 한 다음 한 번에 해시 테이블의 일부만 처리합니다. 모든 디스크와 마찬가지로 이것은 상당히 느립니다.

최적의 경우, 이들은 디스크 I/O를 유발하지 않으며 성능 관점에서 무시할 수 있습니다.

대체로 최악의 경우 - 실제로 같은 양을 읽는 것이 더 빠르야합니다. 논리적 X의 데이터는 작은 디스크 판독 값으로 인해 단일 거절 테이블에서 나온 테이블에 합류했습니다. 같은 양을 읽습니다 물리적 인 데이터, 약간의 오버 헤드가있을 수 있습니다.

쿼리 시간은 일반적으로 I/O 비용에 의해 지배되며, 데이터의 크기가 변하지 않기 때문에 (일부 미성년 행으로 오버 헤드를 제외하고) 테이블을 합쳐서 큰 이점이 없습니다. IME는 성능을 증가시키는 경향이있는 피의 유형은 계산에 필요한 10,000 행을 읽는 대신 계산 된 값을 캐싱합니다.

테이블에 가입하는 순서는 매우 중요합니다. 두 개의 데이터 세트가있는 경우 쿼리를 한쪽으로 빌드하려고 시도하여 가장 작은 것이 먼저 사용되어야하는 데이터의 양을 줄입니다.

일부 데이터베이스의 경우 중요하지 않습니다. 예를 들어 MS SQL은 대부분 적절한 조인 순서를 알고 있습니다. 일부 (IBM Informix와 같은)의 경우 주문이 모든 차이를 만듭니다.

조인의 복잡성 클래스를 고려할 때 교체 또는 정규화 여부를 결정하는 것은 매우 간단한 프로세스입니다. 예를 들어, 쿼리가 O (k log n) 일 때 k가 원하는 출력 크기와 관련이있을 때 데이터베이스를 정규화하여 데이터베이스를 설계하는 경향이 있습니다.

성능을 제거하고 최적화하는 쉬운 방법은 정상화 구조의 변화가 비정규 구조에 어떤 영향을 미치는지 생각하는 것입니다. 그러나 비정규화 된 구조화 된 구조화에 대한 트랜잭션 논리가 필요할 수 있으므로 문제가 될 수 있습니다.

문제가 크기 때문에 정규화와 탈피에 대한 논쟁은 끝나지 않을 것입니다. 자연 솔루션에 두 가지 접근 방식이 모두 필요한 많은 문제가 있습니다.

일반적으로, 나는 항상 재구성 될 수있는 정규화 된 구조와 비정규 화 된 캐시를 저장했습니다. 결국,이 캐시는 미래의 정규화 문제를 해결하기 위해 내 엉덩이를 절약합니다.

다른 사람들이 말한 것을 자세히 설명하고

조인은 립글로스가있는 데카르트 제품입니다. {1,2,3,4} x {1,2,3}는 12 개의 조합을 제공합니다 (NXN = N^2). 이 계산 된 세트는 조건이 적용되는 참조 역할을합니다. DBMS는 조건 (왼쪽과 오른쪽이 모두 2 또는 3 인 경우)을 적용하여 일치 조건을 제공합니다. 실제로 더 최적화되었지만 문제는 동일합니다. 세트의 크기 변화는 결과 크기를 기하 급수적으로 증가시킵니다. 모두 소비 된 메모리 및 CPU 사이클의 양은 지수 적으로 영향을받습니다.

우리가 비정규 화 될 때, 우리는이 계산을 완전히 피하고, 책의 모든 페이지에 첨부 된 끈적 끈적한 끈적 끈적한 것을 생각합니다. 참조를 사용하여 정보를 추론 할 수 있습니다. 우리가 지불하는 형벌은 우리가 DBMS의 본질을 타협하고 있다는 것입니다 (최적의 데이터 구성)

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow