Advanced query tuning example

Introduction

One of the most important and useful ways of optimizing Cypher® queries involves creating appropriate indexes. This is described in more detail in Indexes for search performance, and demonstrated in Basic query tuning example. In summary, an index will be based on the combination of a Label and a property. Any Cypher query that searches for nodes with a specific label and some predicate on the property (equality, range or existence) will be planned to use the index if the cost planner deems that to be the most efficient solution.

In order to benefit from enhancements provided by native indexes, it is useful to understand when index-backed property lookup and index-backed order by will come into play. In Neo4j 3.4 and earlier, the fact that the index contains the property value, and the results are returned in a specific order, was not used improve the performance of any later part of the query that might depend on the property value or result order.

Let’s explain how to use these features with a more advanced query tuning example.

If you are upgrading an existing store to 4.2.19, it may be necessary to drop and re-create existing indexes. For information on native index support and upgrade considerations regarding indexes, see Operations Manual → Indexes.

The data set

In this example we will demonstrate the impact native indexes can have on query performance under certain conditions. We’ll use a movies dataset to illustrate this more advanced query tuning.

LOAD CSV WITH HEADERS FROM 'file:///query-tuning/movies.csv' AS line
MERGE (m:Movie { title: line.title })
ON CREATE SET m.released = toInteger(line.released), m.tagline = line.tagline
LOAD CSV WITH HEADERS FROM 'file:///query-tuning/actors.csv' AS line
MATCH (m:Movie { title: line.title })
MERGE (p:Person { name: line.name })
ON CREATE SET p.born = toInteger(line.born)
MERGE (p)-[:ACTED_IN { roles:split(line.roles, ';')}]->(m)
LOAD CSV WITH HEADERS FROM 'file:///query-tuning/directors.csv' AS line
MATCH (m:Movie { title: line.title })
MERGE (p:Person { name: line.name })
ON CREATE SET p.born = toInteger(line.born)
MERGE (p)-[:DIRECTED]->(m)
CREATE INDEX FOR (p:Person)
ON (p.name)
CALL db.awaitIndexes
+--------------------------------------------+
| No data returned, and nothing was changed. |
+--------------------------------------------+

Index-backed property-lookup

Let’s say we want to write a query to find persons with the name 'Tom' that acted in a movie.

MATCH (p:Person)-[:ACTED_IN]->(m:Movie)
WHERE p.name STARTS WITH 'Tom'
RETURN p.name, count(m)
+---------------------------+
| p.name         | count(m) |
+---------------------------+
| "Tom Cruise"   | 3        |
| "Tom Hanks"    | 12       |
| "Tom Skerritt" | 1        |
+---------------------------+
3 rows

We have asked the database to return all the actors with the first name 'Tom'. There are three of them: 'Tom Cruise', 'Tom Skerritt' and 'Tom Hanks'. In previous versions of Neo4j, the final clause RETURN p.name would cause the database to take the node p and look up its properties and return the value of the property name. With native indexes, however, we can leverage the fact that indexes store the property values. In this case, it means that the names can be looked up directly from the index. This allows Cypher to avoid the second call to the database to find the property, which can save time on very large queries.

If we profile the above query, we see that the NodeIndexSeekByRange in the Details column contains cache[p.name], which means that p.name is retrieved from the index. We can also see that the OrderedAggregation has no DB Hits, which means it does not have to access the database again.

PROFILE
MATCH (p:Person)-[:ACTED_IN]->(m:Movie)
WHERE p.name STARTS WITH 'Tom'
RETURN p.name, count(m)
Compiler CYPHER 4.2

Planner COST

Runtime INTERPRETED

Runtime version 4.2

+-----------------------+--------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+------------+
| Operator              | Details                                                            | Estimated Rows | Rows | DB Hits | Memory (Bytes) | Page Cache Hits/Misses | Ordered by |
+-----------------------+--------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+------------+
| +ProduceResults       | `p.name`, `count(m)`                                               |              1 |    3 |       0 |                |                    0/0 | p.name ASC |
| |                     +--------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+------------+
| +OrderedAggregation   | cache[p.name] AS `p.name`, count(m) AS `count(m)`                  |              1 |    3 |       0 |              0 |                    0/0 | p.name ASC |
| |                     +--------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+------------+
| +Filter               | m:Movie                                                            |              1 |   16 |      16 |                |                    0/0 | p.name ASC |
| |                     +--------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+------------+
| +Expand(All)          | (p)-[anon_17:ACTED_IN]->(m)                                        |              1 |   16 |      20 |                |                    0/0 | p.name ASC |
| |                     +--------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+------------+
| +NodeIndexSeekByRange | p:Person(name) WHERE name STARTS WITH $autostring_0, cache[p.name] |              1 |    4 |       5 |                |                    0/0 | p.name ASC |
+-----------------------+--------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+------------+

Total database accesses: 41, total allocated memory: 0

If we change the query, such that it can no longer use an index, we will see that there will be no cache[p.name] in the Variables, and that the EagerAggregation now has DB Hits, since it accesses the database again to retrieve the name.

PROFILE
MATCH (p:Person)-[:ACTED_IN]->(m:Movie)
RETURN p.name, count(m)
Compiler CYPHER 4.2

Planner COST

Runtime INTERPRETED

Runtime version 4.2

+-------------------+--------------------------------------------+----------------+------+---------+----------------+------------------------+
| Operator          | Details                                    | Estimated Rows | Rows | DB Hits | Memory (Bytes) | Page Cache Hits/Misses |
+-------------------+--------------------------------------------+----------------+------+---------+----------------+------------------------+
| +ProduceResults   | `p.name`, `count(m)`                       |             13 |  102 |       0 |                |                    0/0 |
| |                 +--------------------------------------------+----------------+------+---------+----------------+------------------------+
| +EagerAggregation | p.name AS `p.name`, count(m) AS `count(m)` |             13 |  102 |     172 |          13280 |                    0/0 |
| |                 +--------------------------------------------+----------------+------+---------+----------------+------------------------+
| +Filter           | p:Person                                   |            172 |  172 |     172 |                |                    0/0 |
| |                 +--------------------------------------------+----------------+------+---------+----------------+------------------------+
| +Expand(All)      | (m)<-[anon_17:ACTED_IN]-(p)                |            172 |  172 |     210 |                |                    0/0 |
| |                 +--------------------------------------------+----------------+------+---------+----------------+------------------------+
| +NodeByLabelScan  | m:Movie                                    |             38 |   38 |      39 |                |                    0/0 |
+-------------------+--------------------------------------------+----------------+------+---------+----------------+------------------------+

Total database accesses: 593, total allocated memory: 13280

For non-native indexes there will still be a second database access to retrieve those values.

Predicates that can be used to enable this optimization are:

  • Existence (e.g. WHERE exists(n.name))

  • Equality (e.g. WHERE n.name = 'Tom Hanks')

  • Range (e.g. WHERE n.uid > 1000 AND n.uid < 2000)

  • Prefix (e.g. WHERE n.name STARTS WITH 'Tom')

  • Suffix (e.g. WHERE n.name ENDS WITH 'Hanks')

  • Substring (e.g. WHERE n.name CONTAINS 'a')

  • Several predicates of the above types combined using OR, given that all of them are on the same property (e.g. WHERE n.prop < 10 OR n.prop = 'infinity' )

If there is an existence constraint on the property, no predicate is required to trigger the optimization. For example, CREATE CONSTRAINT constraint_name ON (p:Person) ASSERT exists(p.name)

Aggregating functions

For all built-in aggregating functions in Cypher, the index-backed property-lookup optimization can be used even without a predicate. Consider this query which returns the number of distinct names of people in the movies dataset:

PROFILE
MATCH (p:Person)
RETURN count(DISTINCT p.name) AS numberOfNames
Compiler CYPHER 4.2

Planner COST

Runtime INTERPRETED

Runtime version 4.2

+-------------------+--------------------------------------------------+----------------+------+---------+----------------+------------------------+
| Operator          | Details                                          | Estimated Rows | Rows | DB Hits | Memory (Bytes) | Page Cache Hits/Misses |
+-------------------+--------------------------------------------------+----------------+------+---------+----------------+------------------------+
| +ProduceResults   | numberOfNames                                    |              1 |    1 |       0 |                |                    0/0 |
| |                 +--------------------------------------------------+----------------+------+---------+----------------+------------------------+
| +EagerAggregation | count(DISTINCT cache[p.name]) AS numberOfNames   |              1 |    1 |       0 |           9856 |                    0/0 |
| |                 +--------------------------------------------------+----------------+------+---------+----------------+------------------------+
| +NodeIndexScan    | p:Person(name) WHERE exists(name), cache[p.name] |            125 |  125 |     126 |                |                    0/0 |
+-------------------+--------------------------------------------------+----------------+------+---------+----------------+------------------------+

Total database accesses: 126, total allocated memory: 9856

Note that the NodeIndexScan in the Variables column contains cache[p.name] and that the EagerAggregation has no DB Hits. In this case, the semantics of aggregating functions works like an implicit existence predicate because Person nodes without the property name will not affect the result of an aggregation.

Index-backed order by

Now consider the following refinement to the query:

PROFILE
MATCH (p:Person)-[:ACTED_IN]->(m:Movie)
WHERE p.name STARTS WITH 'Tom'
RETURN p.name, count(m)
ORDER BY p.name
Compiler CYPHER 4.2

Planner COST

Runtime INTERPRETED

Runtime version 4.2

