FQL

/user/index/surname("Johnson",<userID:int>)
/user(:userID,...)

/user(9323,"Timothy","Johnson",37)=nil
/user(24335,"Andrew","Johnson",42)=nil
/user(33423,"Ryan","Johnson",0x0ffa83,42.2)=nil

FQL is an open source query language for FoundationDB. It’s query semantics mirror FoundationDB’s core data model. Fundamental patterns like range-reads and indirection are first class citizens.

• Introduction
• Syntax
  • Overview
  • Data Elements
  • Names
  • Directories
  • Holes & References
  • Space & Comments
  • Options
• Semantics
  • Data Encoding
    • Keys
    • Values
    • Empty Values
  • Query Types
    • Reads & Writes
    • Directories
    • Options
    • Filtering
  • Advanced Queries
    • Indirection
    • Aggregation
• Implementations
  • Connection
  • Permissions
  • Transactions
  • Variables & References
  • Extensions
  • Formatting
• Grammar

Introduction

This document serves as both a language specification and a usage guide for FQL. The Syntax section describes the structure of queries while the Semantics section describes their behavior. The Implementations section highlights features which are not included in FQL but may be defined by a particular implementation. The complete EBNF grammar appears at the end.

Throughout the document, relevant grammar rules are shown alongside the features they define. Python code snippets are also included demonstrating equivalent FoundationDB API calls.

Grammar rules use extended Backus-Naur form as defined in ISO/IEC 14977, with a modification: concatenation and rule termination are implicit.

❗Not all features described in this document have been implemented yet. See the project’s issues for a roadmap of implemantation plans.

Syntax

Overview

FQL is specified as a context-free grammar. The queries look like key-values encoded using the directory and tuple layers. To the left of the = is the key which includes a directory path and tuple. To the right is the value.

query = [ opts '\n' ] ( keyval | key | dquery )
dquery = directory [ '=' 'remove' ]
keyval = key '=' value
key = directory tuple
value = 'clear' | data

For now, the opts prefixing the query can be ignored. Options will be described later in the document. A query may be a full key-value, just a key, or a directory query.

/my/directory("my","tuple")=4000

FQL queries may define a single key-value to be written, as shown above, or may define a set of key-values to be read, as shown below.

/my/directory("my","tuple")=<int>

/my/directory("my","tuple")=4000

The query above has the variable <int> as its value. Variables act as placeholders for any of the supported data elements.

FQL queries may also perform range reads and filtering by including on or more variables in the key. The query below will return all key-values which conform to the schema defined by the query.

/my/directory(<>,"tuple")=nil

/my/directory("your","tuple")=nil
/my/directory(42,"tuple")=nil

The variable <> in the query above lacks a type. This means the schema allows any data element at the variable’s position.

All key-values with a certain key prefix may be range read by ending the tuple with ....

/my/directory("my","tuple",...)=<>

/my/directory("my","tuple")=0x0fa0
/my/directory("my","tuple",47.3)=0x8f3a
/my/directory("my","tuple",false,0xff9a853c12)=nil

A query’s value may be omitted to imply the variable <>, meaning the following query is semantically identical to the one above.

/my/directory("my","tuple",...)

/my/directory("my","tuple")=0x0fa0
/my/directory("my","tuple",47.3)=0x8f3a
/my/directory("my","tuple",false,0xff9a853c12)=nil

Including a variable in the directory path tells FQL to perform the read on all directory paths matching the schema.

/<>/directory("my","tuple")

/my/directory("my","tuple")=0x0fa0
/your/directory("my","tuple")=nil

Key-values may be cleared by using the special clear token as the value.

/my/directory("my","tuple")=clear

The directory layer may be queried by only including a directory path.

/my/<>

/my/directory

Directories are not explicitly created. During a write query, the directory is created if it doesn’t exist. Directories may be removed by suffixing the directory path with =remove.

/my/dir=remove

Data Elements

An FQL query contains instances of data elements. These mirror the types of elements found in the tuple layer. This section will describe how data elements behave in the FQL language, while element encoding describes how FQL encodes the elements before writing them to the DB.

