Uploaded image for project: 'Blazegraph (by SYSTAP)'
  1. Blazegraph (by SYSTAP)
  2. BLZG-1223

Optimize MIN/MAX with single triple pattern

    XMLWordPrintable

    Details

    • Type: New Feature
    • Status: Accepted
    • Resolution: Unresolved
    • Affects Version/s: BLAZEGRAPH_RELEASE_1_5_1
    • Fix Version/s: None
    • Component/s: Query Plan Generator
    • Labels:
      None

      Description

      Optimize queries such as the following using a reverse key-range scan of the POS index.

      PREFIX schema: <http://schema.org/>
      SELECT (MAX(?lastUpdate) as ?maxLastUpdate)
      WHERE { ?s schema:dateModified ?lastUpdate . }
      

      The MAX (or MIN) informs us that the rewrite is possible. In a way, this is similar to the COUNT() optimizations that we have already done. Since the datatype is not restricted for lastUpdate, we have to reverse (forward) scan one tuple from each possible data type key range and let MAX() (MIN()) figure out which one orders last based on the natural ordering semantics of the data types. The set of possible key ranges to be scanned includes xsd:dateTime, xsd:int, xsd:long, xsd:float, xsd:double, xsd:integer, xsd:decimal, etc. See BLZG-403 (lift key-range scan onto access path).

      If there is also a FILTER on the datatype for lastUpdate, then we can further optimize the query. At that point, we would know exactly which data type and could scan a single range.

      STEPS:

      1. Add a query hint for a reverse index scan. This will leverage the existing capability in the indices for reverse scans.

      2. Implement rewrite for reverse scan for POS (POCS) when there is an additional datatype URI filter. In this case, we only need to scan the key range for the data type associated with the filter. Thus we can always find the answer in O(1) index lookups.

      3. Implement reverse scan over key ranges when no data type is specified. In this case we must do a reverse scan over the set of key ranges in the POS (POCS) index.

      BLZG-403 Lift key-range scans onto access path.

        Attachments

          Activity

            People

            Assignee:
            michaelschmidt michaelschmidt
            Reporter:
            bryanthompson bryanthompson
            Votes:
            0 Vote for this issue
            Watchers:
            5 Start watching this issue

              Dates

              Created:
              Updated: