Index of ArangoDB

Index basics

인덱스는 document로 빠른 접근을 허용하는데, 주어진 인덱스 속성들이 쿼리에서 사용된다. ArangoDB는 자동으로 시스템 속성들을 인덱스하며, 사용자들은 비시스템 속성을 자유롭게 추가 인덱스로 활용할 수 있다.

사용자 정의 인덱스들은 collection 레벨에서 생성될 수 있다. 대부분의 사용자 정의 인덱스들은 특정한 인덱스 속성의 이름을 가지고 생성될 수 있다. 일부 인덱스 타입은 단 하나의 속성만 인덱스 허용하는 반면(e.g fulltext index), 여러 속성을 동시에 인덱싱하는 것을 허용하는 것도 있다.

_id, _key, _from, _to와 같은 시스템 속성은 사용자가 인덱스로 정의하지 않더라도 ArangoDB가 자동으로 인덱싱한다. _id와 _key는 collection의 primary key로 다뤄지며, _from과 _to는 edge collection의 edge index로 다뤄진다.

시스템 속성인 _id를 사용자 정의 인덱스로 사용하는 것은 불가능하지만, _key, _rev, _from, _to는 가능하다.

ArangoDB는 다음과 같은 index들을 제공한다.

Primary Index

collection에서 모든 document의 key를 위한 hash index인 primary index가 있다. primary index는 사용시 매우 빠른 검색을 가능하게 하며, _key나 _id를 사용할 때 이것을 이용한다. AQL query에서 _key나 _id로 접근할 때 역시 사용된다. 

주어진 _key 혹은 _id로 document를 검색하는 함수에서 primary index가 항상 사용된다.

db.collection.document("<document-key>");
db._document("<document-id>");

primary index는 정렬되어 있지 않은 hash index이므로, 범위 쿼리나 정렬 쿼리를 위해 사용될 수 없다.

primary index는 삭제나 변경할 수 없으며, 사용자 정의 방식의 primary index를 할 수 없다.

Edge Index

모든 edge collection은 자동으로 생성된 edge index를 가지고 있다. edge index는 _from과 _to 속성에 빠른 접근을 제공하여 vertex 사이의 연결점을 빠르게 찾는데 사용된다.이 인덱스는 vertex의 연결된 edge를 찾는 쿼리를 실행할 때 참조된다.

AQL에서 _from 또는 _to를 찾을 때 Edge index가 사용된다. 아래와 같이 주어진 _from, _to를 통해 edge를 찾는 함수는 항상 edge index를 사용한다.

db.collection.edges("<from-value>");
db.collection.edges("<to-value>");
db.collection.outEdges("<from-value>");
db.collection.outEdges("<to-value>");
db.collection.inEdges("<from-value>");
db.collection.inEdges("<to-value>");

내부적으로 edge index는 hash index로 구현이 되어 있는데 모든 _from과 _to를 저장한다. 이 index는 들여다보는데 사용할 수는 있지만, 정렬이나 범위 쿼리로 사용될 수는 없다. 또한 자동으로 생성되며, 사용자 정의에 따라 생성할 수는 없다. 그러나 사용자 정의 인덱스들에서 _from과 _to의 자유로운 사용은 가능하다.

edge index는 삭제나 변경할 수 없다.

Hash Index

hash index는 특정 속성값을 가진 document를 빠르게 찾는데 사용될 수 있다. hash index는 정렬되지 않기때문에, 검색에만 사용되고, 범위 쿼리나 정렬은 할 수 없다.

hash index는 하나 혹은 여러 document의 속성으로 생성될 수 있다. 만약 검색조건에 모든 인덱스 속성이 주어지고, 모든 속성이 동등 연산자(==)을 사용해서 비교하게 된다면 hash index가 사용될 것이다. AQL에서 byExample, firstExample과 같은 쿼리 함수에서 사용된다.

Hash index들은 선택적으로 unique로 선언될 수 있다. 그럴 경우 인덱스된 속성의 같은 값이 허용되지 않는다. 또 hash index는 sparse 선언이 가능하다.(sparse : 대부분 null이고 값을 가지는 경우가 많지 않은 경우 유리한 index) 

hash index의 타입은 아래와 같다.

• unique hash index:모든 documents들은 index된 속성 값이 유일해야 한다. unique index가 걸려 있는 속성 값이 같은 document를 insert할 경우 unique 제약 위반이 발생된다.
  이 인덱스는 sparse가 아니다. index된 속성을 가지고 있지 않거나, null 값을 가진 document는 index도 index될 것이다.(null 역시 하나만 허용한다는 의미) 따라서 optional 속성에는 이 index를 사용할 수 없다.
  unique 옵션은 _from, _to가 결합된 인덱스에 추가되어 중복된 edge 생성을 방지하는데 사용될 수 있다.
