MongoDB에서 인덱스로 정렬하는 방법은 무엇입니까?

MongoDB에서 인덱스로 정렬하는 방법은 무엇입니까?

MongoDB에서 인덱스로 정렬하는 것이 실제로 어떻게 작동하는지 궁금합니다.MongoDB 문서에는 몇 가지 기사가 있지만 실제로 정렬이 어떻게 진행되는지 또는 시간 복잡성에 대해서는 설명하지 않습니다.SO와 일반적인 인터넷 검색은 지금까지 관련성이 없었습니다.

컬렉션에 문서가 있고, find() 절이 b 문서와 일치하며, 반환된 c 문서의 한계가 있고, a >> b >> c이며, c는 반환된 집합이 메모리에 들어갈 수 없는 적절한 큰 숫자라고 가정합니다. 예를 들어, 1M 문서라고 가정합니다.

작업을 시작할 때, 정렬해야 하는 기존의 문서와 문서가 정렬될 기능에 대한 크기가 a인 정렬 트리 색인이 있습니다.

나는 상상할 수 있습니다.

각 개체에 대해 순서대로 인덱스를 이동합니다.ID는 b 문서 목록을 통과합니다.c에 도달할 때까지 일치 항목을 반환합니다.이것은 O(ab)입니다.

A)로 지정하지만 개체의 해시 집합을 빌드합니다.b 문서의 ID가 먼저입니다.이것은 O(a)이지만 O(b) 메모리를 사용합니다.

저는 b 문서 집합을 가로지르는 것을 기준으로 정렬을 고려해 보았지만 색인 없이 정렬하는 것보다 더 나은 O(blog b)보다 더 빠른 것을 찾을 수 없을 것 같습니다.

모든 종류가 인덱스 스캔을 필요로 하지 않는다고 가정합니다(그러나 제가 틀릴 수도 있습니다). 그렇다면 실제로 어떻게 분류가 작동합니까?

업데이트:

Kevin의 답변과 제공된 링크는 질문의 범위를 많이 좁혔지만 몇 가지 사항을 확인하고 명확히 하고 싶습니다.

1. 메모리 내 정렬을 피하려면 쿼리와 정렬에 다른 인덱스를 사용할 수 없는 것으로 알고 있습니다.제가 이 페이지를 읽었을 때 당신이 할 수 있는 것처럼 보였지만(적어도 어느 쪽이든 지정하지 않았습니다), 그것은 잘못된 것 같습니다.기본적으로 문서는 쿼리 중에 색인 순서대로 검색되므로 색인 순서대로 반환되므로 정렬됩니다.그렇죠?
2. 복합 인덱스를 쿼리할 때 정렬 인덱스는 쿼리가 동일한 인덱스를 제외하고 복합 인덱스의 첫 번째 인덱스여야 합니다.그렇지 않으면 메모리에서 정렬이 수행됩니다.그렇죠?

3. 정렬은 어떻게 작동합니까?$in또는$or질문?예를 들어, 쿼리가 다음과 같다고 가정합니다.

   {a: {$in: [4, 6, 2, 1, 3, 10]}, b: {$gt: 1, $lt: 6}}

그고복지있다니습가수합리▁index▁on에 가 있습니다.a그리고.b그 차례로.정렬이 진행 중인 경우 정렬이 어떻게 작동합니까?a또는b?$or제가 이해하기로는 훨씬 더 복잡합니다$or쿼리는 기본적으로 여러 개의 개별 쿼리로 분할됩니다.$or쿼리는 항상 메모리 내 정렬을 수행합니다. 적어도 개별 쿼리의 결과를 병합하기 위한 것입니까?

MongoDB의 인덱스는 각 인덱스 항목이 디스크의 특정 위치를 가리키는 B-tree 구조로 저장됩니다.또한 B-tree 구조를 사용하면 MongoDB 인덱스가 정렬된 순서로 저장되고 항상 순서대로 이동되며 MongoDB가 인덱스를 통해 정렬된 순서로 일련의 문서를 가져오는 비용이 저렴합니다.

업데이트: B-tree 구조는 MMAPv1 스토리지 엔진에 적용되지만 WiredTiger 스토리지 엔진(MongoDB 3.2 이후 기본값)에 의해 약간 다르게 구현됩니다.기본 아이디어는 동일하게 유지되며, 정렬된 순서로 인덱스를 이동하는 것이 저렴합니다.

A SORT쿼리의 단계(즉, 메모리 내 정렬)는 32MB의 메모리 사용으로 제한됩니다.다음과 같은 경우 쿼리가 실패합니다.SORT단계가 이 제한을 초과합니다.가 MongoDB와 할 수 의 정렬된 하여 이러한 수 .sort()메모리 내 정렬을 수행하지 않는 매개 변수입니다.

쿼리의 모양이 다음과 같다고 가정합니다.

    db.a.find({b:{$gt:100}, c:{$gt:200}}).sort(...)

를 .a다음의 지수를 갖는 것:

    db.a.createIndex({b:1,c:1})