The nil type may only be instantiated as the element nil. The bool type may be instantiated as true or false.

bool = 'true' | 'false'

The int type may be instantiated as any arbitrarily large integer.

int = [ '-' ] digits
digits = digit { digit }
digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

The num type may be instantiated as any real number which can be approximated by an 80-bit floating point value, in accordance with IEEE 754. The implementation determines the exact range of allowed values. Scientific notation may be used. As expressed in the above specification, the type may be instantiated as -inf, inf, -nan or nan.

num = int '.' digits | ( int | int '.' digits ) 'e' int | '-inf' | 'inf' | '-nan' | 'nan'

The str type may be instantiated as a unicode string wrapped in double quotes. Quoted strings may contain double quotes and backslashes via backslash escapes.

string = '"' { char | '\\"' | '\\\\' } '"'

The uuid and bytes types may be instantiated using upper, lower, or mixed case hexidecimal numbers. For uuid, the numbers are grouped in the standard 8, 4, 4, 4, 12 format. For bytes, any even number of hexidecimal digits are prefixed by 0x.

uuid = hex{8} '-' hex{4} '-' hex{4} '-' hex{4} '-' hex{12}
bytes = '0x' { hex hex }
hex = digit | 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'A' | 'B' | 'C' | 'D' | 'E' | 'F'

The tup type may contain any of the data elements, including nested tuples. Elements are separated by commas and wrapped in parentheses. A trailing comma is allowed after the last element. The last element may be the ... token (see holes).

tuple = '(' [ nl elements [ ',' ] nl ] ')'
elements = data [ ',' nl elements ] | '...'

The vstamp type represents a FoundationDB versionstamp. A versionstamp contains a 10-byte transaction version and a 2-byte user version. The transaction version is assigned by the database at commit time. A vstamp without the transaction version (only the user version after the colon) is incomplete and will be filled in by FoundationDB when written.

vstamp = '#' [ hex{20} ] ':' hex{4}

Names

Names are a syntactic construct used throughout FQL. The are not a data element because they are usually not serialized and written to the database. They are used in many contexts including directories, options, and variables.

name = ( letter | '_' ) { letter | digit | '_' | '-' | '.' }

A name must start with a letter or underscore, followed by any combination of letters, digits, underscores, dashes, or periods.

Directories

Directories provide a way to organize key-values into hierarchical namespaces. The directory layer manages these namespaces and maps each path to a short key prefix. Strings are the only element type allowed in directories.

directory = '/' element [ directory ]
element = '<>' | name | string

A directory is specified as a sequence of strings, each prefixed by a forward slash. If the string only uses characters allowed in a name, the quotes may be excluded.

/my/dir/path_way
/my/"dir@--\o/"/path_way

The empty variable <> may be used in a directory path as a placeholder for any directory name.

/root/<>/items

/root/good/items
/root/bad/items
/root/weird/items

Holes & References

Holes are a group of syntax constructs used to define a key-value schema by acting as placeholders for one or more data elements. There are two kinds of holes: variables and the ... token.

variable = '<' [ name ':' ] [ type { '|' type } ] '>'
type = 'any' | 'tuple' | 'bool' | 'int' | 'num' | 'str' | 'uuid' | 'bytes' | 'vstamp'

Variables are used to represent a single data element. Variables may optionally include a name before the type list. Variables are specified as a list of element types, separated by |, wrapped in angled braces.

<int|str|uuid|bytes>

The variable’s type list describes which kinds of data elements are allowed at the variable’s position. A variable may be empty, including no element types, meaning it allows any element type.

/data(<int>,<str|int>,<>)=<>

/data(0,"jon",0xffab0c)=nil
/data(20,3,22.3)=0xff
/data(21,"",nil)=nil

The ... token represents any number of data elements of any type. It is only allowed as the last element of a tuple.

/tuples(0x00,...)

/tuples(0x00)=nil
/tuples(0x00,"something")=nil
/tuples(0x00,42,43,44)=0xabcf

