GraphDB-SE Rule Profiling

Skip to end of metadata
Go to start of metadata
GraphDB Documentation
This documentation is NOT for the latest version of GraphDB.

Latest version - GraphDB 7.1

Next versions

GraphDB 6.5
GraphBD 6.6
GraphBD 7.0
GraphDB 7.1

Previous versions

GraphDB 6.3
GraphDB 6.2
GraphDB 6.0 & 6.1

[OWLIM 5.4]
[OWLIM 5.3]
[OWLIM 5.2]
[OWLIM 5.1]
[OWLIM 5.0]
[OWLIM 4.4]
[OWLIM 4.3]
[OWLIM 4.2]
[OWLIM 4.1]
[OWLIM 4.0]

GraphDB 6 includes a useful new feature that allows you to debug rule performance
This page also includes Optimization Hints for ruleset performance. See GraphDB-SE Performance Tuning for hints about optimizing storage and querying performance.

Rule Execution

To debug rule performance effectively, you first need to understand how GraphDB rules are executed (evaluated). The description below complements the one in GraphDB-SE Reasoner, in particular see Entailment rules.

  • For each rule and each premise (triple pattern in the rule head), a rule variant is generated.
    We call this the "leading premise" of the variant.
    If a premise has the [Cut] annotation, no variant is generated for it.
  • Every incoming triple (inserted or inferred) is checked against the leading premise of every rule variant.
    Since rules are compiled to Java bytecode on startup, this checking is very fast.
  • If the leading premise matches, the rest of the premises are checked.
    This checking needs to access the repository, so it can be much slower.
    • GraphDB first checks premises with the least number of unbound variables
    • For premises that have the same number of unbound variables, GraphDB follows the textual order in the rule
  • If all premises match, the conclusions of the rule are inferred
  • For each inferred statement:

Enable Profiling

To enable rule profiling, start GraphDB with the following Java option:

 -Denable-debug-rules=true

This enables the collection of rule statistics (various counters). Please note that this slows down rule execution (the leading premise checking part) by 10-30%.

Do not use rule profiling in production

Log File

When rule profiling is enabled:

  • GraphDB prints the complete rule statistics every 1M statements, every 5 minutes, or on shutdown (whichever comes first)
  • The statistics is written to openrdf-sesame/logs/main-<date>.log after a line like this:
    Rule statistics:
  • The statistics are cumulative, so you only need to work with the last one
  • Rule variants are ordered by total time (descending)

Consider this rule for example:

Id: ptop_PropRestr
  t <ptop:premise>     p
  t <ptop:restriction> r
  t <ptop:conclusion>  q
  t <rdf:type>         <ptop:PropRestr>
  x p y
  x r y
  ----------------
  x q y

This is a conjunction of two props. It is declared with the axiomatic (A-Box) triples involving t. Whenever the premise p and restricton r hold between two resources,, the rule infers the conclusion q between the same resources, i.e. p & r => q

The corresponding log for variant 4 of this rule may look like the following:

RULE ptop_PropRestr_4 invoked 163,475,763 times.
ptop_PropRestr_4:
e b f
a ptop_premise b
a rdf_type ptop_PropRestr
e c f
a ptop_restriction c
a ptop_conclusion d
------------------------------------
e d f

a ptop_conclusion d invoked 1,456,793 times and took 1,814,710,710 ns.
a rdf_type ptop_PropRestr invoked 7,261,649 times and took 9,409,794,441 ns.
a ptop_restriction c invoked 1,456,793 times and took 1,901,987,589 ns.
e c f invoked 17,897,752 times and took 635,785,943,152 ns.
a ptop_premise b invoked 10,175,697 times and took 9,669,316,036 ns.
Fired 1,456,793 times and took 157,163,249,304 ns.
Inferred 1,456,793 statements.
Time overall: 815,745,001,232 ns.
  • Unfortunately variable names are renamed due to the compilation to Java bytecode
  • The premises are checked in the order given in RULE. (The premise stats printed after the blank line are not in any particular order; we have an improvement request for this: OWLIM-1548)
  • invoked is the number of times the rule variant or specific premise was checked successfully. Tracing through the rule:
    • ptop_PropRestr_4 checked successfully 163M times: for each incoming triple, since the lead premise (e b f = x p y) is a free pattern.
    • a ptop_premise b checked successfully 10M times: for each b=p that has an axiomatic triple involving ptop_premise.
      This premise was selected because it has only 1 unbound variable (a) and it's first in the rule text.
    • a rdf_type ptop_PropRestr checked successfully 7M times: for each ptop_premise that has type ptop_PropRestr.
      This premise was selected because it has 0 unbound variables (after the previous premise binds a)
    • etc, etc
  • The time to check each premise is printed in ns
  • fired is the number of times all premises matched, so the rule variant was fired
  • inferred is the number of inferred triples.
    It may be more than "fired" if there are multiple conclusions.
    It may be less then "fired" since a duplicate triple is not inferred a second time.
  • time overall is the total time that this rule variant took