• unique, sparse hash index: unique hash index와 동일하며 추가적으로, null 값이나 속성 값이 없을 경우 index에 포함되지 않는다.
• non-unique hash index: collection의 모든 document들이 index 된다. sparse가 아니기 때문에 속성 값이 없거나 null인 것도 index되며, 중복된 값도 허용된다.
• non-unique, sparse hash index: null이 아닌 값이 있는 document 만 index된다.

unique hash index의 lookup, insert, update, remove 연산의 할부시간복잡도는 O(1)이 된다.

Non-unique hash index도 마찬가지로 O(1)이다. 

모든 혹은, 대부분의 document에서 값이 없는 속성에 hash index가 생성되면 아래와 같이 동작하게 된다.

• index가 sparse이면, 속성값이 존재하지 않는 document는 index되지 않을 것이고, 메모리 index를  사용하지 않을 것이다. 따라서, update나 remove 연산의 성능에 영향을 미치지 않을 것이다.
• sparse가 아니라면, 속성값이 없는 document들은 null key 값으로 index에 포함될 것이다.

Hash index들은 index 속성이름이 [*]를 포함한다면  배열값을 index하는 것도 지원한다.

Skiplist Index

skiplist는 정렬된 index 구조다. 범위에 대한 쿼리와 정렬된 순서로 document를 리턴하기 위한, 특정 속성 값을 빠르게 찾을 수 있다. byExample, firstExample 등에서 사용될 수 있다.

Skiplist 인덱스들은 쿼리에 인덱스 되는 속성이 주어지거나, index 속성의 prefix값이 지정될 경우 검색, 범위쿼리, 정렬에 사용될 수 있다.

예를 들어, value1과 value2로 skiplist인덱스가 생성된다면 아래의 필터 조건은 인덱스를 사용할 것이다.(<=, >=도 포함인데 밑에서는 생략되었다.)

FILTER doc.value1 == ...
FILTER doc.value1 < ...
FILTER doc.value1 > ...
FILTER doc.value1 > ... && doc.value1 < ...

FILTER doc.value1 == ... && doc.value2 == ...
FILTER doc.value1 == ... && doc.value2 > ...
FILTER doc.value1 == ... && doc.value2 > ... && doc.value2 < ...

정렬을 위해 skiplist 인덱스를 사용하기 위해서는, 인덱스 정의 순서와 동일한 순서로 SORT 구문에 속성이 명시되어야 한다. Skiplist 인덱스들은 항상 오름차순으로 생성되지만, 오름차순, 내림차순 모두에 사용될 수 있다. 그러나 복합 인덱스에서는, 복합 인덱스를 구성하는 모든 요소가 모드 오름차순이거나 모두 내림차순으로 SORT 구문에 명시되어야 한다.(기본적으로 오름차순으로 인식된다).

예를 들어, value1과 value2로 skiplist 인덱스가 생성될 때, 아래의 sort 구문은 인덱스를 사용할 수 있다.

• SORT value1 ASC, value2 ASC (and its equivalent SORT value1, value2)
• SORT value1 DESC, value2 DESC
• SORT value1 ASC (and its equivalent SORT value1)
• SORT value1 DESC

아래의 sort 구문은 인덱스가 만들어진 순서를 사용하지 않아서 추가적인 정렬 과정이 필요하게 된다.

• SORT value1 ASC, value2 DESC
• SORT value1 DESC, value2 ASC
• SORT value2 (and its equivalent SORT value2 ASC)
• SORT value2 DESC (because first indexed attribute value1 is not used in sort clause)

마지막 두 sort 구문은 인덱스 속성의 가장 좌측 prefix 속성을 사용하지 않으므로 인덱스를 사용하지 않는다.

Skiplist 역시 선택적으로 unique를 선언해서, 인덱스 되는 속성의 값을 불허할 수 잇다. sparse와 non-sparse 도 선언될 수 있다.

여러 종류의 skiplist index가 있으며 아래와 같은 특성이 있다.