References allow two queries to be connected via a variable’s name, allowing for index indirection. Before the type list, a variable may include a name. The reference is specified as a variable’s name prefixed with a :.

reference = ':' name [ '!' type ]

/index("car makes",<makeID:int>)
/data(:makeID,...)

/data(33,"mazda")=nil
/data(320,"ford")=nil
/data(411,"chevy")=nil

Named variables must include at least one type. To allow named variables to match all element type, use the any type.

/stuff(<thing:any>)

/stuff("cat")
/stuff(42)
/stuff(0x5fae)

References may include a type cast by appending ! followed by a type name. This converts the referenced value to the specified type.

:myVar!str

The example above typecasts the value of :myVar to type str. Type casting is useful when a variable’s type differs from how it needs to be used in a subsequent query.

/ids(<id:int>)
/data(:id!str,...)

In the example above, the <id:int> variable is defined as an int but is cast to str when used as a reference.

Type casts that fail at runtime (e.g., parsing a non-numeric string as int) will cause the query to error.

Space & Comments

Whitespace and newlines are allowed within a tuple, between its elements. Trailing commas are also permitted.

/account/private(
  <int>,
  <int>,
  <str>,
)=<int>

Comments start with a % and continue until the end of the line. They can be used to document a tuple’s elements.

% private account balances
/account/private(
  <int>,  % group ID
  <int>,  % account ID
  <str>,  % account name
)=<int>   % balance in USD

Options

Options modify the semantics of data elements, variables, and queries. They can instruct FQL to use alternative encodings, limit a query’s result count, or change other behaviors.

options = '[' option { ',' option } ']'
option = name [ ':' argument ]
argument = name | int | string

Options are specified as a comma separated list wrapped in brackets. For instance, to specify that an int should be encoded as a little-endian unsigned 8-bit integer, the following options would be included after the element.

3548[u8]

Similarly, if a variable should only match against big-endian 32-bit floats then the following options would be included after the num type.

<num[f32,be]>

Query options are specified on the line before the query. For instance, to specify that a range-read query should read in reverse and only read 5 items, the following options would be included before the query.

[reverse,limit:5]
/my/integers(<int>)=nil

Notice that the limit option includes a number after the colon. Some options include a single argument to further specify the option’s behavior.

Semantics

Data Encoding

FoundationDB stores the keys and values as simple byte strings leaving the client responsible for encoding the data. FQL determines how to encode data elements based on their data type, position within the query, and associated options.

Keys

Keys are always encoded using the directory and tuple layers. Write queries create directories if they do not exist.

/directory/"p@th"(nil,57223,0xa8ff03)=nil

@fdb.transactional
def write_kv(tr):
    # Open directory; create if doesn't exist
    dir = fdb.directory.create_or_open(tr, ('directory', 'p@th'))

    # Pack the tuple and prepend the directory prefix
    key = dir.pack((None, 57223, b'\xa8\xff\x03'))

    # Write the KV
    tr[key] = b''

If a query reads from a directory which doesn’t exist, nothing is returned. The tuple layer encodes metadata about element types, allowing FQL to decode keys without a schema.

/directory/<>(...)

@fdb.transactional
def read_kvs(tr):
    # Open directory; exit if it doesn't exist
    dir = fdb.directory.open(tr, ('directory',))
    if dir is None:
        return []

    # List the sub-directories
    sub_dirs = dir.list(tr)

    # For each sub-directory, grab all the KVs
    results = []
    for sub_name in sub_dirs:
        sub_dir = dir.open(tr, (sub_name,))
        for key, val in tr[sub_dir.range()]:
            # Remove the directory prefix and unpack the tuple
            tup = sub_dir.unpack(key)
            # Value unpacking will be discussed later...
            results.append((sub_dir.get_path(), tup, val))

    return results

Values

Values have more encoding flexibility. There is a default encoding where data elements are encoded as the lone member of a tuple. For instance, the value 42 is encoded as the tuple (42).

The exceptions to this default encoding are when values are tuples (which are not wrapped in another tuple) and byte strings (which are used as-is for the value).

/people/age("jon","smith")=42

