PatternQuery Implementation

Like SQL, PatternQuery is not Turing complete, but all queries terminate eventually, so there are no infinite loops. A PatternQuery cannot run out of memory except for intentional use of temporary space, such as the session state in a REST client query . The execution engine uses only nested loops, without temporary space, but a stepped query can explicitly use temporary space or modify the database and then input the modifications. Unlike relational, the nested loops form a tree. Optimization is rule-based and almost immediate in all cases.

Concurrency

Queries can overlap, do not interfere, and are not limited in degree of concurrency. The multi-core concurrency of the underlying InfinityDB BTree is fully utilized. Each query executes single-Threaded (so far!). There are no inter-query locks, or in fact any locks at all within the PatternQuery code, except that if a query is executed in the context of an Optimistic transaction, then OptimisticLockConflictExceptions can be thrown and retries may be needed, as with any other code.

Expression Evaluation

Common subexpressions are factored out and values are cached where helpful. A notification tree propagates value change events, so expressions and subexpressions are not unnecessarily re-executed when referred to. This can be important when doing regex matching and text formatting in relatively outer parts of the pattern.

Example Plan

Here is a printout of the execution plan of a particular test query. The symbols in the test definition are all named symbol(n) and the literals are numbers from 1 to 15, with no expressions. The nested loops are indicated by indentation. This plan is efficient because it is not just a diagonal but has many ‘outdents’ where backtracking can occur, showing the tree structure of the looping. The looping is dependent on the particular pattern used and is not always possible to flatten to this degree. However many common data structures in an ItemSpace do use multiple Items with common prefixes, which take advantage of the logically tree-like execution. Joins and cross-products in the result produce various ‘edits’ to the pattern not shown here. Terms in parentheses are from the pattern, and those with square brackets are from the result.

(root)
    (1:0)
        (=symbol1:1)
            (2:2)
                (=symbol2:3)
                    *:4t [11:0] [=symbol1:1] [12:2] [=symbol2:3]
            (3:2)
                (4:3)
                    (=symbol4:4)
                        *:5t [11:0] [=symbol1:1] [13:2] [14:3] [=symbol4:4]
                (5:3)
                    (=symbol3:4)
                        *:5t [11:0] [=symbol1:1] [13:2] [15:3] [=symbol3:4]

Relational Plans

PatternQuery plans contrast with those generated by a relational system, in which the nesting of a nested loops plan is only diagonal, determining effectively a huge logical cross product that is filtered at appropriate points. Nested loops in a relational system are therefore not always very efficient, and various other join mechanisms are often used, but the selection of the join mechanisms is very complex and unpredictable in effect. Query optimization may take substantial time due to the difficulty of finding a reasonably efficient plan, and the efficiency is still often low, possibly extremely so. Relational plans other than nested loops require temporary space of some sort.