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.

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

Show execution results

  1. { 
  2.   "deduplicate" : true, 
  3.   "fields" : [ 
  4.     "myId" 
  5.   ], 
  6.   "id" : "ids/16443", 
  7.   "isNewlyCreated" : true, 
  8.   "sparse" : false, 
  9.   "type" : "skiplist", 
  10.   "unique" : true, 
  11.   "code" : 201 
  12. }
  13. { 
  14.   "_id" : "ids/16446", 
  15.   "_key" : "16446", 
  16.   "_rev" : "_ZHpYtFm--_" 
  17. }
  18. { 
  19.   "_id" : "ids/16450", 
  20.   "_key" : "16450", 
  21.   "_rev" : "_ZHpYtFm--B" 
  22. }
  23. { 
  24.   "_id" : "ids/16453", 
  25.   "_key" : "16453", 
  26.   "_rev" : "_ZHpYtFm--D" 
  27. }
  28. [ArangoError 1210: unique constraint violated - in index 16443 of type skiplist over ["myId"]; conflicting key: 16446]

Hide execution results

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

Show execution results

  1. { 
  2.   "deduplicate" : true, 
  3.   "fields" : [ 
  4.     "name.first", 
  5.     "name.last" 
  6.   ], 
  7.   "id" : "ids/16424", 
  8.   "isNewlyCreated" : true, 
  9.   "sparse" : false, 
  10.   "type" : "skiplist", 
  11.   "unique" : true, 
  12.   "code" : 201 
  13. }
  14. { 
  15.   "_id" : "ids/16427", 
  16.   "_key" : "16427", 
  17.   "_rev" : "_ZHpYtCi--_" 
  18. }
  19. { 
  20.   "_id" : "ids/16431", 
  21.   "_key" : "16431", 
  22.   "_rev" : "_ZHpYtCm--_" 
  23. }
  24. { 
  25.   "_id" : "ids/16434", 
  26.   "_key" : "16434", 
  27.   "_rev" : "_ZHpYtCm--B" 
  28. }
  29. [ArangoError 1210: unique constraint violated - in index 16424 of type skiplist over ["name.first","name.last"]; conflicting key: 16427]

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.

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

Show execution results

  1. { 
  2.   "deduplicate" : true, 
  3.   "fields" : [ 
  4.     "first" 
  5.   ], 
  6.   "id" : "names/16290", 
  7.   "isNewlyCreated" : true, 
  8.   "sparse" : false, 
  9.   "type" : "skiplist", 
  10.   "unique" : false, 
  11.   "code" : 201 
  12. }
  13. { 
  14.   "_id" : "names/16293", 
  15.   "_key" : "16293", 
  16.   "_rev" : "_ZHpYst2--_" 
  17. }
  18. { 
  19.   "_id" : "names/16297", 
  20.   "_key" : "16297", 
  21.   "_rev" : "_ZHpYst2--B" 
  22. }
  23. { 
  24.   "_id" : "names/16300", 
  25.   "_key" : "16300", 
  26.   "_rev" : "_ZHpYst6--_" 
  27. }
  28. { 
  29.   "_id" : "names/16303", 
  30.   "_key" : "16303", 
  31.   "_rev" : "_ZHpYst6--B" 
  32. }
  33. { 
  34.   "_id" : "names/16306", 
  35.   "_key" : "16306", 
  36.   "_rev" : "_ZHpYsu---_" 
  37. }

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.

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

Show execution results

  1. { 
  2.   "deduplicate" : true, 
  3.   "fields" : [ 
  4.     "a[*]" 
  5.   ], 
  6.   "id" : "test/16313", 
  7.   "isNewlyCreated" : true, 
  8.   "sparse" : false, 
  9.   "type" : "skiplist", 
  10.   "unique" : false, 
  11.   "code" : 201 
  12. }
  13. { 
  14.   "_id" : "test/16316", 
  15.   "_key" : "16316", 
  16.   "_rev" : "_ZHpYsw2--_" 
  17. }
  18. { 
  19.   "_id" : "test/16320", 
  20.   "_key" : "16320", 
  21.   "_rev" : "_ZHpYsw6--_" 
  22. }
  23. { 
  24.   "_id" : "test/16323", 
  25.   "_key" : "16323", 
  26.   "_rev" : "_ZHpYsw6--B" 
  27. }

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

  1. { "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

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

will match, but the document

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

will not.

However, if you use

  1. { "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

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

and

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

will match.