다음과 같은 경우 두 가지 가능한 시나리오가 있습니다.sort()단계가 쿼리에서 지정되었습니다.

MongoDB는 인덱스의 정렬된 특성을 사용할 수 없으며 메모리 내 단계를 수행해야 합니다.

이것은 쿼리가 "인덱스 접두사"를 사용할 수 없는 경우의 결과입니다.예:

    db.a.find({b:{$gt:100}, c:{$gt:200}}).sort({c:1})

위의 쿼리에서 인덱스는{b:1,c:1}다음 용도로 사용할 수 있습니다.

• 이 있는 문서 :b의경보 100다큼우의 경우 보다 큼{b:{$gt:100}}쿼리의 일부입니다.
• 그러나 반환된 문서가 에 따라 정렬된다는 보장은 없습니다.

따라서 MongoDB는 메모리 내 정렬을 수행할 수밖에 없습니다. 그explain()에는 이쿼의출다가것질입다니음을력은리가 표시가 표시됩니다.SORT이 무. 이. 거. 대.SORT스테이지는 32MB의 메모리 사용으로 제한됩니다.

MongoDB는 인덱스의 정렬된 특성을 사용할 수 있습니다.

쿼리에서 다음을 사용하는 경우의 결과입니다.

• 인덱스 순서와 일치하는 키 정렬
• 를 지정합니다 인와즉순서를동한(다, 인덱스니)).{b:1,c:1}에 사용할 수 있습니다.sort({b:1,c:1})또는sort({b:-1,c:-1})하지만 아닙니다.sort({b:1,c:-1}))

예:

    db.a.find({b:{$gt:100}, c:{$gt:200}}).sort({b:1})

위의 쿼리에서 인덱스는{b:1,c:1}다음 용도로 사용할 수 있습니다.

• 이 있는 문서 :b의경보 100다큼우의 경우 보다 큼{b:{$gt:100}}쿼리의 일부입니다.
• 이 경우 MongoDB는 반환된 문서가 로 정렬되도록 보장할 수 있습니다.

그explain()위 쿼리의 출력은 다음을 포함하지 않습니다.SORTstage. 또한 쿼리를 사용한 경우와 사용하지 않은 경우의 출력이 동일합니다.본질적으로, 우리는 다음을 얻고 있습니다.sort()무료.

이 주제를 이해할 수 있는 유용한 자료는 MongoDB 복합 인덱스 최적화입니다.이 블로그 게시물은 2012년에 작성되었습니다.일부 용어는 구식이지만 게시물의 기술적 특성은 여전히 관련이 있습니다.

후속 질문에 대한 업데이트

1. MongoDB는 대부분의 쿼리에 대해 하나의 인덱스만 사용합니다.예를 들어 인메모리를 방지하기 위해SORT in (쿼리의 단계)

   db.a.find({a:1}).sort({b:1})
   

   인덱스는 둘 다 포함해야 합니다.a그리고.b에; 를동시에들어, 같복다음, 합지은수과 등의 {a:1,b:1}필수 항목입니다.의 인덱스는 둘 수 없습니다.{a:1}그리고.{b:1}.{a:1}, 동일부인덱스 및할사용에품및▁index▁to.{b:1}정렬 부품에 사용할 인덱스입니다.이 경우 MongoDB는 두 개의 인덱스 중 하나를 선택합니다.

   따라서 결과는 인덱스 순서대로 조회 및 반환되므로 정렬되는 것이 맞습니다.

2. 복합 인덱스를 사용한 메모리 내 정렬을 방지하려면 인덱스의 첫 번째 부분이 쿼리의 동일한 부분을 충족해야 하고, 두 번째 부분은 쿼리의 정렬 부분을 충족해야 합니다(위의 (1)에 대한 설명 참조).

   다음과 같은 쿼리가 있는 경우:

   db.a.find({}).sort({a:1})
   

   인색{a:1,b:1}기본적으로 전체 컬렉션을 반환하므로 정렬 부분에 사용할 수 있습니다.쿼리가 다음과 같은 경우:

   db.a.find({a:1}).sort({b:1})
   

   {a:1,b:1}쿼리의 두 부분에도 사용할 수 있습니다.다음과 같습니다.

   db.a.find({a:1,b:1})
   

   동일한 인덱스를 사용할 수도 있습니다.{a:1,b:1}

   하세요: 여서패주십시오목하턴에기오▁here▁the▁notice시▁pattern.find()에 뒤에sort()인 매개변인순따릅다니서를 따릅니다.{a:1,b:1}따라서 복합 인덱스는 equality -> sort 순으로 정렬해야 합니다.

다른 유형의 정렬에 대한 업데이트

간에 " " " " " " " " " " " " " " " " " "a문자열은 한 문서에서, 숫자는 다른 문서에서, 부울은 다른 문서에서) 정렬은 어떻게 진행됩니까?

정답은 MongoDB BSON 유형 비교 순서입니다.매뉴얼 페이지를 바꿔 말하면, 순서는 다음과 같습니다.