Excel Format

The log records detailed information about each rule and premise, which is indispensable when you are trying to understand which rule is spending too much time. However, it can be hard to grasp because of this level of detail.

We have developed the script rule-stats.pl that outputs a TSV file like this:

rule ver tried time patts checks time fired time triples speed
ptop_PropChain 4 163475763 776.3 5 117177482 185.3 15547176 590.9 9707142 12505
  • rule: rule id (name)
  • ver: rule version (variant) or "T" for overall rule totals
  • tried, time: number of times the rule/variant was tried, and overall time in sec
  • patts: number of triple patterns (premises) in the rule, not counting the leading premise
  • checks, time: number of times premises were checked, time in sec
  • fired: number of times all premises matched, so the rule was fired
  • triples: number of inferred triples
  • speed: inference speed, triples/sec

You can run the script like this:

Investigate Performance

We'll give an example of using the Excel format to investigate where time is spent during rule execution.

Open the result in Excel, set a filter "ver=T" (to first look at rules as a whole, not rule variants), sort descending by total "time" (third column). You can download the Excel and maybe use it as a template for your own investigations.
main-2014-08-08.xlsx

At the bottom are totals for "time" and "triples" and average for "speed". These formulas are dynamic in that they refresh when you change the filters.

Now focus on rules that spend substantial time, and whose speed is significantly lower than average (highlighted in red above). Let's pick PropRestr and look at its variants by filtering on "rule=PropRestr" and "ver<>T":

We should first focus on variant ptop_PropRestr_5, which spends 30% of the time of this rule, and has very low "speed". The reason is that it fired 1.4M times but produced only 238 triples, so most of the inferred triples were duplicate. We find the definition of this variant in the log file:

RULE ptop_PropRestr_5 invoked 163,475,763 times.
ptop_PropRestr_5:
e c f
a ptop_restriction c
a rdf_type ptop_PropRestr
e b f
a ptop_premise b
a ptop_conclusion d
------------------------------------
e d f

It is very similar to the productive variant ptop_PropRestr_4 (see Log File above):

  • one checks e b f. a ptop_premise b first,
  • the other checks e c f. a ptop_restriction c first.

But the function of these premises in the rule is the same, so it's little wonder that the variant ptop_PropRestr_5 (which is checked after 4) is unproductive.

Presumably, performance would be improved if we make the two premises use the same axiomatic triple ptop:premise (emphasizing they have the same role), and introduce a [Cut]:

Id: ptop_PropRestr_SYM
  t <ptop:premise>     p
  t <ptop:premise>     r
  t <ptop:conclusion>  q
  t <rdf:type>         <ptop:PropRestr>
  x p y
  x r y                [Cut]
  ----------------
  x q y

The cut eliminates the rule variant with x r y as leading premise. It's legitimate to do this, since the two variants are the same, up to substitution p<->r.

Introducing a cut in the original version of the rule would not be legitimate:

Id: ptop_PropRestr_CUT
  t <ptop:premise>     p
  t <ptop:restriction> r
  t <ptop:conclusion>  q
  t <rdf:type>         <ptop:PropRestr>
  x p y
  x r y                [Cut]
  ----------------
  x q y

Since it would omit some potential inferences (in the case above, 238 triples), changing the semantics of the rule.

  • Assume these axiomatic triples:
    :t_CUT a ptop:PropRestr; ptop:premise :p; ptop:restriction :r; ptop:conclusion :q. # for ptop_PropRestr_CUT
    :t_SYM a ptop:PropRestr; ptop:premise :p; ptop:premise     :r; ptop:conclusion :q. # for ptop_PropRestr_SYM
    
  • Now consider a sequence of inserted triples :x :p :y. :x :r :y.
  • ptop_PropRestr_CUT will not infer :x :q :y since no variant is fired by the second incoming triple :x :r :y: it is matched against x p y, but there's no axiomatic triple t ptop:premise :r
  • ptop_PropRestr_SYM will infer :x :q :y since the second incoming triple :x :r :y will match x p y and t ptop:premise :r, then the previously inserted :x :p :y will match t ptop:premise :p and the rule will fire.

