Skip to main content

Fluree Indexing

Overview​

This guide is a work in progress, additional details will be added.

Flakes are placed into up to 4 indexes (+ optionally a Lucene index if full text searching is used). The guide about Flakes describes in more detail the anatomy of a Flake and how it is used, which can help greatly when understanding indexes. In summary, a Flake is a 6-tuple that contains a subject ID (s), predicate ID (p), object/value (o), a reference to the transaction/time it was created at (t), the boolean operation of adding or retracting the flake (op) and optional metadata (m).

Indexes are labeled based on the sort order of the Flakes. The four indexes are:

  • spot - subject, predicate, object, time - contains all Flakes
  • psot - predicate, subject, object, time - contains all Flakes
  • post - predicate, object, subject, time - contains indexed Flakes
  • opst - object, predicate, subject, time - contains reference Flakes

Every query is broken into one or more statements which is executed in order. Each query statement, depending on the missing variables within it, goes to one of the above indexes to fill in the result.

spot is used to find information about a subject quickly - and requires you know the subject ahead of time. psot is the "column database" index - and allow you to quickly find all subjects that have a specific predicate. post is only used for Flakes with predicates defined as being indexed (defined as index: true, unique: true, along with a couple other cases). This allows you to quickly find an indexed value (object) for a known predicate. opst is only used for Flakes with a reference (join) predicate defined as type: ref. This index allows reverse graph crawls, i.e. spot would be use to find everyone that Jane 'follows', but opst would be used to find everyone that 'follows' Jane. As a graph, relationships automatically can be traversed in both directions and the reverse direction is the job of opst.

Immutable Indexes​

Fluree uses immutable data structures to do what it does efficiently - everything is shared, nothing is copied. When Fluree is working through slices of time, each time is just a delta sitting on top of some reference time - and the common Flakes are all shared via pointers in memory.

Say you wanted to see the results of a query as of midnight for every day of the year, for the past 3 years. That is technically over 1,000 distinct databases you'd be querying. While you get the benefit of it seeming like you can query 1,000 distinct backups of your db, the machine is just representing deltas against some reference time - and a Flake is never duplicated. The actual impact of this might be a 5% increase in memory, not the 1,000x one might think it would require.

It is extradorinarily efficient, and an end-user should never have to concern themselves with querying a ledger as of current or historical times.

Once an index segment is loaded from disk and in memory, Fluree uses an immutable AVL tree that will be pivoted and filtered based on time (t) and ultimately the user's permissions as controlled by SmartFunctions. Every alternate view into this index segment builds on top the closest calculated representation and only consumes the memory resources consisting of diffs in terms of pointers to Flakes. Representations that are not longer used are thrown away via an LRU cache, so Fluree won't consume more resources than it is given.

Persisted Indexes​

While the prior section focused on index data that resides in-memory, as a data platform that guarantees ACID compliance Fluree must durably persist that data to storage. Fluree's model for this combines immutable persisted data files that roughly represent nodes in a B-tree. Fluree has an abstracted storage protocol that requires just a few simple storage operations, so long as there is a durability guarantee and therefore does not break the 'D' in ACID. Today Fluree supported storage backends are the local file system (default), AWS S3, or in-memory which is primarily used for testing and short-lived database needs.

All of Fluree indexes are immutable when persistently stored - meaning once the index file is written to storage it will never be updated, but it may be deleted (garbage collected) once no longer in use. Re-indexing data can take time, and for that reason Fluree does this in the background and only periodically. Fluree triggers reindexing jobs based on the settings fdb-memory-reindex and fdb-memory-reindex-max, giving Fluree operators control over this process. Reasonable defaults for these values are always maintained, and most Fluree operators will not need to concern themselves with this.

As new transactions happen against a ledger, the results of the transactions are Flakes, which are the deltas from the prior version of the ledger. The result of applying the Flakes from a transaction result to the prior state is a new immutable database. New Flakes are streamed to query servers up-stream (and permissioned in the process) where the query servers store these deltas in-memory and merge them into any persisted immutable indexes being used locally to satisfy queries. This process continues until the size of the Flakes from new transactions is >= to fdb-memory-reindex which will trigger a new persistent indexing process in the background

Persisted index files are designed to stay around 100kb each with each file being a node from a balanced tree (b-tree). The root and all branch nodes point to the children nodes and so on down to the leaf nodes, which contain the raw Flake data. New Flakes from transactions get pushed into the the leaf nodes where they belong (based on sort order, so spot, psot, post, and opst) and nodes will split if they exceed 100kb. Because new Flakes will likely end up in a minimal set of leaf nodes, only those nodes are updated, along with their parents (branch nodes), meaning any index node not affected by new data remains untouched and can also remain active in any upstream cache.