+-----------------------+--------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+------------+
| Operator              | Details                                                            | Estimated Rows | Rows | DB Hits | Memory (Bytes) | Page Cache Hits/Misses | Ordered by |
+-----------------------+--------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+------------+
| +ProduceResults       | `p.name`, `count(m)`                                               |              1 |    3 |       0 |                |                    0/0 | p.name ASC |
| |                     +--------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+------------+
| +OrderedAggregation   | cache[p.name] AS `p.name`, count(m) AS `count(m)`                  |              1 |    3 |       0 |              0 |                    0/0 | p.name ASC |
| |                     +--------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+------------+
| +Filter               | m:Movie                                                            |              1 |   16 |      16 |                |                    0/0 | p.name ASC |
| |                     +--------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+------------+
| +Expand(All)          | (p)-[anon_17:ACTED_IN]->(m)                                        |              1 |   16 |      20 |                |                    0/0 | p.name ASC |
| |                     +--------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+------------+
| +NodeIndexSeekByRange | p:Person(name) WHERE name STARTS WITH $autostring_0, cache[p.name] |              1 |    4 |       5 |                |                    0/0 | p.name ASC |
+-----------------------+--------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+------------+

Total database accesses: 41, total allocated memory: 0

We are asking for the results in ascending alphabetical order. The native index happens to store String properties in ascending alphabetical order, and Cypher knows this. In Neo4j 3.4 and earlier, Cypher would plan a Sort operation to sort the results, which means building a collection in memory and running a sort algorithm on it. For large result sets this can be expensive in terms of both memory and time. In Neo4j 3.5 and later, Cypher will recognize that the index already returns data in the correct order, and skip the Sort operation.

The Order column describes the order of rows after each operator. We see that the Order column contains p.name ASC from the index seek operation, meaning that the rows are ordered by p.name in ascending order.

Index-backed order by can also be used for queries that expect their results is descending order, but with slightly lower performance.

In cases where the Cypher planner is unable to remove the Sort operator, the planner can utilize knowledge of the ORDER BY clause to plan the Sort operator at a point in the plan with optimal cardinality.

min() and max()

For the min and max functions, the index-backed order by optimization can be used to avoid aggregation and instead utilize the fact that the minimum/maximum value is the first/last one in a sorted index. Consider the following query which returns the fist actor in alphabetical order:

PROFILE
MATCH (p:Person)-[:ACTED_IN]->(m:Movie)
RETURN min(p.name) AS name
+----------------+
| name           |
+----------------+
| "Aaron Sorkin" |
+----------------+
1 row

Aggregations are usually using the EagerAggregation operation. This would mean scanning all nodes in the index to find the name that is first in alphabetic order. Instead, the query is planned with Projection, followed by Limit, followed by Optional. This will simply pick the first value from the index.

Compiler CYPHER 4.2

Planner COST

Runtime INTERPRETED

Runtime version 4.2

+-------------------+-----------------------------+----------------+------+---------+----------------+------------------------+
| Operator          | Details                     | Estimated Rows | Rows | DB Hits | Memory (Bytes) | Page Cache Hits/Misses |
+-------------------+-----------------------------+----------------+------+---------+----------------+------------------------+
| +ProduceResults   | name                        |              1 |    1 |       0 |                |                    0/0 |
| |                 +-----------------------------+----------------+------+---------+----------------+------------------------+
| +EagerAggregation | min(p.name) AS name         |              1 |    1 |     172 |              0 |                    0/0 |
| |                 +-----------------------------+----------------+------+---------+----------------+------------------------+
| +Filter           | p:Person                    |            172 |  172 |     172 |                |                    0/0 |
| |                 +-----------------------------+----------------+------+---------+----------------+------------------------+
| +Expand(All)      | (m)<-[anon_17:ACTED_IN]-(p) |            172 |  172 |     210 |                |                    0/0 |
| |                 +-----------------------------+----------------+------+---------+----------------+------------------------+
| +NodeByLabelScan  | m:Movie                     |             38 |   38 |      39 |                |                    0/0 |
+-------------------+-----------------------------+----------------+------+---------+----------------+------------------------+

Total database accesses: 593, total allocated memory: 0

For large datasets, this can improve performance dramatically.

Index-backed order by can also be used for corresponding queries with the max function, but with slightly lower performance.

Restrictions

The optimization can only work on native indexes. It does not work for predicates only querying for the spatial type Point. Predicates that can be used to enable this optimization are:

  • Existence (e.g.WHERE exists(n.name))

  • Equality (e.g. WHERE n.name = 'Tom Hanks')

  • Range (e.g. WHERE n.uid > 1000 AND n.uid < 2000)

  • Prefix (e.g. WHERE n.name STARTS WITH 'Tom')

  • Suffix (e.g. WHERE n.name ENDS WITH 'Hanks')

  • Substring (e.g. WHERE n.name CONTAINS 'a')

Predicates that will not work:

  • Several predicates combined using OR

  • Equality or range predicates querying for points (e.g. WHERE n.place > point({ x: 1, y: 2 }))

  • Spatial distance predicates (e.g. WHERE distance(n.place, point({ x: 1, y: 2 })) < 2)

If there is an existence constraint on the property, no predicate is required to trigger the optimization. For example, CREATE CONSTRAINT constraint_name ON (p:Person) ASSERT exists(p.name)

As of Neo4j 4.2.19, predicates with parameters, such as WHERE n.prop > $param, can trigger index-backed order by. The only exception are queries with parameters of type Point.