@fdb.transactional
def write_age(tr):
    dir = fdb.directory.create_or_open(tr, ('people', 'age'))
    key = dir.pack(('jon', 'smith'))

    # Pack the value as a tuple
    val = fdb.tuple.pack((42,))

    # Write the KV
    tr[key] = val

This default encoding allows values to be decoded without knowing their type.

/people/age("jon","smith")=<>

@fdb.transactional
def read_age(tr):
    dir = fdb.directory.open(tr, ('people', 'age'))
    key = dir.pack(('jon', 'smith'))

    # Read the value
    val_bytes = tr[key]

    # Assume the value is a tuple
    try:
        val_tup = fdb.tuple.unpack(val_bytes)
        if len(val_tup) == 1:
            return val_tup[0]
        return val_tup
    except:
        # If decoding as a tuple fails, return raw bytes
        return val_bytes

The table below shows options which change how int and num types are encoded as values.

int may use the widths 8, 16, 32, and 64, while num may use 32, 64, and 80. FQL provides be as an alias for bigendian. Additionally, FQL provides provides pseudo types to decrease the verbosity of the encoding options.

If the value was encoded with non-default options, then the encoding must be specified in the variable when read. Otherwise, the default decoding will fail and it will be returned as raw bytes.

Empty Values

Within a tuple, nil, empty bytes, and empty nested tuples are encoded with their types preserved and will be decoded appropriately. As a value, all three are encoded as an empty byte string. A typeless variable will decode said value as nil.

The top-level tuple of a key is encoded as an empty byte string when it contains no elements, allowing queries to write KVs where the key is simply the directory prefix.

Query Types

FQL queries may write a single key-value, read/clear one or more key-values, or list/remove directories. Although all queries resemble key-values, their tokens imply one of the above operations.

Reads & Writes

Queries lacking holes perform writes on the database. You can think of these queries as declaring the existence of a particular key-value. Most query results can be fed back into FQL as write queries. The exception to this rule are aggregate queries and results created by non-default formatting.

❗Queries lacking a value altogether imply an empty variable as the value and should not be confused with write queries.

Queries containing holes read one or more key-values. If the holes only appear in the value, then a single key-value is returned, if one matching the schema exists.

FQL attempts to decode the value as each of the types listed in the variable, stopping at first success. If the value cannot be decoded, the key-value does not match the schema.

Queries with variables in their key (and optionally in their value) result in a range of key-values being read.

Whether reading single or many, when a key-value is encountered which doesn’t match the query’s schema it is filtered out of the results. Including the strict query option causes the query to fail when encountering a non-conformant key-value.

If a query has the token clear as it’s value, it clears all the key matching the query’s schema. Keys not matching the schema are ignored unless the strict option is present, resulting in the query failing.

Directories

The directory layer may be queried in isolation by using a lone directory as a query. Directory queries are read-only except when removing a directory. If the directory path contains no variables, the query will read that single directory.

A directory can be removed by appending =remove to the directory query. If multiple directories match the schema, they will all be removed.

Options

As hinted at above, queries have several options which modify their default behavior.

Range-read queries support all the options listed above. Single-read queries support snapshot and strict. Clear queries support strict. With the strict option, the clear operation is a no-op if FQL encounters a key in the given directory which doesn’t match the schema.

Filtering

As stated above, read queries define a schema to which key-values may or may-not conform. Because filtering is performed on the client side, range reads may stream a lot of data to the client while filtering most of it away. For example, consider the following query:

/people(3392,<str|int>,<>)=(<int>,...)

In the key, the location of the first hole determines the range read prefix used by FQL. For this particular query, the prefix would be as follows:

/people(3392)

FoundationDB will stream all key-values with this prefix to the client. As they are received, the client will filter out key-values which don’t match the query’s schema. This may be most of the data. Ideally, filter queries are only used on small amounts of data to limit wasted bandwidth.

Below you can see a Python implementation of how this filtering would work.