• unique skiplist index: collection의 모든 document는 index되는 속성의 값이 유일하다. 이미 존재하는 속성의 document를 넣으면 제약 조건 위반을 초래한다.이 인덱스는 sparse가 아니므로 값이 없거나 null인 document들도 인덱스 된다. null value는 그래서 딱 하나의 document에서만 허용된다. 따라서 optional 속성에는 이 인덱스를 사용할 수 없다.
• unique, sparse skiplist index: unique skiplist index와 동일하지만, null값이나 속성값이 없는 document는 index하지 않는다.
• non-unique skiplist index: null이나 속성값이 없는 document도 인덱스하며, 중복이 허용된다.
• non-unique, sparse skiplist index: null이나 속성값이 없는 document는 인덱스 하지 않으며, 중복이 허용된다.

skiplist의 할부시간복잡도는 인덱스 되는 document의 개수를 N이라고 할 때 logN이 된다.

Skiplist index 역시 배열에 인덱스를 걸 수 있다.

Persistent Index

persistent index는 정렬된 인덱스로, document가 저장될 때와 업데이트 될 때 index가 disk에 쓰여져 영구 보존된다. 이는 서버가 재시작되거나, index된 collection이 초기에 로드될 때 data로부터 재생성할 필요가 없음을 의미한다. 그래서 영구 index를 사용하는 것은 collection의 로드 시간을 줄여줄 수 있다.

영구 인덱스 타입은 두 번째 인덱스로 바로 사용될 수 있다. 이것은 collection에 in-memory primary 인덱스가 항상 존재하고, 잠재적으로 edge index와 같이 더 많은 index가 있기 때문에, 영구 인덱스가 현재 collection의 유일한 인덱스로는 될 수 없음을 의미한다.

이 index의 구현은 RocksDB 엔진을 사용하며, insert, update, remove 연산을 log시간이 걸린다. 영구 index는 in-memory 인덱스가 아니기 때문에, primary index로 가는 pointer를 저장하지 않고, 대신에 document의 primary key를 저장한다. 영구 index를 통해 document를 찾을 경우, primary index를 찾는 추가적인 O(1) 시간이 필요하다.

영구 index는 정렬되어 있어서, 검색, 범위 검색, 정렬 동작에 사용될 수 있지만, query에 모든 속성이 제공되거나, 인덱스를 선언한 순서대로 속성이 나열되어야 한다.

Geo Index

사용자들은 collection에서 하나 혹은 여러 속성에 geo index를 생성할 수 있다. geo index는 장소나 지표면을 빠르게 검색하는데 사용할 수 있다.

geo index는 2차원 좌표를 저장한다. 이는 위도와 경도를 모두 포함하는 배열 속성이나 두 개의 document 속성에다가 생성될 수 있다. 위도와 경도 값은 숫자여야 한다.

geo index는 주어진 좌표와 가장 가까운 좌표를 갖는 document를 검색하는 동작을 제공하며, 주어진 좌표 주위 특정 반지름내에 존재하는 좌표를 갖는 document를 찾는 것을 제공한다.

geo index는 AQL 함수나, simple 쿼리 함수를 통해 사용되며, 다른 방법으로는 사용될 수 없다.

Fulltext Index

전체 텍스트 색인을 사용하여 문서에서 단어 또는 단어의 접두사를 찾을 수 있습니다. 전체 텍스트 색인은 하나의 속성에만 만들 수 있으며, 그 속성의 텍스트 값을 가지는 문서에 포함 된 모든 단어를 인덱싱합니다. 지정할 수 있는 최소 길이의 단어만 색인됩니다. 워드 토큰화는 libicu에서 제공하는 단어 경계 분석을 사용하여 수행되며, 서버 시작시 해당 서버의 언어를 따른다. 단어는 소문자 형태로 색인화됩니다. 이 인덱스는 완전 일치 조회 및 접두사 조회를 지원하며, 부분적인 결과를 결합하는 and, or, not 연산을 지원한다.

전체 텍스트 색인은 sparse입니다. 즉, 인덱스 속성이 설정된 문자열 값을 포함하는 문서만 인덱싱합니다. 또한 구성 가능한 최소 길이의 단어만 인덱스에 포함됩니다.
전체 텍스트 색인은 AQL의 전용 함수나 간단한 쿼리에서 사용되지만 다른 유형의 조회 및 조건에서는 사용하지 않습니다.

Indexing attributes and sub-attributes

최상위 속성뿐만 아니라 내부 속성도 인덱스 될 수 있다. 최상위 속성을 인덱싱하기 위해서는 속성 이름이 필요하다. 하나의 필드에 인덱스를 하기 위해서 ensureIndex() 메소드의 fields 파라미터에 하나의 element를 가진 배열을 기재한다. element는 인덱스하려는 속성의 이름이다. 여러 field에 걸쳐 복합 인덱스를 생성하려면 fields 배열에 나열하면 된다.

