TRIEJOIN

Triejoin is an optimized calculation algorithm for OLAP rules.

Triejoin evaluates rules through the leapfrog triejoin algorithm. The algorithm concurrently sweeps the compressed sparse index (CSI) data structures of all referenced cubes, instead of evaluating cells individually.

Use the Triejoin algorithm for performance-critical scenarios. When you write or tune rules, use formula patterns that qualify for Triejoin.

See the Supported constructs section.

Avoid functions that prevent Triejoin. Rewrite rules to remove unsupported constructs to improve performance, especially for rules that process large cell ranges.

Triejoin is enabled by default at the database level. You can control the algorithm per database in the Database/Properties/RulesTriejoinUsage XML property.

Some rule formulas don't qualify for Triejoin. During rule compilation, formulas are analyzed and, if unsupported constructs are detected, the standard CSI sweep is applied. The rule functional behavior remains unchanged and only the evaluation method changes.

Verifying the Triejoin usage with RuleDebug

You can verify whether Triejoin is used by a rule with the RuleDebug logging feature.

To use RuleDebug, perform these steps:

  1. Select EPM Administration > Dashboards > Manage Application Logs.
  2. Click + Add to create a new log filter.
  3. Specify information in these fields:
    • Details: Specify the name of the filter.
    • Events: Select Rule Debug Start and Rule Debug Stop.
    • Minimum Level: Select Debug.
    • Application: Select the application.
  4. Click Save.
  5. Once the log filter is created, select it, and click Start to activate the RuleDebug logging.

The RuleDebug output contains these two lines:

  • Rule flag: Shows compilation flags. These rule flags' indicators are used:
    • RF_TRIEJOIN: Indicates that a rule is eligible for Triejoin during compilation.
    • RF_CONJUNCTIVE_SWEEP or RF_DISJUNCTIVE_SWEEP: Indicates the sweep type.
    Note: Other rule flags such as RF_BaseCells, RF_ConsCells, RF_Pull, RF_Stet, and RF_Complex may appear in the RuleDebug output. These flags classify the rule type and don't affect Triejoin eligibility.
  • Rule execution flag: Shows runtime flags. These rule execution flags' indicators are used:
    • RP_OPTIMIZEDREFERENCES: Indicates that Triejoin was skipped at runtime because references had been merged. See the Additional runtime conditions section.
    • RP_PARAMETERALWAYSERROR: Indicates that Triejoin was skipped because all parameters had been resolved to errors.
    Note: Other execution flags such as RP_RECURSIVE and RP_JITACTIVE can appear in the RuleDebug output. These flags don't affect Triejoin eligibility.

A rule is run with Triejoin when RF_TRIEJOIN exists in the rule flags, and neither RP_OPTIMIZEDREFERENCES nor RP_PARAMETERALWAYSERROR exists in the execution flags.

Supported constructs

These constructs are compatible with the Triejoin engine. A rule formula must include only these constructs to remain eligible for Triejoin processing.

DB() function

The DB() function is the only rule that is compatible with Triejoin.

DB('SalesCube', 'Elem1', 'Elem2', 'Elem3')

All DB() function parameters must be valid at runtime. These parameters are available:

  • The referenced cube: Required.
  • The number of parameters: Must match the cube's dimension count.
  • The referenced elements: Required.

Invalid parameters cause a fallback at the prefetch time.

See the Additional runtime conditions section.

Cell references (area references)

Direct cell references that use area notation are compatible with Triejoin.

[Dimension:'Element']: Triejoin is eligible.

[Dim1:'Elem1', Dim2:'Elem2']: Triejoin is eligible.

You can use the !DimensionName element syntax in formulas. When used inside DB() calls, it remains Triejoin-eligible.

DB('Cube', !Dim1, 'Elem2', 'Elem3'): Triejoin is eligible.

You can combine multiple cell references into a single rule. Cells remain Triejoin-eligible when the rule doesn't include unsupported constructs.

Triejoin applies only when the formula contains at least one cell reference.

Arithmetic operators

Arithmetic operators, such as *, /, +, and -, are compatible with Triejoin when used between cell references or DB() functions.

Multiplication (*) and division (/) perform a conjunctive sweep that intersects data from cell references. Only cells with values in all references are visited.

Addition (+) and subtraction (-) operator between two cell references perform a disjunctive sweep. The operation unions data from cell references. Cells that contain a value in any reference are visited.

[Dim:'Elem1'] * [Dim:'Elem2']: Triejoin is eligible (conjunctive).

[Dim:'Elem1'] + [Dim:'Elem2']: Triejoin is eligible (disjunctive).

[Dim:'Elem1'] * [Dim:'Elem2'] + [Dim:'Elem3']: Triejoin is eligible (disjunctive because addition is used).

Unary operators on references

Unary + and - operators that are applied to cell references are compatible with Triejoin. These operators are treated as unary and not as binary addition or subtraction.

- [Dim:'Elem']: Triejoin is eligible.

- 2 * [Dim:'Elem']: Triejoin is eligible.

- ( 2 * [Dim:'Elem'] ) : Triejoin is eligible.

Numeric constants in a multiplicative context

Numeric constants that are used as factors in multiplication or division with cell references are compatible with Triejoin.

2 * [Dim:'Elem']: Triejoin is eligible.

[Dim:'Elem'] / 100: Triejoin is eligible.

Unsupported constructs

These constructs result in the rule fall back to the standard CSI sweep engine.