@fdb.transactional
def filter_range(tr):
    dir = fdb.directory.open(tr, ('people',))
    if dir is None:
        return []

    prefix = dir.pack((3392,))
    range_result = tr[fdb.Range(prefix, fdb.strinc(prefix))]

    results = []
    for key, val in range_result:
        tup = dir.unpack(key)

        # Our query specifies a key-tuple with 3 elements
        if len(tup) != 3:
            continue

        # The 2nd element must be either a string or an int
        if not isinstance(tup[1], (str, int)):
            continue

        # The query tells us to assume the value is a packed tuple
        try:
            val_tup = fdb.tuple.unpack(val)
        except:
            continue

        # The value-tuple must have one or more elements
        if len(val_tup) == 0:
            continue

        # The first element of the value-tuple must be an int
        if not isinstance(val_tup[0], int):
            continue

        results.append((tup, val_tup))

    return results

Advanced Queries

Indirection

Indirection queries are similar to SQL joins. They associate different groups of key-values via some shared data element.

In FoundationDB, indexes are implemented using indirection. Suppose we have a large list of people, one key-value for each person.

/people(
  <int>, % ID
  <str>, % First Name
  <str>, % Last Name
  <int>, % Age
)=nil

If we wanted to read all records containing the last name “Johnson”, we’d have to perform a linear search across the entire “people” directory. To make this kind of search more efficient, we can store an index for last names in a separate directory.

/people/last_name(
  <str>, % Last Name
  <int>, % ID
)=nil

If we query the index, we can get the IDs of the records containing the last name “Johnson”.

/people/last_name("Johnson",<int>)

/people/last_name("Johnson",23)=nil
/people/last_name("Johnson",348)=nil
/people/last_name("Johnson",2003)=nil

FQL can forward the observed values of named variables from one query to the next. We can use this to obtain our desired subset from the “people” directory.

/people/last_name("Johnson",<id:int>)
/people(:id,...)

/people(23,"Lenny","Johnson",22,"Mechanic")=nil
/people(348,"Roger","Johnson",54,"Engineer")=nil
/people(2003,"Larry","Johnson",8,"N/A")=nil

Notice that the results of the first query are not returned. Instead, they are used to build a collection of single-KV read queries whose results are the ones returned.

Aggregation

Aggregation queries combine multiple key-values into a single key-value. FQL provides pseudo data types for performing aggregation, similar to SQL’s aggregate functions.

Suppose we are storing value deltas. If we range-read the keyspace we end up with a list of integer values.

/deltas("group A",<int>)

/deltas("group A",20)=nil
/deltas("group A",-18)=nil
/deltas("group A",3)=nil

Instead, we can use the pseudo type sum in our variable to automatically sum up the deltas into the actual value.

/deltas("group A",<sum>)

/deltas("group A",5)=nil

Aggregation queries are also useful when reading large blobs. The data is usually split into chunks stored in separate key-values. The respective keys contain the byte offset of each chunk.

/blob(
  "my_file.bin",    % The identifier of the blob.
  <offset:int>, % The byte offset within the blob.
)=<chunk:bytes> % A chunk of the blob.

/blob("my_file.bin",0)=10kb
/blob("my_file.bin",10000)=10kb
/blob("my_file.bin",20000)=2.7kb

❗Instead of printing the actual byte strings in these results, only the byte lengths are printed. This is a possible feature of an FQL implementation. See Formatting for more details.

Using append, the client obtains the entire blob instead of having to concatenate the chunks themselves.

/blob("my_file.bin",...)=<blob:append>

/blob("my_file.bin",...)=22.7kb

With non-aggregation queries, holes are resolved to actual data elements in the results. For aggregation queries, only aggregation variables are resolved, leaving the ... token in the resulting key-value.

The table below lists the available aggregation types.

sum, min, and max output int if all inputs are int. Otherwise, they output num. Similarly, append outputs str if all inputs are str. Otherwise, it outputs bytes.

append may be given the option sep which defines a str or bytes separator placed between each of the appended values.

% Append the lines of text for a blog post.
/blog/post(
  253245,      % post ID
  <offset:int> % line offset
)=<body:append[sep:"\n"]>

Implementations

FQL defines the query language but leaves many details to the implementation. This sections outlines some of those details and how an implementation may choose to provide them.