// { name: "Smith", age: 35 }
db.posts.ensureIndex({ type: "hash", fields: [ "name" ] })
db.posts.ensureIndex({ type: "hash", fields: [ "name", "age" ] })

sub속성에 인덱스를 걸기 위해서는 .(dot)를 사용하여 속성의 경로를 기재한다.

// { name: {last: "Smith", first: "John" } }
db.posts.ensureIndex({ type: "hash", fields: [ "name.last" ] })
db.posts.ensureIndex({ type: "hash", fields: [ "name.last", "name.first" ] })

Indexing array values

만약 array를 포함한 속성을 인덱스하려고 하면, ArangoDB는 기본적으로 인덱스 값으로 배열 전체를 저장한다. 배열의 각 멤버를 인덱스를 통해 접근하는 것은 이러한 방법으로는 불가능하다.

전체 배열 값을 저장하지 않고, 배열 각 멤버의 값을 인덱스하기 위해서는 특별한 배열 인덱스가 필요하다. 배열 인덱스는 collection.ensureIndex 함수를 통해 hash나 skiplist 인덱스로 설정될 수 있다. hash나 skiplist 배열 인덱스를 만들기 위해 인덱스를 생성할때 인덱스 속성명은 [*]가 추가되어야 한다.

아래는 배열 hash index를 tags 속성에 거는 예제이다.

db.posts.ensureIndex({ type: "hash", fields: [ "tags[*]" ] });
db.posts.insert({ tags: [ "foobar", "baz", "quux" ] });

이 배열 인덱스는 AQL 쿼리에서 IN 연산자를 통해 각 tags 값을 찾는데 사용될 수 있다.

FOR doc IN posts
  FILTER 'foobar' IN doc.tags
  RETURN doc

확장연산자 [*]를 추가해도 되지만 필수는 아니다. 확장 연산자를 기재하는 것은 명시적으로 array index를 사용하라는 것이지만, 명시적일뿐이다.

FOR doc IN posts
  FILTER 'foobar' IN doc.tags[*]
  RETURN doc

아래 필터 조건은 배열 인덱스를 사용하지 않음에 주의하라

FILTER doc.tags ANY == 'foobar'
FILTER doc.tags ANY IN 'foobar'
FILTER doc.tags IN 'foobar'
FILTER doc.tags == 'foobar'
FILTER 'foobar' == doc.tags

배열 값의 sub 속성에도 인덱스를 생성할 수 있다. 아래와 같이 object 배열이라면 가능한 상황이다.

db.posts.ensureIndex({ type: "hash", fields: [ "tags[*].name" ] });
db.posts.insert({ tags: [ { name: "foobar" }, { name: "baz" }, { name: "quux" } ] });

아래 쿼리는 배열 인덱스를 사용한다. 이 경우는 명시적으로 확장 연산자([*])를 기재해야 한다.

FOR doc IN posts
  FILTER 'foobar' IN doc.tags[*].name
  RETURN doc

만약 한 document가 하위 속성이 없는 element들의 집합인 배열을 가지고 있다면, 이 document는 null 값으로 인덱스 될 것이며, ArangoDB에서 이는 속성이 존재하지 않는 것과 과 같다.

ArangoDB는 배열 인덱스에 하나의 속성당 하나의 [*] 연산자만 허용한다. 예를 들어 아래는 인덱스가 가능하지 않다.

db.posts.ensureIndex({ type: "hash", fields: [ "tags[*].name[*].value" ] });

배열 인덱스 값은 자동으로 중복되지 않는다. 예를 들어 collection에 아래와 같은 document를 넣는다고 가정할 때, bar 값이 중복되지만 인덱스는 한 번만 저장된다.

db.posts.insert({ tags: [ "foobar", "bar", "bar" ] });

배열의 인덱스가 unique로 선언 된 경우 인덱스에 값을 삽입하기 전에 배열의 중복 제거가 이루어 지므로 위 삽입 작업은 실패하지 않습니다. 인덱스에 이미 bar 값의 인스턴스가 포함되어있는 경우는 실패하지만 값 bar가 인덱스에 존재하지 않는 경우는 성공합니다.

배열 인덱스가 선언되어 있고, 지정된 속성에 배열이 없는 문서를 저장하면 이 문서는 인덱스에 삽입되지 않습니다. 따라서 다음 개체는 인덱스에 등록되지 않습니다.