The immutability guarantee around the storage, combined with the Fluree's Flake partitioning strategy minimizes the number of affected index nodes as new transaction Flakes are applied. This gives Fluree the ability to linearly scale its query servers while allowing them to effectively run at in-memory speeds -- even with a fraction of memory that the entire database consumes.

spot Index​

Simplifying a Flake to just s, p and o, consider the following 3-tuple Flakes which are sorted in spo order:

;; s     p          o 
;;-----------------------------
 [88 'company'   'ACME Inc"    ]
 [26 'firstName' 'John'        ]
 [26 'follows'    25           ]
 [26 'lastName'  'Smith'       ]
 [26 'username'  'jsmith'      ]
 [25 'email'     'jane@doe.com']
 [25 'firstName' 'Jane'        ]
 [25 'lastName'  'Doe'         ]
 [25 'username'  'janedoe'     ]

Note that the s value is sorted in descending order. This sort order means the most recently added subjects are always going to come first based on how Fluree partitions data within a collection. Therefore, the query of {"select": ["*"], "from": "person", "limit": 10} would return the 10 most recently added people without requring any additional sorting.

You can see from the above Flakes that the following questions could be answered very quickly based on the corresponding match pattern:

Question: Tell me everything about John Smith

Query:

// Fluree will lookup ["username", "jsmith"] and resolve it to s = 26
 {"select": ["*"], 
 "from": ["username", "jsmith"]}

 // or, if the subject ID was already known:
{"select": ["*"], 
 "from": 26}

Match Pattern:

= [26 ? ?]

Filtered Flakes:

[26 'firstName' 'John'  ]
[26 'follows'    25     ]
[26 'lastName'  'Smith' ]
[26 'username'  'jsmith']

Question: Tell me who John Smith follows

Query:

{"select": ["?following"], 
 "where": [[26 "follows" "?following"]]}

 // or, could write as:
{"select": ["?following"], 
 "where": [[["username", "jsmith"], "follows", "?following"]]}

 // or, could write as:
 {"select": ["?following"], 
 "where": [["?john", "username", "jsmith"],
           ["?john", "follows",  "?following"]]}

Match Pattern:

= [26 'follows' ?]

Filtered Flakes:

[26 'follows'    25] ;; John follows the subject id 25 (Jane)

psot Index​

The psot index helps answer questions related to finding subjects that contain a specific predicate.

While technically the Flake is not rearranged for any of the index sort orders, we rearrange it below to help illustrate.

;;   p       s     o 
;;-----------------------------
['company'   88 'ACME Inc"    ]
['email'     25 'jane@doe.com']
['firstName' 26 'John'        ]
['firstName' 25 'Jane'        ]
['follows'   26  25           ]
['lastName'  26 'Smith'       ]
['lastName'  25 'Doe'         ]
['username'  26 'jsmith'      ]
['username'  25 'janedoe'     ]

post Index​

The post index includes only flakes that whose predicate is unique: true, index: true, and also include all refs type: ref.

;;   p           o          s 
;;-----------------------------
['company'   'ACME Inc"     88]
['email'     'jane@doe.com' 25]
['firstName' 'Jane'         25]
['firstName' 'John'         26]
['follows'    25            26]
['lastName'  'Doe'          25]
['lastName'  'Smith'        26]
['username'  'janedoe'      25]
['username'  'jsmith'       26]

You can see this index would be able to quickly find any predicate's value. When using a Subject Identity to reference a subject in Fluree this is the index that would be used.

For example, if I was looking for the s value for the Subject Identity of ["username", "janedoe"], the corresponding match pattern would be:

= ['username' 'janedoe' ?]

You can see this index could quickly give the you answer: s = 25.

Range scans are also possible with this and an other index. Particularly useful here might be to find all 'firstName' values that start with "J". Such a match pattern would look like:

start: >= ['firstName' 'J' ?] 
end:    < ['firstName' 'K' ?]

Here we've introduced a range scan. Technically every index match, even the = match we have been using previously, returns a range of matching values.

opst Index​

The opst index only contains Flakes with reference predicates (type: ref), and is used to crawl the graph in reverse order.

;; o    p      s 
;;----------------
 [25 'follows' 26]

Our sample data set only contains a single ref Flake, but note that this index is a flip of the s and o values from our primary spot index. If we wanted to know who John Smith follows, the spot index gives us the quick answer that John (26) follows Jane (25). But what if I want to know who is following Jane, which is the reverse question. opst would answer this question quickly with the match expression:

= [25 'follows' ?] ; Jane = 25, John = 26

You see this index quickly is able to tell us that the subject _id of 26 follows Jane, which is John. If Jane had multiple people following her there would be multiple values returned from this match.