Query Optimisation Ontology

AI SEARCH

FLOW ALGEBRA — QUERY OPTIMISATION ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/databases/query-optimisation-ontology.html

FLOW QUERY_OPTIMISATION_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Databases"
    ONTOLOGY = "Query Optimisation Ontology"
    PURPOSE = "Formalise database query optimisation, logical and physical plans, rewrites, access paths, join ordering, statistics, cardinality estimation, cost models and plan selection."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    QUERY_OPTIMISATION
    QUERY_OPTIMISER
    QUERY
    LOGICAL_QUERY_PLAN
    PHYSICAL_QUERY_PLAN
    EXECUTION_PLAN
    PLAN_NODE
    LOGICAL_OPERATOR
    PHYSICAL_OPERATOR
    SELECTION
    PROJECTION
    JOIN
    AGGREGATION
    SORT
    SUBQUERY
    PREDICATE
    EQUIVALENCE_RULE
    REWRITE_RULE
    PREDICATE_PUSHDOWN
    PROJECTION_PUSHDOWN
    SUBQUERY_UNNESTING
    JOIN_REORDERING
    ACCESS_PATH
    TABLE_SCAN
    INDEX_SCAN
    INDEX_SEEK
    INDEX
    JOIN_ALGORITHM
    NESTED_LOOP_JOIN
    HASH_JOIN
    MERGE_JOIN
    JOIN_ORDER
    SEARCH_SPACE
    CANDIDATE_PLAN
    PLAN_ENUMERATION
    DYNAMIC_PROGRAMMING
    GREEDY_SEARCH
    HEURISTIC_SEARCH
    COST_BASED_OPTIMISATION
    RULE_BASED_OPTIMISATION
    COST_MODEL
    ESTIMATED_COST
    CPU_COST
    IO_COST
    MEMORY_COST
    NETWORK_COST
    DATABASE_STATISTICS
    TABLE_STATISTICS
    COLUMN_STATISTICS
    INDEX_STATISTICS
    CARDINALITY
    CARDINALITY_ESTIMATE
    SELECTIVITY
    SELECTIVITY_ESTIMATE
    HISTOGRAM
    DISTINCT_VALUE_COUNT
    DATA_DISTRIBUTION
    CORRELATION
    PARTITION
    PARTITION_PRUNING
    MATERIALISED_VIEW
    VIEW_REWRITE
    PARALLEL_EXECUTION
    DISTRIBUTED_QUERY
    DATA_LOCALITY
    RUNTIME_STATISTICS
    ADAPTIVE_QUERY_PROCESSING
    PLAN_CACHE
    PARAMETER
    OPTIMISATION_GOAL
    EXECUTION_TRACE
    BENCHMARK
    CONFIGURATION
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    OPTIMISES
    HAS_QUERY
    HAS_LOGICAL_PLAN
    HAS_PHYSICAL_PLAN
    HAS_PLAN_NODE
    HAS_OPERATOR
    TRANSFORMS_TO
    EQUIVALENT_TO
    REWRITES
    PUSHES_DOWN
    REORDERS
    UNNESTS
    HAS_ACCESS_PATH
    USES_INDEX
    SCANS
    SEEKS
    HAS_JOIN_ALGORITHM
    HAS_JOIN_ORDER
    ENUMERATES
    SEARCHES
    HAS_CANDIDATE_PLAN
    HAS_COST_MODEL
    HAS_ESTIMATED_COST
    HAS_CPU_COST
    HAS_IO_COST
    HAS_MEMORY_COST
    HAS_NETWORK_COST
    HAS_STATISTICS
    HAS_CARDINALITY
    ESTIMATES_CARDINALITY
    HAS_SELECTIVITY
    ESTIMATES_SELECTIVITY
    HAS_HISTOGRAM
    HAS_DISTRIBUTION
    HAS_CORRELATION
    PRUNES_PARTITION
    USES_MATERIALISED_VIEW
    PARALLELISES
    DISTRIBUTES
    HAS_DATA_LOCALITY
    HAS_RUNTIME_STATISTICS
    ADAPTS
    HAS_PARAMETER
    HAS_OPTIMISATION_GOAL
    SELECTS_PLAN
    EXECUTED_AS
    BENCHMARKED_BY
    HAS_CONFIGURATION
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    QUERY_TEXT
    PARSED_QUERY
    DATABASE_SCHEMA
    LOGICAL_PLANS
    PHYSICAL_OPERATORS
    INDEX_METADATA
    TABLE_STATISTICS
    COLUMN_STATISTICS
    INDEX_STATISTICS
    HISTOGRAM_DATA
    DATA_DISTRIBUTIONS
    PARTITION_METADATA
    MATERIALISED_VIEW_METADATA
    COST_MODEL_PARAMETERS
    HARDWARE_AND_RUNTIME_CONTEXT
    QUERY_PARAMETERS
    PLAN_CACHE_DATA
    EXECUTION_PLANS
    RUNTIME_STATISTICS
    EXECUTION_TRACES
    BENCHMARK_DATA
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_QUERY_IDENTIFIERS
    NORMALISE_LOGICAL_OPERATOR_NAMES
    NORMALISE_PHYSICAL_OPERATOR_NAMES
    NORMALISE_PLAN_NODE_IDENTIFIERS
    NORMALISE_INDEX_IDENTIFIERS
    NORMALISE_JOIN_ALGORITHM_NAMES
    NORMALISE_JOIN_ORDER_REPRESENTATIONS
    NORMALISE_STATISTICS_UNITS
    NORMALISE_CARDINALITY_AND_SELECTIVITY_VALUES
    NORMALISE_COST_UNITS
    NORMALISE_PARTITION_IDENTIFIERS
    NORMALISE_PARAMETER_CONTEXT
    NORMALISE_OPTIMISATION_GOALS
    RESOLVE_QUERY_PLAN_OPERATOR_AND_STATISTIC_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS QUERY_OPTIMISATION_PIPELINE {
    QUERY
      -> PARSE_AND_VALIDATE
      -> INITIAL_LOGICAL_PLAN
      -> LOGICAL_REWRITES
      -> CANDIDATE_LOGICAL_PLANS
      -> PHYSICAL_OPERATOR_MAPPING
      -> PLAN_ENUMERATION
      -> CARDINALITY_AND_COST_ESTIMATION
      -> PLAN_COMPARISON
      -> SELECTED_EXECUTION_PLAN
      -> EXECUTION_AND_FEEDBACK
  }

  PROCESS LOGICAL_REWRITE_REASONING {
    LOGICAL_PLAN
      -> EQUIVALENCE_RULES

    PREDICATE_FILTER
      -> PREDICATE_PUSHDOWN

    UNUSED_ATTRIBUTES
      -> PROJECTION_PUSHDOWN

    SUBQUERY
      -> SUBQUERY_UNNESTING_IF_SEMANTICALLY_VALID

    JOIN_SET
      -> JOIN_REORDERING_CANDIDATES

    REWRITTEN_PLAN
      -> SEMANTIC_EQUIVALENCE_CHECK
  }

  PROCESS ACCESS_PATH_REASONING {
    TABLE_REFERENCE + PREDICATES
      -> ACCESS_PATH_CANDIDATES

    ACCESS_PATH_CANDIDATES
      -> TABLE_SCAN_INDEX_SCAN_OR_INDEX_SEEK

    INDEX_METADATA + SELECTIVITY
      -> INDEX_USEFULNESS_ESTIMATE

    ACCESS_PATH
      -> ESTIMATED_IO_CPU_AND_MEMORY_COST
  }

  PROCESS CARDINALITY_REASONING {
    BASE_RELATION
      -> TABLE_STATISTICS
      -> BASE_CARDINALITY

    PREDICATE
      -> COLUMN_STATISTICS + HISTOGRAM + DISTRIBUTION
      -> SELECTIVITY_ESTIMATE

    INPUT_CARDINALITY * SELECTIVITY_ESTIMATE
      -> OUTPUT_CARDINALITY_ESTIMATE

    JOIN
      -> JOIN_KEY_STATISTICS_AND_CORRELATION_ASSUMPTIONS
      -> JOIN_CARDINALITY_ESTIMATE
  }

  PROCESS JOIN_ORDER_REASONING {
    JOIN_GRAPH
      -> POSSIBLE_JOIN_ORDERS

    SEARCH_STRATEGY
      -> ENUMERATED_CANDIDATES

    EACH_CANDIDATE
      -> INTERMEDIATE_CARDINALITIES + JOIN_COSTS

    COST_COMPARISON
      -> PREFERRED_JOIN_ORDER
  }

  PROCESS PHYSICAL_OPERATOR_REASONING {
    LOGICAL_OPERATOR
      -> PHYSICAL_IMPLEMENTATION_CANDIDATES

    JOIN
      -> NESTED_LOOP_HASH_OR_MERGE_JOIN

    PHYSICAL_CANDIDATE
      -> RESOURCE_AND_ORDERING_PROPERTIES

    PROPERTIES + COST
      -> OPERATOR_SELECTION
  }

  PROCESS COST_REASONING {
    CANDIDATE_PLAN
      -> PLAN_OPERATORS

    EACH_OPERATOR
      -> CPU_IO_MEMORY_NETWORK_COST

    OPERATOR_COSTS + INTERMEDIATE_RESULT_COSTS
      -> TOTAL_ESTIMATED_COST

    OPTIMISATION_GOAL
      -> COST_COMPARISON_POLICY
  }

  PROCESS PARTITION_REASONING {
    QUERY_PREDICATES + PARTITION_METADATA
      -> RELEVANT_PARTITIONS

    EXCLUDED_PARTITIONS
      -> PARTITION_PRUNING

    RELEVANT_PARTITIONS
      -> REDUCED_SCAN_AND_NETWORK_COST
  }

  PROCESS DISTRIBUTED_REASONING {
    DISTRIBUTED_QUERY
      -> DATA_LOCATIONS
      -> LOCAL_AND_REMOTE_OPERATORS

    REMOTE_OPERATORS
      -> NETWORK_TRANSFER_COST

    DATA_LOCALITY
      -> PLAN_COST_ADJUSTMENT
  }

  PROCESS ADAPTIVE_REASONING {
    EXECUTION_PLAN
      -> RUNTIME_STATISTICS

    RUNTIME_STATISTICS
      -> COMPARE_ESTIMATED_AND_ACTUAL_CARDINALITIES

    SIGNIFICANT_DEVIATION
      -> ADAPTIVE_REOPTIMISATION_CANDIDATE
  }

  RULES {
    IF QUERY_PLAN_IS_COMPARED
    THEN PRESERVE QUERY_SCHEMA_STATISTICS_PARAMETERS_AND_CONFIGURATION_CONTEXT

    IF LOGICAL_REWRITE_IS_APPLIED
    THEN REQUIRE SEMANTIC_EQUIVALENCE_UNDER_DATABASE_SEMANTICS

    IF CARDINALITY_IS_ESTIMATED
    THEN PRESERVE STATISTICS_SOURCE_AGE_DISTRIBUTION_AND_CORRELATION_ASSUMPTIONS

    IF INDEX_ACCESS_IS_SELECTED
    THEN PRESERVE PREDICATE_SELECTIVITY_INDEX_STRUCTURE_AND_COVERAGE_CONTEXT

    IF JOIN_ORDER_IS_SELECTED
    THEN PRESERVE INTERMEDIATE_CARDINALITY_AND_COST_ESTIMATES

    IF DISTRIBUTED_PLAN_IS_ANALYSED
    THEN INCLUDE NETWORK_DATA_LOCALITY_AND_PARTITION_CONTEXT

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND QUERY_OPTIMISATION_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        QUERY_IDENTITY_CERTAINTY,
        SCHEMA_CERTAINTY,
        STATISTICS_FRESHNESS,
        CARDINALITY_ESTIMATE_QUALITY,
        COST_MODEL_QUALITY,
        PLAN_ENUMERATION_COMPLETENESS,
        RUNTIME_EVIDENCE_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF STATISTICS_ARE_STALE_OR_MISSING
    THEN REDUCE_CARDINALITY_AND_PLAN_CONFIDENCE

    IF CORRELATED_COLUMNS_ARE_MODELLED_AS_INDEPENDENT_WITHOUT_EVIDENCE
    THEN REDUCE_SELECTIVITY_CONFIDENCE

    IF ESTIMATES_AND_REPEATED_RUNTIME_EVIDENCE_CONVERGE
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        QUERY_IDENTIFIER,
        LOGICAL_SEMANTICS,
        SCHEMA_VERSION,
        PARAMETER_CONTEXT,
        OPTIMISATION_GOAL,
        CONFIGURATION
      )

    IF EQUIVALENCE_KEY(A) == EQUIVALENCE_KEY(B)
    THEN A SEMANTICALLY_EQUIVALENT_TO B
    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    QUERY_OPTIMISATION != QUERY_EXECUTION
    LOGICAL_PLAN != PHYSICAL_PLAN
    ESTIMATED_COST != ACTUAL_RUNTIME
    CARDINALITY_ESTIMATE != ACTUAL_CARDINALITY
    SELECTIVITY != CARDINALITY
    RULE_BASED_OPTIMISATION != COST_BASED_OPTIMISATION
    INDEX_SCAN != INDEX_SEEK
    JOIN_ORDER != JOIN_ALGORITHM
    PREDICATE_PUSHDOWN != PROJECTION_PUSHDOWN
    TABLE_STATISTICS != COLUMN_STATISTICS
    PLAN_CACHE_REUSE != GUARANTEED_OPTIMAL_PLAN
    LOWER_ESTIMATED_COST != GUARANTEED_LOWER_WALL_CLOCK_TIME
    OPTIMAL_PLAN_DEPENDS_ON_SEARCH_SPACE_COST_MODEL_STATISTICS_AND_CONFIGURATION
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_QUERY_IDENTIFIER
    CHECK_SCHEMA_VERSION
    CHECK_LOGICAL_PLAN
    CHECK_REWRITE_EQUIVALENCE
    CHECK_PHYSICAL_OPERATOR_CANDIDATES
    CHECK_INDEX_METADATA
    CHECK_STATISTICS
    CHECK_CARDINALITY_ESTIMATES
    CHECK_SELECTIVITY_ESTIMATES
    CHECK_JOIN_ORDERS
    CHECK_JOIN_ALGORITHMS
    CHECK_COST_MODEL
    CHECK_PARTITION_PRUNING
    CHECK_DISTRIBUTED_COSTS_IF_APPLICABLE
    CHECK_PLAN_CACHE_CONTEXT
    CHECK_RUNTIME_FEEDBACK
    CHECK_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_QUERY_OPTIMISATION_ENTITIES
    LOGICAL_PLAN_RELATIONS
    REWRITE_RELATIONS
    ACCESS_PATH_RELATIONS
    INDEX_SELECTION_RELATIONS
    CARDINALITY_AND_SELECTIVITY_RELATIONS
    JOIN_ORDER_RELATIONS
    PHYSICAL_OPERATOR_RELATIONS
    COST_MODEL_RELATIONS
    CANDIDATE_PLAN_RELATIONS
    SELECTED_PLAN_RELATIONS
    PARTITION_PRUNING_RELATIONS
    DISTRIBUTED_PLAN_RELATIONS
    ADAPTIVE_OPTIMISATION_RELATIONS
    PLAN_CACHE_RELATIONS
    RUNTIME_COMPARISON_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON QUERY_SCHEMA_STATISTICS_OR_CONFIGURATION_CHANGE {
      NORMALISE
      RESOLVE_QUERY_PLAN_OPERATOR_AND_STATISTIC_IDENTITIES
      UPDATE_LOGICAL_PLAN
      UPDATE_STATISTICS_AND_CARDINALITIES
      REENUMERATE_AFFECTED_PLANS
      RECOMPUTE_COSTS
      RESELECT_EXECUTION_PLAN
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON NEW_RUNTIME_EVIDENCE {
      LINK_EVIDENCE
      UPDATE_ACTUAL_CARDINALITIES_AND_RESOURCE_USAGE
      COMPARE_ESTIMATES_WITH_ACTUALS
      UPDATE_ADAPTIVE_OPTIMISATION_CONTEXT
      UPDATE_CONFIDENCE
      RECORD_PROVENANCE
    }

    ON ONTOLOGY_REVISION {
      REMAP_TERMS
      CHECK_SEMANTIC_EQUIVALENCE
      IDENTIFY_DEPRECATED_TERMS
      MIGRATE_RELATIONSHIPS
      PRESERVE_PRIOR_VERSION_REFERENCES
    }
  }

  FLOW_HASH {
    HASH_INPUT =
      CANONICALISE(
        ENTITY_TYPES,
        RELATIONSHIPS,
        RULES,
        CONFIDENCE,
        SEMANTIC_EQUIVALENCE,
        REASONING_CONSTRAINTS,
        UPDATE_MODEL
      )

    FLOW_HASH = SHA256(HASH_INPUT)
  }

  AI_CONSUMPTION {
    INDEX {
      ONTOLOGY
      ENTITY_TYPES
      RELATIONSHIPS
      RULES
      OUTPUTS
    }

    RETRIEVE {
      BY_QUERY
      BY_LOGICAL_PLAN
      BY_PHYSICAL_PLAN
      BY_OPERATOR
      BY_INDEX
      BY_JOIN_ORDER
      BY_STATISTIC
      BY_CARDINALITY
      BY_SELECTIVITY
      BY_COST
      BY_CANDIDATE_PLAN
      BY_SELECTED_PLAN
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_LOGICAL_REWRITES
      ANALYSE_ACCESS_PATHS
      ESTIMATE_CARDINALITIES
      ESTIMATE_SELECTIVITIES
      ENUMERATE_JOIN_ORDERS
      SELECT_PHYSICAL_OPERATORS
      COMPUTE_PLAN_COSTS
      ANALYSE_PARTITION_PRUNING
      ANALYSE_DISTRIBUTED_PLANS
      ANALYSE_ADAPTIVE_OPTIMISATION
      ANALYSE_PLAN_CACHE
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_QUERY_OPTIMISATION_FROM_QUERY_EXECUTION
      DISTINGUISH_LOGICAL_FROM_PHYSICAL_PLANS
      PRESERVE_QUERY_SCHEMA_STATISTICS_PARAMETER_COST_MODEL_AND_CONFIGURATION_CONTEXT
      DISTINGUISH_ESTIMATED_FROM_ACTUAL_CARDINALITY_AND_COST
      PRESERVE_PLAN_ENUMERATION_AND_RUNTIME_EVIDENCE
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_OPTIMISATION_INFERENCE
    }
  }

  TERMINAL {
    RESULT =
      VALIDATED(
        SEMANTICALLY_NORMALISED(
          EVIDENCE_LINKED(
            CONFIDENCE_AWARE(
              QUERY_OPTIMISATION_KNOWLEDGE
            )
          )
        )
      )
  }
}

END FLOW