We wrote "Presumably, performance would be improved" since rule execution is often non-intuitive. So you are advised to keep detailed speed history, and comparing the performance after each change.

Optimization Hints

In the previous section we provided a detailed example of poring through the Log File and Excel Format and optimizing a rule set. In this section we provide more general advice about optimizing rule sets.

Reasoning Complexity

The complexity of the rule set has a large effect on loading performance, number of inferred statements, and the overall size of the repository after inferencing. The complexity of the standard rule sets increases as follows:

  • none (lowest complexity, best performance)
  • rdfs-optimized
  • rdfs
  • owl-horst-optimized
  • owl-horst
  • owl-max-optimized
  • owl-max
  • owl2-ql-optimized
  • owl2-ql
  • owl2-rl-optimized
  • owl2-rl (highest complexity, worst performance)

OWL RL and OWL QL do a lot of heavy work that is often not required by applications.

Know What You Want to Infer

Check the "expansion ratio" (total/explicit statements) for your dataset, and have an idea whether that is what you expect. If your rule set infers say 4x more statements over a large number of explicit statements, that will take time, no matter how you try to optimize the rules.

Minimize Number of Rules

The number of rules and their complexity affects inferencing performance, even for rules that never infer any new statements. This is because every incoming statement is passed through every variant of every rule to check whether something can be inferred. This often results in many checks & joins, even if the rule never fires.

So start with a minimal rule set, then add only the additional rules that you require. The default ruleset (owl-horst-optimized) works for many people, but you could even consider starting from RDFS. Eg if you need owl:Symmetric and owl:inverseOf on top of RDFS, you could copy only these rules from OWL Horst to RDFS, and leave the rest aside.

Conversely, you can start with a bigger standard ruleset, then remove the rules that you don't need.

To deploy a custom rule set, set the ruleset configuration parameter to the full pathname of your custom .pie file.

Write Your Rules Carefully

Be careful when you write custom rules:

  • Recursive rules can lead to an explosion in the number of inferred statements
  • If you misspell a variable in a premise, this will lead to a Cartesian explosion of the number of triple joins to be considered by the rule
  • If you misspell a variable in a conclusion (or use an unbound variable), this cause new blank nodes to be created. This is almost never what you really want
  • Order premises by specificity. GraphDB first checks premises with the least number of unbound variables. But if there's a tie, it follows the order given by you. Since you may know the cardinalities of triples in your data, you may be in a better position to determine which premise has better specificity (selectivity).
  • Use [Cut] for premises that have the same role (see Investigating Performance for an example), but be careful not to remove some needed inferences by mistake

Avoid Duplicate Statements

Avoid inserting explicit statements in a named graph, if the same statements are inferrable. GraphDB always stores inferred statements in the default graph, so this will lead to duplication of statements. This will increase repository size and will slow down query answering.
You can eliminate duplicates from query results using DISTINCT or FROM onto:skip-redundant-implicit (as documented in Other special query behaviour). But these are slow operations, and it's better not to produce duplicate statements in the first place.

Know the Implications of Ontology Mapping

People often use owl:equivalentProperty, owl:equivalentClass (and less often rdfs:subPropertyOf, rdfs:subClassOf) to map ontologies. But every such assertion means that many more statements are inferred (owl:equivalentProperty works as a pair of rdfs:subPropertyOf, and owl:equivalentClass works as a pair of rdfs:subClassOf).
A good example is DCTerms (DCT): almost each DC property has a declared DCT subproperty, and there is also a hierarchy amongst DCT properties, eg:

dcterms:created rdfs:subPropertyOf dc:date, dcterms:date .
dcterms:date rdfs:subPropertyOf dc:date.

This means that every dcterms:created statement will expand to 3 statements. So do not load the DC ontology unless you really need these inferred dc:date.

Consider Avoiding Inverse Statements

Inverse properties (eg :p owl:inverseOf :q) offer some convenience in querying, but are never necessary:

  • SPARQL natively has bidirectional data access: instead of ?x :q ?y you can always query for ?y :p ?x.
  • You can even invert the direction in a property path: instead of ?x :p1/:q ?y, use ?x :p1/(^:p) ?y

