couchbase/query

• Latest: Query README
• Modified: 2015-04-25

This README describes the source code and implementation of the N1QL query engine and components.

The goals of this implementation are:

• Language completeness

• GA code base

• Source code aesthetics

  • Design, object orientation
  • Data structures, algorithms
  • Modularity, readability

This N1QL implementation provides the following features:

• Read

  • SELECT
  • EXPLAIN

• DDL

  • CREATE / DROP INDEX
  • CREATE PRIMARY INDEX

• DML

  • UPDATE
  • DELETE
  • INSERT
  • UPSERT
  • MERGE

  The ACID semantics of the DML statements have not yet been decided or implemented. Nor has the underlying support in Couchbase Server. At this time, only the DML syntax and query engine processing have been provided.

The query engine is a multi-threaded server that runs on a single node. When deployed on a cluster, multiple instances are deployed on separate nodes. This is only for load-balancing and availability. In particular, the query engine does not perform distributed query processing, and separate instances do not communicate or interact.

In production, users will have the option of colocating query engines on KV and index nodes, or deploying query engines on dedicated query nodes. Because the query engine is highly data-parallel, we have a goal of achieving good speedup on dedicated query nodes with high numbers of cores.

The remainder of this document refers to a single instance of the query engine. At this time, load balancing, availability, and liveness are external concerns that will be handled later by complementary components.

• Parse: Text to algebra. In future, we could also add JSON to algebra (e.g. if we add something like JSONiq or the Mongo query API).

• Prepare: Algebra to plan. This includes index selection.

• Execute: Plan to results. When we add prepared statements, this phase can be invoked directly on a prepared statement.

The value package implements JSON and non-JSON values, including delayed parsing. This implementation has measured a 2.5x speedup over dparval.

Primitive JSON values (boolean, number, string, null) are implemented as golang primitives and incur no memory or garbage-collection overhead.

This package also provides collation, sorting, and sets (de-duplication) over Values.

• Value: Base interface.

• AnnotatedValue: Can carry attachments and metadata.

• CorrelatedValue: Refers and escalates to a parent Value. Used to implement subqueries and name scoping.

• ParsedValue: Delayed evaluation of parsed values, including non-JSON values.

• MissingValue: Explicit representation of MISSING values. These are useful for internal processing, and can be skipped during final projection of results.

• BooleanValue, NumberValue, StringValue, NullValue, ArrayValue, ObjectValue: JSON values.

The errors package provides a dictionary of error codes and messages. When fully implemented, the error codes will mirror SQL, and the error messages will be localizable.

All user-visible errors and warnings should come from this package.

The expression package defines the interfaces for all expressions, and provides the implementation of scalar expressions.

This package is usable by both query and indexing (for computed indexes).

Expressions are evaluated within a context; this package provides a default context that can be used by indexing. The context includes a statement-level timestamp.

Expressions also provide support for query planning and processing; this includes equivalence testing, constant folding, etc.

The following types of scalar expressions are included:

• arithmetic operators
• CASE
• Collection expressions (ANY / EVERY / ARRAY / FIRST)
• Comparison operators (including IS operators)
• String concat
• Constants (including literals)
• Functions
• Identifiers
• Navigation (fields, array indexing, array slicing)

The algebra package defines the full algebra and AST (abstract syntax tree) for all N1QL statements (using the expression package for scalar expressions).

It includes aggregate functions, subquery expressions, parameter expressions, bucket references, and all the N1QL statements and clauses.

• ARRAY_AGG(expr)

• ARRAY_AGG(DISTINCT expr)

• AVG(expr)

• AVG(DISTINCT expr)

• COUNT(*)

• COUNT(expr)

• COUNT(DISTINCT expr)

• MAX(expr)

• MIN(expr)

• SUM(expr)

• SUM(DISTINCT expr)

The plan package implements executable representations of queries. This includes both SELECTs and DML statements.

When we implement prepared statements, they will be represented as plans and stored as JSON documents or in-memory plan objects.

Plans are built from algebras using a visitor pattern. A separate planner / optimizer will be implemented for index selection.

Plans include the following operators:

• Scans

  • PrimaryScan: Scans a primary index.

  • IndexScan: Scans a secondary index.

  • KeyScan: Does not perform a scan. Directly treats the provided keys as a scan.

  • ValueScan: Used for the VALUES clause of INSERT and UPSERT statements. Treats the provided values as the result of a scan.

  • DummyScan: Used for SELECTs with no FROM clause. Provides a single empty object as the result of a scan.

  • CountScan: Used for SELECT COUNT(*) FROM bucket-name. Treats the bucket size as the result of a scan, without actually performing a full scan of the bucket.

  • IntersectScan: A container that scans its child scanners and intersects the results. Used for scanning multiple secondary indexes concurrently for a single query.

• Fetch

• Joins

  • Join

  • Nest

  • Unnest

• Filter

• Group: To enable data-parallelism, grouping is divided into three phases. The first two phases can each be executed in a data-parallel fashion, and the final phase merges the results.

  • InitialGroup: Initial phase.

  • IntermediateGroup: Cumulate intermediate results. This phase can be chained.

  • FinalGroup: Compute final aggregate results.

• Other SELECT operators

  • Project

  • Distinct

  • Order

  • Offset

  • Limit

  • Let

  • UnionAll: Combine the results of two queries. For UNION, we perform UNION ALL followed by DISTINCT.

• Framework operators

  • Collect: Collect results into an array. Used for subqueries.

  • Discard: Discard results.

  • Stream: Stream results out. Used for returning results.

  • Parallel: A container that executes multiple copies of its child operator in parallel. Used for all data-parallelism.

  • Sequence: A container that chains its children into a sequence. Used for all execution pipelining.

• DML operators

  • SendDelete

  • SendInsert

  • Set: Used for UPDATE.

  • Unset: Used for UPDATE.

  • Clone: Used for UPDATE. Clones data values so that UPDATEs read original values and mutate a clone.

  • SendUpdate

  • Merge

The execution package implements query execution. The objects in this package mirror those in the plan package, except that these are the running instances.

Golang channels are used extensively to implement concurrency and signaling.

The Context object supports subquery execution. It performs planning, execution, and collection of subquery results. It also performs plan and result caching for uncorrelated subqueries.

The datastore package defines the interface to the underlying database server.

Some key differences from the previous datastore API (previously catalog API):

• DML support

• Use of channels for error handling and stop signaling

• Generalized index interface that supports any combination of hash and range indexing

This package will contain the parser and lexer.

This package will contain the main engine executable and listener.

This package defines the interface to the underlying cluster management system.

It provides a common abstraction for cluster management, including configuration of and the lifecycle of a cluster.

This package will contain the interface to workload tracking and monitoring. Accounting data can cover metrics, statistics, event and potentially log data.

It provides a common abstraction for recording accounting data and services over accounting data.

This package will contain the client command-line shell.

This package provides a parallel sort. It was copied from the Golang source and basic parallelism was added, but it has not been fine-tuned.

This package provides a client library that will be used by the command-line shell to encapsulate cluster-awareness and other connectivity concerns.

The library will implement the standard golang database APIs at database/sql and database/sql/driver.

The library will connect using the Query REST API and the Query Clustering API.

The query engine is designed to be highly data-parallel. By data-parallel, we mean that individual stages of the execution pipeline are parallelized over their input data. This is in addition to the parallelism achieved by giving each stage its own goroutine.

Below, N1QL statement execution pipelines are listed, along with the data-parallelization and serialization points.

1. Scan
2. Parallelize
3. Fetch
4. Join / Nest / Unnest
5. Let (Common subexpressions)
6. Where (Filter)
7. GroupBy: Initial
8. GroupBy: Intermediate
9. Serialize
10. GroupBy: Final
11. Parallelize
12. Letting (common aggregate subexpressions)
13. Having (aggregate filtering)
14. Serialize
15. Order By (Sort)
16. Parallelize
17. Select (Projection)
18. Serialize
19. Distinct (De-duplication)
20. Offset (Skipping)
21. Limit

1. Scan
2. Parallelize
3. SendInsert
4. Returning (Projection)

1. Scan
2. Parallelize
3. Fetch
4. Let (Common subexpressions)
5. Where (Filter)
6. Serialize
7. Limit
8. Parallelize
9. SendDelete
10. Returning (Projection)

1. Scan
2. Parallelize
3. Fetch
4. Let (Common subexpressions)
5. Where (Filter)
6. Serialize
7. Limit
8. Parallelize
9. Clone
10. Set / Unset
11. SendUpdate
12. Returning (Projection)

The N1QL query engine build is part of the couchbase cluster build.