Pattern Trick for Objects #366

floriankramer · 2020-11-27T13:05:16Z

This pr will do two things:

Reduce the number of bytes used to represent predicate ids within patterns and the hasPredicate relation
Add an object based hasPredicate relation which also supports the pattern trick

floriankramer · 2020-12-04T14:09:08Z

TODO:

Ignore literals when generating the pattern trick for objects
Implement usage of the pattern trick for objects data
testing

hannahbast · 2020-12-27T01:03:15Z

I just realized the following phenomenon regarding the efficiency of the "normal" pattern trick + I assume this also applies for the new code. Namely, consider the following query on Fbeasy:

SELECT ?entity (COUNT(?predicate) AS ?count) WHERE {
  ?entity ql:has-predicate ?predicate
}
GROUP BY ?entity 
ORDER BY DESC(?count)

This query is easy using patterns. For each entity, we just need to compute the size of its pattern. We do not even have to materialized the patterns for that. However, that is what seems to happen and hence the query takes very long, even on Fbeasy.

It's an important query because it gives a natural way to order entities for any knowledge base., without assuming that any other predicate exists that is a good measure of popularity

* When an input to the HasPredicateScan from a subquery has no predicates associated with it the result computation would terminate early. * The full scan always used the subject metadata to acquire its output size

floriankramer · 2021-02-12T13:42:00Z

@hannahbast Those types of queries should now be supported in this pr

joka921

In general I like this very much. There are some general remarks:

This PR is too long. It took me 3 days to review, and contains three seperate features (Objects, Counting, Compression) that each are non-trivial. Please split up features in the future to make the review process more interactive.
The general functionality is fine, I had some remarks on software architecture.
For some reason you suddenly switched to snake_case whereas the rest of QLever uses camelCase. I think we should stick with a naming scheme for consistency.
@hannahbast suggested keeping the original ql:has-predicate like you did, but additionally adding the alias ql:subject-has-predicate to match your ql:object-has-predicate for consistency.
If you have any questions or remarks, don't hesitate to contact me via comments here or telephone.

joka921 · 2021-03-23T15:50:40Z

e2e/scientists_queries.yaml

+      - num_cols: 2
+      - selected: ["?entity", "?count"]
+      - contains_row: ["<Australia>", "5"]
+      - contains_row: ["<Astronomer>", "4"]


I would also like an e2e test for the ql:object-has-predicate where the ?entity is already constrained (e.g. Geographer-Object-Has-Predicate)

joka921 · 2021-03-23T15:55:18Z

src/engine/EntityCountPredicates.cpp

+      _predicateVarName("predicate"),
+      _countVarName("count"),
+      _count_for(CountType::SUBJECT) {}
+


I would prefer setting the defaults directly with the member definition, it is error-prone to always manually specify the defaults for members that are not initialized by constructor arguments. E.G the _subjectColumnIndex Always seems to be 0 unless it is not specified.

joka921 · 2021-03-23T15:55:35Z

src/engine/EntityCountPredicates.cpp

+      _predicateVarName("predicate"),
+      _countVarName("count"),
+      _count_for(CountType::SUBJECT) {}
+


joka921 · 2021-03-23T15:55:42Z

src/engine/EntityCountPredicates.cpp

+      _predicateVarName("predicate"),
+      _countVarName("count"),
+      _count_for(CountType::SUBJECT) {}
+


joka921 · 2021-03-23T15:59:12Z

src/engine/EntityCountPredicates.cpp

+
+// _____________________________________________________________________________
+void EntityCountPredicates::setCountFor(CountType count_for) {
+  _count_for = count_for;


countFor (camelCase)

joka921 · 2021-03-26T14:32:52Z

src/index/PatternIndex.cpp

+
+  // This is not inside a templated method as the PSO metadata is based upon
+  // HashMaps which need to be treated differently
+  TripleVec::bufreader_type reader(*vocabData->idTriples);


I don't understand this comment, and I don't think it is necessary. We don't deal with the PSO metadata here at all.

joka921 · 2021-03-26T14:38:24Z

src/index/PatternIndex.cpp

+    Id langPredLowerBound, Id langPredUpperBound, IndexMetaDataHmap& meta_data,
+    const std::string& filename_base) {
+  // This is not inside a templated method as the PSO metadata is based upon
+  // HashMaps which need to be treated differently


Do you mean: We only use this with PSO and PSO is always MetaDataHmap and thus we need no template?
I think this can be left out, it automatically breaks the compilation if we change this.
The only important INFO is that meta_data has to be sorted by the P column.

joka921 · 2021-03-26T14:41:50Z

src/index/PatternIndex.cpp

+  for (size_t i = 0; i < _predicate_local_to_global_ids.size(); ++i) {
+    _predicate_global_to_local_ids.try_emplace(
+        _predicate_local_to_global_ids[i], i);
+  }


Duplicate code block here, can be removed.

joka921 · 2021-03-26T14:44:21Z

src/index/PatternIndex.cpp

+      _predicate_global_to_local_ids, &_object_meta_data, _maxNumPatterns,
+      langPredLowerBound, langPredUpperBound, meta_data, file);
+
+  _initialized = true;


what is the purpose of this_initialized variable, is it checked later on?
It also gets true if we are halfway initialized (e.g. Objects but no subjects)

joka921 · 2021-03-26T14:53:16Z

src/index/PatternIndex.cpp

+             "The requested feature requires a loaded patterns file ("
+             "do not specify the --no-patterns option for this to work)");
+  }
+}


I only skimmed this last part, I assume it is mostly a copy of the original pattern creation with adapted templated types.
In general we should use a proper symmetric serialization mechanism in the future to avoid mistakes with the manual read and write calls.

floriankramer force-pushed the reversed_pattern_trick branch 5 times, most recently from 7264422 to 945b7b8 Compare December 4, 2020 13:00

floriankramer added 6 commits January 22, 2021 12:03

Added support for using less bytes for pattern trick predicate ids.

1a10430

Refactored the patterns part of the index, fixed patterns loading bugs.

9f30a00

Fixed the index test.

2c9c714

Readded support for adding patterns to an existing index

9a584a2

Added a pattern generation pass for objects based patterns.

f063a59

Updated the engine to ecplicitly use subject pattern data.

ab7b49f

floriankramer force-pushed the reversed_pattern_trick branch from b95592d to ab7b49f Compare January 22, 2021 11:03

floriankramer added 6 commits January 29, 2021 12:20

Added support for object-has-predicate to CountAvailablePredicates.

1ba19eb

Added object-has-predicate support to HasPredicateScan

9b7e032

Fixed two bugs in the HasPredicateScan operation

70607a1

* When an input to the HasPredicateScan from a subquery has no predicates associated with it the result computation would terminate early. * The full scan always used the subject metadata to acquire its output size

Renamed CountAvailablePredicates to PredicateCountEntities

01c4558

Added an EntityCountPredicates operation.

0ad20e9

Integrated EnityCountPredicates into the QueryPlanner

86f7967

floriankramer marked this pull request as ready for review February 12, 2021 13:42

joka921 reviewed Mar 26, 2021

View reviewed changes

joka921 force-pushed the master branch from b553831 to 6680993 Compare May 5, 2021 08:18

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Pattern Trick for Objects #366

Pattern Trick for Objects #366

floriankramer commented Nov 27, 2020

floriankramer commented Dec 4, 2020 •

edited

hannahbast commented Dec 27, 2020

floriankramer commented Feb 12, 2021

joka921 left a comment

joka921 Mar 23, 2021

joka921 Mar 23, 2021

joka921 Mar 23, 2021

joka921 Mar 23, 2021

joka921 Mar 23, 2021

joka921 Mar 26, 2021

joka921 Mar 26, 2021

joka921 Mar 26, 2021

joka921 Mar 26, 2021

joka921 Mar 26, 2021

Pattern Trick for Objects #366

Are you sure you want to change the base?

Pattern Trick for Objects #366

Conversation

floriankramer commented Nov 27, 2020

floriankramer commented Dec 4, 2020 • edited

hannahbast commented Dec 27, 2020

floriankramer commented Feb 12, 2021

joka921 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

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

floriankramer commented Dec 4, 2020 •

edited