Added a FullRelationScan operation. #164

floriankramer · 2018-12-15T16:49:36Z

This implements a FullRelationScan opertion, which allows for queries of the form:

SELECT ?a WHERE {
 ?a ?b ?c
}
GROUP BY ?a

as we had discussed. The current implementation is based upon the FullRelationMetadata stored in the index. It does not do any optimizations (e.g. applying prefix filters when scanning the metadata or caching a prefix of the result and applying LIMIT early).
The FullRelationScan is used if all of these three conditions are met by the query:

There must only be one triple which must only contain variables
Only one of these variables (and optionally its count) must be selected.
The query must group on the selected variable.

niklas88

LGTM though I did add some questions. Will be interesting to see what kind of performance we get from this.

niklas88 · 2018-12-17T09:55:06Z

src/index/MetaDataHandler.h

  // ____________________________________________________________
  ConstIterator cend() const { return _map.end(); }

  // ____________________________________________________________
  Iterator end() { return _map.end(); }

+  // ____________________________________________________________
+  ConstIterator end() const { return _map.end(); }


There is already cend()

I use a for loop to iterate through the meta data right now (for (auto e : meta)) and that seems to only use begin and end, but I needed a constant version of those as I only had a reference to the constant metadata. std::vector seems to also have a constant end and a separate also constant cend.

What about for (const auto& e: meta) {…}?

@niklas88 : the for (const auto...) overload uses the const overload to begin and end.
So they are necessary for Florians use case.
@floriankramer : Niklas is right, MetaData should by all means be accessed in a const way.
Btw: By a second thought I don't think you will have much fun with this implementation since iterating over the MetaData takes a very long time. I think storing the ids of all subjects, objects and predicates in a sorted way on disk would be much faster.

@joka921 Is there currently any non constant access? The Index only returns a constant reference.
I tried running the current implementation on the wikidata full dataset on galera and aborted the query after it took more than a full minute, so we definitely need to precompute this, preferably during the index building.

@floriankramer I think @joka921 was only talking about the for (auto e: meta) in your comment which didn't make the constness explicit.

niklas88 · 2018-12-17T09:57:28Z

src/index/MetaDataHandler.h

@@ -215,12 +215,18 @@ class MetaDataWrapperHashMap {
  // __________________________________________________________________
  Iterator begin() { return _map.begin(); }

+  // __________________________________________________________________
+  ConstIterator begin() const { return _map.begin(); }


I'd use cbegin() even though in std::vector there is also a const begin() see https://en.cppreference.com/w/cpp/container/vector/begin

ad_utility::HashMap does not have a cbegin, and we can't add it using a simple using statement, (that leads to g++ complaining that there is no matching member).

I see, ok this was just style nitpicking anyway

niklas88 · 2018-12-17T10:19:57Z

src/engine/FullRelationScan.cpp

+  return os.str();
+}
+
+size_t FullRelationScan::getResultWidth() const { return 2; }


Is this correct when there is not COUNT?

The count is always returned by the operation. When it is not selected it is discarded during the json assembly.

What about when using this as a subquery e.g. to join it with wikibase:claim?

niklas88 · 2018-12-17T10:27:33Z

src/engine/FullRelationScan.cpp

+                   std::to_string(static_cast<int>(type)));
+    }
+
+    for (const std::pair<size_t, const FullRelationMetaData&> elem :


All these ifs do basically the same except for which meta data is used and using a different type for predicates. I think this could be handled in a templated method which just gets called with index.getXyzMeta() and index.getNofXyz()

niklas88 · 2018-12-17T10:31:08Z

src/index/Index.h

+      return _psoMeta;
+    } else {
+      AD_THROW(ad_semsearch::Exception::CHECK_FAILED,
+               "Can only use the spo metadta if all 6 permutations "


Is this true? I mean we still have _psoMetah?

I just forgot to remove the check after copying the method. It's gone now.

floriankramer · 2019-01-25T13:04:16Z

Given the bad performance of this implementation on large datasets, and the possiblity of extracting similar data to what this provided using schema:name I'll close this pr for now.

floriankramer requested a review from niklas88 December 15, 2018 16:49

niklas88 reviewed Dec 17, 2018

View reviewed changes

floriankramer added 2 commits December 17, 2018 16:03

Added a FullRelationScan operation.

9521c89

Code cleanup and minor bugfixes.

53111c3

floriankramer force-pushed the full_relation_scan branch from 45b702f to 53111c3 Compare December 17, 2018 15:05

floriankramer closed this Jan 25, 2019

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Added a FullRelationScan operation. #164

Added a FullRelationScan operation. #164

floriankramer commented Dec 15, 2018

niklas88 left a comment

niklas88 Dec 17, 2018

floriankramer Dec 17, 2018

niklas88 Dec 17, 2018

joka921 Dec 17, 2018

floriankramer Dec 18, 2018

niklas88 Dec 18, 2018

niklas88 Dec 17, 2018

floriankramer Dec 17, 2018 •

edited

niklas88 Dec 17, 2018

niklas88 Dec 17, 2018

floriankramer Dec 17, 2018

niklas88 Dec 17, 2018

niklas88 Dec 17, 2018

floriankramer Dec 17, 2018

niklas88 Dec 17, 2018

floriankramer Dec 17, 2018

floriankramer commented Jan 25, 2019

Added a FullRelationScan operation. #164

Added a FullRelationScan operation. #164

Conversation

floriankramer commented Dec 15, 2018

niklas88 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

floriankramer Dec 17, 2018 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

floriankramer commented Jan 25, 2019

floriankramer Dec 17, 2018 •

edited