Skiplists

Introduction to Skiplist Indexes

This is an introduction to ArangoDB’s skiplists.

It is possible to define a skiplist index on one or more attributes (or paths)of documents. This skiplist is then used in queries to locate documentswithin a given range. If the skiplist is declared unique, then no two documents areallowed to have the same set of attribute values.

Creating a new document or updating a document will fail if the uniqueness is violated.If the skiplist index is declared sparse, a document will be excluded from the index and nouniqueness checks will be performed if any index attribute value is not set or has a valueof null.

Accessing Skiplist Indexes from the Shell

Unique Skiplist Index

Ensures that a unique skiplist index exists:collection.ensureIndex({ type: "skiplist", fields: [ "field1", …, "fieldn" ], unique: true })

Creates a unique skiplist index on all documents using field1, … _fieldn_as attribute paths. At least one attribute path has to be given. The index willbe non-sparse by default.

All documents in the collection must differ in terms of the indexedattributes. Creating a new document or updating an existing document willfail if the attribute uniqueness is violated.

To create a sparse unique index, set the sparse attribute to true:

collection.ensureIndex({ type: "skiplist", fields: [ "field1", …, "fieldn" ], unique: true, sparse: true })

In a sparse index all documents will be excluded from the index that do notcontain at least one of the specified index attributes or that have a valueof null in any of the specified index attributes. Such documents willnot be indexed, and not be taken into account for uniqueness checks.

In a non-sparse index, these documents will be indexed (for non-presentindexed attributes, a value of null will be used) and will be taken intoaccount for uniqueness checks.

In case that the index was successfully created, an object with the indexdetails, including the index-identifier, is returned.

arangosh> db.ids.ensureIndex({ type: "skiplist", fields: [ "myId" ], unique: true });
arangosh> db.ids.save({ "myId": 123 });
arangosh> db.ids.save({ "myId": 456 });
arangosh> db.ids.save({ "myId": 789 });
arangosh> db.ids.save({ "myId": 123 });

Show execution results

{ 
  "deduplicate" : true, 
  "fields" : [ 
    "myId" 
  ], 
  "id" : "ids/73966", 
  "isNewlyCreated" : true, 
  "selectivityEstimate" : 1, 
  "sparse" : false, 
  "type" : "skiplist", 
  "unique" : true, 
  "code" : 201 
}
{ 
  "_id" : "ids/73968", 
  "_key" : "73968", 
  "_rev" : "_ZP4PUBm---" 
}
{ 
  "_id" : "ids/73970", 
  "_key" : "73970", 
  "_rev" : "_ZP4PUBq---" 
}
{ 
  "_id" : "ids/73972", 
  "_key" : "73972", 
  "_rev" : "_ZP4PUBu---" 
}
[ArangoError 1210: unique constraint violated - in index 73966 of type rocksdb-skiplist over ["myId"]; conflicting key: 73968]

Hide execution results

arangosh> db.ids.ensureIndex({ type: "skiplist", fields: [ "name.first", "name.last" ], unique: true });
arangosh> db.ids.save({ "name" : { "first" : "hans", "last": "hansen" }});
arangosh> db.ids.save({ "name" : { "first" : "jens", "last": "jensen" }});
arangosh> db.ids.save({ "name" : { "first" : "hans", "last": "jensen" }});
arangosh> db.ids.save({ "name" : { "first" : "hans", "last": "hansen" }});

Show execution results

{ 
  "deduplicate" : true, 
  "fields" : [ 
    "name.first", 
    "name.last" 
  ], 
  "id" : "ids/73948", 
  "isNewlyCreated" : true, 
  "selectivityEstimate" : 1, 
  "sparse" : false, 
  "type" : "skiplist", 
  "unique" : true, 
  "code" : 201 
}
{ 
  "_id" : "ids/73950", 
  "_key" : "73950", 
  "_rev" : "_ZP4PUAS---" 
}
{ 
  "_id" : "ids/73952", 
  "_key" : "73952", 
  "_rev" : "_ZP4PUAS--A" 
}
{ 
  "_id" : "ids/73954", 
  "_key" : "73954", 
  "_rev" : "_ZP4PUAW---" 
}
[ArangoError 1210: unique constraint violated - in index 73948 of type rocksdb-skiplist over ["name.first","name.last"]; conflicting key: 73950]

Hide execution results

Non-unique Skiplist Index

Ensures that a non-unique skiplist index exists:collection.ensureIndex({ type: "skiplist", fields: [ "field1", …, "fieldn" ] })

