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/74807", 
  7.   "isNewlyCreated" : true, 
  8.   "name" : "idx_1642473901018578946", 
  9.   "selectivityEstimate" : 1, 
  10.   "sparse" : false, 
  11.   "type" : "skiplist", 
  12.   "unique" : true, 
  13.   "code" : 201 
  14. }
  15. { 
  16.   "_id" : "ids/74811", 
  17.   "_key" : "74811", 
  18.   "_rev" : "_ZJNS8NG---" 
  19. }
  20. { 
  21.   "_id" : "ids/74813", 
  22.   "_key" : "74813", 
  23.   "_rev" : "_ZJNS8NG--A" 
  24. }
  25. { 
  26.   "_id" : "ids/74815", 
  27.   "_key" : "74815", 
  28.   "_rev" : "_ZJNS8NG--C" 
  29. }
  30. [ArangoError 1210: unique constraint violated - in index idx_1642473901018578946 of type skiplist over 'myId'; conflicting key: 74811]

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/74788", 
  8.   "isNewlyCreated" : true, 
  9.   "name" : "idx_1642473901013336066", 
  10.   "selectivityEstimate" : 1, 
  11.   "sparse" : false, 
  12.   "type" : "skiplist", 
  13.   "unique" : true, 
  14.   "code" : 201 
  15. }
  16. { 
  17.   "_id" : "ids/74792", 
  18.   "_key" : "74792", 
  19.   "_rev" : "_ZJNS8My---" 
  20. }
  21. { 
  22.   "_id" : "ids/74794", 
  23.   "_key" : "74794", 
  24.   "_rev" : "_ZJNS8My--A" 
  25. }
  26. { 
  27.   "_id" : "ids/74796", 
  28.   "_key" : "74796", 
  29.   "_rev" : "_ZJNS8My--C" 
  30. }
  31. [ArangoError 1210: unique constraint violated - in index idx_1642473901013336066 of type skiplist over 'name.first, name.last'; conflicting key: 74792]

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/74444", 
  7.   "isNewlyCreated" : true, 
  8.   "name" : "idx_1642473900946227200", 
  9.   "selectivityEstimate" : 1, 
  10.   "sparse" : false, 
  11.   "type" : "skiplist", 
  12.   "unique" : false, 
  13.   "code" : 201 
  14. }
  15. { 
  16.   "_id" : "names/74448", 
  17.   "_key" : "74448", 
  18.   "_rev" : "_ZJNS8Iu--_" 
  19. }
  20. { 
  21.   "_id" : "names/74450", 
  22.   "_key" : "74450", 
  23.   "_rev" : "_ZJNS8Iu--B" 
  24. }
  25. { 
  26.   "_id" : "names/74452", 
  27.   "_key" : "74452", 
  28.   "_rev" : "_ZJNS8Iy---" 
  29. }
  30. { 
  31.   "_id" : "names/74454", 
  32.   "_key" : "74454", 
  33.   "_rev" : "_ZJNS8Iy--A" 
  34. }
  35. { 
  36.   "_id" : "names/74456", 
  37.   "_key" : "74456", 
  38.   "_rev" : "_ZJNS8Iy--C" 
  39. }

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/74465", 
  7.   "isNewlyCreated" : true, 
  8.   "name" : "idx_1642473900951470080", 
  9.   "selectivityEstimate" : 1, 
  10.   "sparse" : false, 
  11.   "type" : "skiplist", 
  12.   "unique" : false, 
  13.   "code" : 201 
  14. }
  15. { 
  16.   "_id" : "test/74469", 
  17.   "_key" : "74469", 
  18.   "_rev" : "_ZJNS8JC--_" 
  19. }
  20. { 
  21.   "_id" : "test/74471", 
  22.   "_key" : "74471", 
  23.   "_rev" : "_ZJNS8JG---" 
  24. }
  25. { 
  26.   "_id" : "test/74473", 
  27.   "_key" : "74473", 
  28.   "_rev" : "_ZJNS8JG--A" 
  29. }

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.

Creating Skiplist Index in Background

This section only applies to the rocksdb storage engine

Creating new indexes is by default done under an exclusive collection lock. This meansthat the collection (or the respective shards) are not available as long as the indexis created. This “foreground” index creation can be undesirable, if you have to perform iton a live system without a dedicated maintenance window.

Indexes can also be created in “background”, not using an exclusive lock during the creation. The collection remains available, other CRUD operations can run on the collection while the index is created.This can be achieved by using the inBackground option.

To create a Skiplist index in the background in arangosh just specify inBackground: true:

  1. db.collection.ensureIndex({ type: "skiplist", fields: [ "value" ], inBackground: true });

For more information see “Creating Indexes in Background” in the Index basics page.