Functions (except DB())

All functions except DB() disable Triejoin. The most common cases of disabling Triejoin include:

  • The IF() function is not compatible with Triejoin. Any use of the IF() function in a rule formula disables Triejoin optimization for that rule, regardless of the condition or branch expressions.

    IF([Dim:'Elem'] > 0, 1, 2): Triejoin is not used.

    IF([Dim:'A'] > [Dim:'B'], [Dim:'A'], [Dim:'B']): Triejoin is not used even though all operands are cell references.

  • The GETATTR() function (also available as ATTR()) is not compatible with Triejoin.

    GETATTR('Product', !Product, 1, 'Price'): Triejoin is not used.

This table shows the list of unsupported functions that are grouped by category:

Category Functions
Mathematical functions
  • ABS
  • ACOS
  • ASIN
  • ATAN
  • COS
  • EXP
  • INT
  • LN
  • LOG
  • MAX
  • MIN
  • MOD
  • PI
  • ROUND
  • ROUNDUP
  • SIGN
  • SIN
  • SQRT
  • TAN
  • FV
String functions
  • UPPER
  • LOWER
  • CAPIT
  • TRIM
  • STR
  • SUBST
  • FILL
  • INSRT
  • DELET
  • SCAN
  • LONG
  • CHAR
  • CODE
  • NUMBR
Dimension element functions
  • DE.TYPE
  • DE.LEVEL
  • DE.INDEX
  • DE.NAME
  • DE.PARENTNAME
  • DE.CHILDNAME
  • DE.PARENTSCOUNT
  • DE.CHILDRENCOUNT
  • DE.COUNT
  • DE.FIRST
  • DE.NEXT
  • DE.PREV
  • DE.ISCHILD
  • DE.SIBLING
  • DE.WEIGHT
  • DE.ISDESCENDANT
  • DE.DESCENDANTSCOUNT
  • DE.LEAFCHILDRENCOUNT
  • DE.LEAFDESCENDANTSCOUNT
  • DIM.TOPLEVEL
  • TDIM.NAME
Hierarchy functions
  • OPENINGPERIOD
  • CLOSINGPERIOD
  • DE.HSIBLING
  • HOPENINGPERIOD
  • HCLOSINGPERIOD
  • ELEMENTINHIERARCHY
Other functions
  • STET
  • ISNULL
  • ISSTRING
  • ISNUMBER
  • COORDINATE
  • DATE
  • DATES
  • DAYNO
  • TODAY
  • ERROR
  • LOGDEBUG
  • LOGERROR

MIN([Dim:'A'], [Dim:'B']): Triejoin is not used even though both arguments are cell references.

Numeric constants in an additive context (value generation)

A standalone numeric constant in addition or subtraction disables Triejoin, because Triejoin sweeps only across existing values in CSI structures. Adding a constant to a cell requires value generation for cells without stored data, which isn't supported by the sweep algorithm.

[Dim:'Elem'] + 5: Triejoin is not used.

[Dim:'Elem'] - 100: Triejoin is not used.

1 - 2 * [Dim:'Elem']: Triejoin is not used 1 is an additive constant term.

Numeric constants in a multiplicative context remain Triejoin-eligible. For example, 2 * [Dim:'Elem'] is eligible because multiplication by constant scales existing values and does not create new cells.

Rules without cell references

Rules without cell references or DB() functions aren't eligible for Triejoin because no CSI data is availabe to sweep over.

42: Triejoin is not used.

PI: Triejoin is not used. PI is a function that independently disables Triejoin.

Additional runtime conditions

A rule can compile as Triejoin-eligible but can revert to the standard CSI sweep during the prefetch phase at runtime.

If query filters narrow dimensions so that multiple cell references become equivalent and can be merged into a single optimized reference, Triejoin is not used. In this case, the optimized single-reference path is recommended.

If all DB() function parameters return errors at the prefetch time, for example, non-existent cube or elements, or incorrect parameter count, the rule is marked as always-error and Trejoin is not used. All affected cells return errors.

These runtime conditions don't change the RF_TRIEJOIN compilation flag. The flag remains set, but the Triejoin run path isn't used.

Override comments

Rule formulas can include special comments to control Triejoin behavior.

These comments override automatic detection:

  • /* TRIEJOIN */: Specify this comment at the beginning of the formula to enable Triejoin for the rule.
  • /* NO_TRIEJOIN */: Specify this comment at the beginning of the formula to disable Triejoin for the rule.

The /* TRIEJOIN */ comment sets the initial Triejoin flag before analysis. If unsupported constructs are detected during compilation, Triejoin is disabled even if the comment exists.

The /* NO_TRIEJOIN */ comment disables Triejoin for the rule. The compiler doesn't enable Triejoin thereafter.

Configuration

Triejoin is enabled by default for all databases.

You can disable Triejoin per database with this Database PutProperties method in the XML API:

<Alea:Document xmlns:Alea="http://www.misag.com"> 
  <Alea:Request Class="Database" Method="PutProperties"> 
    <Alea:Properties> 
      <Alea:RulesTriejoinUsage Enabled="false" /> 
    </Alea:Properties> 
  </Alea:Request> 
</Alea:Document>

To verify the current setting, use the Database GetProperties method. The response includes the RulesTriejoinUsage XML element with the Enabled attribute that indicates the current state. If the RulesTriejoinUsage element doesn't exist, Triejoin is enabled by default.

Changing the setting causes recompilation of all rules in the database.