Creates a non-unique skiplist index on all documents using field1, …fieldn as attribute paths. At least one attribute path has to be given.The index will be non-sparse by default.

To create a sparse non-unique index, set the sparse attribute to true.

collection.ensureIndex({ type: "skiplist", fields: [ "field1", …, "fieldn" ], sparse: true })

In case that the index was successfully created, an object with the indexdetails, including the index-identifier, is returned.

arangosh> db.names.ensureIndex({ type: "skiplist", fields: [ "first" ] });
arangosh> db.names.save({ "first" : "Tim" });
arangosh> db.names.save({ "first" : "Tom" });
arangosh> db.names.save({ "first" : "John" });
arangosh> db.names.save({ "first" : "Tim" });
arangosh> db.names.save({ "first" : "Tom" });

Show execution results

{ 
  "deduplicate" : true, 
  "fields" : [ 
    "first" 
  ], 
  "id" : "names/73822", 
  "isNewlyCreated" : true, 
  "selectivityEstimate" : 1, 
  "sparse" : false, 
  "type" : "skiplist", 
  "unique" : false, 
  "code" : 201 
}
{ 
  "_id" : "names/73824", 
  "_key" : "73824", 
  "_rev" : "_ZP4PT4q---" 
}
{ 
  "_id" : "names/73826", 
  "_key" : "73826", 
  "_rev" : "_ZP4PT4u---" 
}
{ 
  "_id" : "names/73828", 
  "_key" : "73828", 
  "_rev" : "_ZP4PT4u--A" 
}
{ 
  "_id" : "names/73830", 
  "_key" : "73830", 
  "_rev" : "_ZP4PT4y---" 
}
{ 
  "_id" : "names/73832", 
  "_key" : "73832", 
  "_rev" : "_ZP4PT42---" 
}

Hide execution results

Skiplist Array Index

Ensures that a skiplist array index exists (non-unique):collection.ensureIndex({ type: "skiplist", fields: [ "field1[]", …, "fieldn[]" ] })

Creates a non-unique skiplist array index for the individual elements of the arrayattributes field1[], … fieldn[] found in the documents. At leastone attribute path has to be given. The index always treats the indexed arrays assparse.

It is possible to combine array indexing with standard indexing:collection.ensureIndex({ type: "skiplist", fields: [ "field1[*]", "field2" ] })

In case that the index was successfully created, an object with the indexdetails, including the index-identifier, is returned.

arangosh> db.test.ensureIndex({ type: "skiplist", fields: [ "a[*]" ] });
arangosh> db.test.save({ a : [ 1, 2 ] });
arangosh> db.test.save({ a : [ 1, 3 ] });
arangosh> db.test.save({ a : null });

Show execution results

{ 
  "deduplicate" : true, 
  "fields" : [ 
    "a[*]" 
  ], 
  "id" : "test/73842", 
  "isNewlyCreated" : true, 
  "selectivityEstimate" : 1, 
  "sparse" : false, 
  "type" : "skiplist", 
  "unique" : false, 
  "code" : 201 
}
{ 
  "_id" : "test/73844", 
  "_key" : "73844", 
  "_rev" : "_ZP4PT52---" 
}
{ 
  "_id" : "test/73846", 
  "_key" : "73846", 
  "_rev" : "_ZP4PT56---" 
}
{ 
  "_id" : "test/73848", 
  "_key" : "73848", 
  "_rev" : "_ZP4PT56--A" 
}

Hide execution results

Query by example using a skiplist index

Constructs a query-by-example using a skiplist index:collection.byExample(example)

Selects all documents from the collection that match the specified exampleand returns a cursor. A skiplist index will be used if present.

You can use toArray, next, or hasNext to access theresult. The result can be limited using the skip and _limit_operator.

An attribute name of the form a.b is interpreted as attribute path,not as attribute. If you use

{ "a" : { "c" : 1 } }

as example, then you will find all documents, such that the attributea contains a document of the form {c : 1 }. For example the document

{ "a" : { "c" : 1 }, "b" : 1 }

will match, but the document

{ "a" : { "c" : 1, "b" : 1 } }

will not.

However, if you use

{ "a.c" : 1 },

then you will find all documents, which contain a sub-document in a_that has an attribute _c of value 1. Both the following documents

{ "a" : { "c" : 1 }, "b" : 1 }

and

{ "a" : { "c" : 1, "b" : 1 } }

will match.