db.posts.ensureIndex({ type: "hash", fields: [ "tags[*]" ] });
db.posts.insert({ something: "else" });
db.posts.insert({ tags: null });
db.posts.insert({ tags: "this is no array" });
db.posts.insert({ tags: { content: [1, 2, 3] } });

배열 인덱스는 명시적인 null 값을 인덱싱 할 수 있습니다. 조회하면 배열에 명시 적으로 null이 저장되어있는 문서만 리턴할 것이며, 배열이 전혀 없는 문서는 반환되지 않습니다.

db.posts.ensureIndex({ type: "hash", fields: [ "tags[*]" ] });
db.posts.insert({tags: null}) // Will not be indexed
db.posts.insert({tags: []})  // Will not be indexed
db.posts.insert({tags: [null]}); // Will be indexed for null
db.posts.insert({tags: [null, 1, 2]}); // Will be indexed for null, 1 and 2

배열 인덱스 sparse로 선언하는 것은 인덱스의 배열 부분에는 영향을 주지 않습니다. 이것은 특히 명시적인 null값도 sparse 버전에서도 인덱스화되는 것을 의미합니다. 인덱스가 배열과 일반 속성으로 결합되어 있는 경우, 그 속성에 sparsity가 적용됩니다.

db.posts.ensureIndex({ type: "hash", fields: [ "tags[*]", "name" ], sparse: true });
db.posts.insert({tags: null, name: "alice"}) // Will not be indexed
db.posts.insert({tags: [], name: "alice"}) // Will not be indexed
db.posts.insert({tags: [1, 2, 3]}) // Will not be indexed
db.posts.insert({tags: [1, 2, 3], name: null}) // Will not be indexed
db.posts.insert({tags: [1, 2, 3], name: "alice"})
// Will be indexed for [1, "alice"], [2, "alice"], [3, "alice"]
db.posts.insert({tags: [null], name: "bob"})
// Will be indexed for [null, "bob"]

배열 인덱스를 사용한 필터링은 AQL 쿼리에서만 작동하며, 쿼리 IN 연산자를 사용하여 인덱스 속성을 필터링하는 경우에만 작동한다는 점에 유의하십시오. 현재 다른 비교 연산자 (==,! =,>,> =, <, <, ANY, ALL NONE)는 배열 인덱스를 사용할 수 없습니다.

Vertex centric indexes

위에서 언급한 바와 같이 그래프의 가장 중요한 인덱스는 에지 컬렉션 _from 속성과 _to 속성을 인덱스하는 에지 인덱스입니다. 그들은 주어진 정점에서 시작하거나 거기에 도착하는 모든 에지에 매우 빠른 액세스를 제공하여 정점의 모든 이웃을 빠르게 찾을 수 있도록 한다.

많은 경우 더 구체적인 쿼리를 실행하고 싶을 수 있습니다. 예를 들어, 타임 스탬프가 가장 최근인 20의 정점에서 시작하는 에지들을 찾을 수 있습니다. 이는 "정점 중심의 인덱스"로 얻을 수 있습니다. 어떤 의미에서는 이러한 것들은 edge 컬렉션의 지역화 된 인덱스이며, 이것은 모든 단일 정점에 위치합니다.

기술적으로는 이들은 ArangoDB에서 인덱스로 구현되어 있습니다. 이 인덱스는 먼저 _from에서 다른 속성으로 전체 edge 컬렉션을 정렬합니다. 예를 들어, 에지 컬렉션의 _from 및 타임 스탬프에 skiplist 인덱스가 있는 경우, 인덱스의 단일 범위 참조로 매우 빠르게 위의 문제를 해결할 수 있다.

ArangoDB 3.0부터는 특수 에지 속성인 _from 또는 _to와 기타 속성을 인덱스하는 정렬 된 인덱스 (유형 "skiplist"및 "persistent")을 만들 수 있습니다. ArangoDB 3.1부터는 optimizer에 의해 발견된 적절한 FILTER 구문에서 이것들이 그래프 탐색에 사용된다.

예를 들어, 위 형태의 vertex centric index를 생성하기 위해서는 아래와 같이 할 수 있다.

db.edges.ensureIndex({"type":"skiplist", "fields": ["_from", "timestamp"]});

그러면 다음과 같은 쿼리는

FOR v, e, p IN 1..1 OUTBOUND "V/1" edges
  FILTER e.timestamp >= "2016-11-09"
  RETURN p

정점 "V / 1"에서 시작하는 에지는 많지만, 최근의 타임 스탬프는 조금 밖에 존재하지 않는 경우에는 상당히 빠르게된다.