Connection

An implementation determines how users connect to a FoundationDB cluster. This may involve selecting from predefined cluster files or specifying a custom path. An implementation could even simulate an FDB cluster locally for testing purposes.

Permissions

An implementation may disallow write queries unless a specific configuration option is enabled. This provides a safeguard against accidental mutations. Implements could also limit access to certain directories or any other behavior for any reason.

Transactions

An implementation defines how transaction boundaries are specified. The Go implementation uses CLI flags to group queries into transactions.

$ fql \
  -q /users(100)="Alice" \
  -q /users(101)="Bob" \
  --tx \
  -q /users(...)

The --tx flag represents a transaction boundary. The first two queries execute within the same transaction. The third query runs in its own transaction.

Variables & References

An implementation defines the scope of named variables. Variables may be namespaced to a single transaction, available across multiple transactions, or persist for an entire session.

Named variables could also be used to output specific values to other parts of the application. For instance, variables with the name stdout may write their values to the STDOUT stream of the process.

/mq("topic",<stdout:str>)

topicA
topicB
topicC

Similarly, references could be used to inject values into a query from another part of the process.

% Write the string contents of STDIN into the DB.
/mq("msg","topicB",:stdin)

Extensions

An implementation may provide custom options and types beyond those defined by FQL. For example, the pseudo type json could act as a restricted form of str which only matches valid JSON. A custom option every:5 could filter results to return only every fifth key-value.

Formatting

An implementation can provide multiple formatting options for key-values returned by read queries. The default format prints key-values as their equivalent write queries. Alternative formats may be provided for different use cases:

• Print byte lengths instead of actual bytes to reduce output verbosity for large values.
• Print placeholders (<uuid>, <vstamp>) in place of actual values when the details are not relevant.
• Output key-values in a binary format suitable for storage on disk or transmission over a network.

Grammar

The complete FQL grammar is specified below.

(* Top-level query structure *)
query = [ opts '\n' ] ( keyval | key | dquery )
dquery = directory [ '=' 'remove' ]

keyval = key '=' value
key = directory tuple
value = 'clear' | data

(* Directories *)
directory = '/' ( '<>' | name | string ) [ directory ]

(* Tuples *)
tuple = '(' [ nl elements [ ',' ] nl ] ')'
elements = '...' | data [ ',' nl elements ]

(* Data elements *)
data = 'nil' | bool | int | num | string | uuid
     | bytes | tuple | vstamp | variable | reference

bool = 'true' | 'false'
int = [ '-' ] digits
num = int '.' digits | ( int | int '.' digits ) 'e' int
string = '"' { char | '\"' | '\\' } '"'
uuid = hex{8} '-' hex{4} '-' hex{4} '-' hex{4} '-' hex{12}
bytes = '0x' { hex{2} }
vstamp = '#' [ hex{20} ] ':' hex{4}

(* Variables and References *)
variable = '<' [ name ':' ] [ type { '|' type } ] '>'
reference = ':' name [ '!' type ]
type = 'any' | 'tuple' | 'bool' | 'int' | 'num'
     | 'str' | 'uuid' | 'bytes' | 'vstamp' | agg
agg = 'count' | 'sum' | 'avg' | 'min' | 'max' | 'append'

(* Options *)
opts = '[' option { ',' option } ']'
option = name [ ':' argument ]
argument = name | int | string

(* Primitives *)
digits = digit { digit }
digit = '0' | '1' | '2' | '3' | '4'
      | '5' | '6' | '7' | '8' | '9'
hex = digit
    | 'a' | 'b' | 'c' | 'd' | 'e' | 'f'
    | 'A' | 'B' | 'C' | 'D' | 'E' | 'F'
name = ( letter | '_' ) { letter | digit | '_' | '-' | '.' }
letter = 'a' | ... | 'z' | 'A' | ... | 'Z'
char = ? Any printable UTF-8 character except '"' and '\' ?

(* Whitespace *)
ws = { ' ' | '\t' }
nl = { ' ' | '\t' | '\n' | '\r' }