1. MinKey(내부 유형)
2. Null
3. 숫자(ints, longs, double, decimal)
4. 기호, 문자열
5. 물건
6. 배열
7. BinData
8. 개체 ID
9. 부울
10. 날짜.
11. 타임스탬프
12. 정규식
13. MaxKey(내부 유형)

따라서 오름차순을 사용하는 위의 예에서 숫자를 포함하는 문서는 먼저 나타나고 문자열을 사용한 다음 부울을 사용합니다.

비록 @kevinadi가 멋진 대답을 하지만요.정렬과 함께 복합 인덱스에 대해 한 가지 더 추가합니다.

문서 몽고 인덱스별 최적 성능, 복합 인덱스 사용

ESR 규칙을 따릅니다.

복합 인덱스의 경우 이 경험칙은 인덱스의 필드 순서를 결정하는 데 유용합니다.

• 먼저 Equality 쿼리가 실행되는 필드를 추가합니다.
• 색인화할 다음 필드는 쿼리의 정렬 순서를 반영해야 합니다.
• 마지막 필드는 액세스할 데이터 범위를 나타냅니다.

그리고 알렉스는 ESR 규칙에 대해 자세히 설명합니다.

• 동일 술어를 먼저 배치해야 합니다.

동일 조건은 값을 정확하게 일치시키려고 시도하는 필터 조건입니다.예:

find({ x: 123 })
find({ x: { $eq: 123 } })
aggregate([ { $match:{ "x.y": 123 } } ])

이러한 필터는 설명 계획의 인덱스Bounds에 표시될 때 단단히 바인딩됩니다.

"indexBounds" : {
    "x" : [
        "[123.0, 123.0]"
    ]
}

여러 동일 조건 술어는 가장 선택적인 술어에서 가장 덜 선택적인 술어로 순서를 정할 필요가 없습니다.이 지침은 과거에 제공되었지만 B-Tree 인덱스의 특성 및 리프 페이지에서 B-Tree가 모든 필드 값의 조합을 저장하는 방식으로 인해 잘못된 것입니다.이와 같이 키 순서에 관계없이 정확히 동일한 수의 조합이 있습니다.

• 술어 정렬은 동등 술어를 따릅니다. 술어 정렬은 작업에 대해 요청된 전체 정렬을 나타내며 결과 순서를 결정합니다.예:

find().sort({ a: 1 })
find().sort({ b: -1, a: 1 })
aggregate([ { $sort: { b: 1 } } ])

정렬 요구 사항을 충족하기 위해 전체 키 범위를 검색해야 하므로 정렬 술어의 범위가 제한되지 않습니다.

"indexBounds" : {
    "b" : [
        "[MaxKey, MinKey]"
    ],
    "a" : [
        "[MinKey, MaxKey]"
    ]
}

• 범위 술어는 동등 및 정렬 술어를 따릅니다.

범위 술어는 정확한 일치 여부를 테스트하지 않기 때문에 여러 키를 검색할 수 있는 필터입니다.예:

find({ z: { $gte: 5} })
find({ z: { $lt: 10 } })
find({ z: { $ne: null } })

필터 요구 사항을 충족하기 위해 키 범위의 하위 집합을 스캔해야 하므로 범위 술어는 느슨하게 제한됩니다.

"indexBounds" : {
    "z" : [
        "[5.0, inf.0]"
    ]
}
"indexBounds" : {
    "z" : [
        "[-inf.0, 10.0)"
    ]
}
"indexBounds" : {
    "z" : [
        "[MinKey, undefined)",
        "(null, MaxKey]"
    ]
}

---

• 평등 우선

  선택성을 보장하는 쿼리를 만들 때 "선택성"은 인덱스를 사용하여 결과를 좁히는 쿼리의 기능임을 알게 됩니다.효과적인 인덱스는 더 선택적이며 MongoDB는 쿼리 수행과 관련된 작업의 많은 부분에 대해 인덱스를 사용할 수 있습니다.

  동일 필드는 항상 인덱스의 접두사를 형성하여 선택성을 보장해야 합니다.

• (E → S) 정렬 전 동등

  순차 동등 키 뒤에 정렬 술어를 배치하면 인덱스가 다음을 수행할 수 있습니다.

  • 비차단 정렬을 제공합니다.
  • 필요한 검색량을 최소화합니다.

• (E → R) 범위 이전의 동일성

  범위 술어는 (정렬 술어와 달리) 키의 하위 집합을 스캔하지만 키 순서가 선택에 최적화되도록 동등 술어 뒤에 배치해야 합니다.

• (S → R) 범위 전 정렬

  정렬 앞에 범위 술어가 있으면 인덱스를 사용하여 정렬 기준을 충족할 수 없으므로 차단(메모리 내) 정렬이 수행될 수 있습니다.

언급URL : https://stackoverflow.com/questions/36142299/how-does-sorting-with-an-index-work-in-mongodb