If an ontology defines inverses but you skip inverse reasoning, you should check which of the two properties is used in a particular data set, and write your queries carefully.
The Provenance Ontology (PROV-O) has considered this dilemma thoughtfully and abstained from defining inverses, to "avoid the need for OWL reasoning, additional code, and larger queries", see http://www.w3.org/TR/prov-o/#inverse-names

Consider Avoiding Long Transitive Chains

A chain of N transitive relations (eg rdfs:subClassOf) causes GraphDB to infer and store a further (N2-N)/2 statements. If the relationship is also symmetric (e.g. in a family ontology with a predicate such as relatedTo) then there will be N2-N inferred statements.

Consider removing the transitivity and/or symmetry of relations that make long chains. Or if you must have them, consider the implementation of TransitiveProperty Through Step Property, which can be faster than the standard implementation of owl:TransitiveProperty

Consider Specialized Property Constructs

While OWL2 has very powerful class constructs, its property constructs are quite weak. Some widely-used OWL2 property constructs could be done faster.

See this draft: http://vladimiralexiev.github.io/pres/extending-owl2/ for some ideas and clear illustrations. Below we describe 3 of these ideas.
A detailed account of applying some of these ideas in a real-world setting is here: http://vocab.getty.edu/doc/#Inference. It also provides the respective rule implementations.

PropChain

Consider 2-place PropChain instead of general owl:propertyChainAxiom.

owl:propertyChainAxiom needs to use intermediate nodes and edges in order to unroll the rdf:List representing the chain. Since most chains found in practice are 2-place chains (and a chain of any length can be implemented as a sequence of 2-place chains), consider a rule like this:

Id: ptop_PropChain
  t <ptop:premise1>   p1
  t <ptop:premise2>   p2
  t <ptop:conclusion> q
  t <rdf:type> <ptop:PropChain>
  x p1 y
  y p2 z
  ----------------
  x q z

It's used with axiomatic triples like this:

@prefix ptop: <http://www.ontotext.com/proton/protontop#>.
:t a ptop:PropChain; ptop:premise1 :p1; ptop:premise2 :p2; ptop:conclusion :q.

transitiveOver

ptop:transitiveOver has been part of Ontotext's PROTON ontology since 2008. It is defined like this:

Id: ptop_transitiveOver
  p <ptop:transitiveOver> q
  x p y
  y q z
  ---------------
  x p z

It is a specialized PropChain, where premise1 and conclusion coincide. It allows you to chain p with q on the right, yielding p. For example, the inferencing of types along the class hierarchy can be expressed as:

rdf:type ptop:transitiveOver rdfs:subClassOf

TransitiveProperty Through Step Property

owl:TransitiveProperty is widely used and is usually implemented like this:

Id: owl_TransitiveProperty
  p <rdf:type> <owl:TransitiveProperty>
  x p y
  y p z
  ----------
  x p z

You may recognize this as a self-chain, thus a specialization of ptop:transitiveOver, i.e.

?p rdf:type owl:TransitiveProperty <=> ?p ptop:transitiveOver ?p

Most transitive properties comprise transitive closure over a basic "step" property. For example, skos:broaderTransitive is based on skos:broader and is implemented as:

skos:broader rdfs:subPropertyOf skos:broaderTransitive.
skos:broaderTransitive a owl:TransitiveProperty.

Now consider a chain of N skos:broader between two nodes. The owl_TransitiveProperty rule has to consider every split of the chain, thus infers the same closure between the two nodes N times, leading to quadratic inference complexity.

This can be optimized by looking for the step property s and extending the chain only at the right end:

Id: TransitiveUsingStep 
  p <rdf:type> <owl:TransitiveProperty>
  s <rdfs:subPropertyOf> p
  x p y
  y s z
  ----------
  x p z

However, this won't make the same inferences as owl_TransitiveProperty if someone inserts the transitive property explicitly, which is a bad practice anyway (see Avoid Duplicate Statements).

It is more robust to declare the step and transitive properties together using ptop:transitiveOver, eg:

skos:broader rdfs:subPropertyOf skos:broaderTransitive.
skos:broaderTransitive ptop:transitiveOver skos:broader.
Labels:
None
Enter labels to add to this page:
Please wait 
Looking for a label? Just start typing.