Starting 'Select *' implementation #546

joaomarques90 · 2022-01-19T14:56:57Z

No description provided.

reintroducing '_re_string.size() > 0'

Restored code, Implementing 'variant<_selectedVariables,Asterisk>' throughout the files e2e -> accept whitespace in vars-paths TODO: test/SparqlParserTest

updating to the '_varsOrAsterisk' variant type

joka921

Thanks for this implementations,
We have found 2 bugs together and have discussed how the SelectedVarsOrAsterisk should work to make the code more readable.

Please add some unit tests for the SparqlParser and some e2e tests via the scientists.quieries.yaml in the e2e directory.

src/engine/QueryExecutionTree.cpp

src/parser/ParsedQuery.h

src/engine/QueryPlanner.cpp

joka921 · 2022-01-21T14:40:08Z

src/engine/Server.cpp

-        query.hasSelectClause()
-            ? query.selectClause()._selectedVariables
-            : std::vector<std::string>{"?subject", "?predicate", "?object"};
+        query.hasSelectClause() ?


This is wrong,
even with the * you have to put all the variables
in the ["selected"] field, and they have to be in the correct order
(as by the column indices).

joka921 · 2022-01-21T14:42:47Z

src/parser/SparqlParser.cpp

@@ -162,9 +164,12 @@ void SparqlParser::parseSelect(ParsedQuery* query) {
  if (_lexer.accept("reduced")) {
    selectClause._reduced = true;
  }
+  if (_lexer.accept("*")) {
+    selectClause._varsOrAsterisk = '*';


selectClause._varsOrAsterisk.setAsterisk()

joka921 · 2022-01-21T14:45:29Z

test/SparqlParserTest.cpp

-    ASSERT_EQ(1u, selectClause._selectedVariables.size());
-    ASSERT_EQ("?movie", selectClause._selectedVariables[0]);
+    ASSERT_EQ(1u, std::get<ParsedQuery::_selectedVariables>(selectClause._varsOrAsterisk).size());
+    ASSERT_EQ("?movie", std::get<ParsedQuery::_selectedVariables>(selectClause._varsOrAsterisk)[0]);


Also implement some tests for queries with SELECT *.

joaomarques90 · 2022-01-21T15:37:07Z

Branch renamed "select_asterisk"

TODO: Unit tests for SparqlParserTest e2e tests

joka921

Thanks for these improvements. It is already much more readable, and it almost works.

The QleverJson format also needs the variable field to be set to the explicit variables in the correct order and not to "*".
I discussed with @hannahbast that we want the variables in a SELECT * query to be in the order of their first appearance in the query. Since doing this exactly again would need to intrusively change the parsing of the complete query, and since this is not required by the standard but just a convenience feature, you can implement this as follows:

In the SelectedVarsOrAsterisk class, store the complete text of the query.
As soon as you resolve the asterisk to concrete variables (you know all the variables then) you can just search for the first occurence of each variable in the query and sort by this. It is ok, if the order is wrong in the presence of subqueries, e.g.

SELECT * WHERE {
  { SELECT ?a WHERE {
     ?a <pred> ?c
 } }
 ?a <pred> ?b.
?a <pred2> ?c
}

We get the variable order ?a ?c ?b although the first occurence of ?c is in the inner suquery space, and ?a ?b ?c would be expected.

As soon as there's a GROUP BY in the query, SELECT * is illegal. Make sure to implement this case, and also write a test, that checks, that the parser throws a readable error in this case.

joka921 · 2022-01-24T09:18:42Z

src/engine/QueryExecutionTree.cpp

@@ -91,22 +92,29 @@ void QueryExecutionTree::setVariableColumns(
 // _____________________________________________________________________________
 template <QueryExecutionTree::ExportSubFormat format>
 ad_utility::stream_generator::stream_generator
-QueryExecutionTree::generateResults(const vector<string>& selectVars,
+QueryExecutionTree::generateResults(const SelectedVarsOrAsterisk & selectVarsOrAsterisk,


Since the type is now called SelectedVarsOrAsterisk
the corresponding variables should also be called selectedVarsOrAsterisk
(vs. selectVarsOrAsterisk)

joka921 · 2022-01-24T09:24:34Z

src/engine/QueryExecutionTree.cpp

-    if (getVariableColumns().contains(var)) {
-      auto columnIndex = getVariableColumns().at(var);
+  if(selectVarsOrAsterisk.isAsterisk()) {
+    for(const auto& elem: getVariableColumns()) {


As a further improvement:
the type of elem here is a pair of (std::string, Index) (the index is an unsigned integer).
The string is the Variable (the keys of the hash map).

So you can further Improve this to
for (const auto& [variable, columnIndex]) {.... }

here variable is what previously was elem.first and columnIndex is variable.second.

This is a C++17 feature called "structured binding" in case you want to research it.

joka921 · 2022-01-24T09:25:40Z

src/engine/QueryExecutionTree.cpp

-          var, columnIndex, resultTable.getResultType(columnIndex)});
-    } else {
-      exportColumns.emplace_back(std::nullopt);
+          elem.first, elem.second, resultTable.getResultType(elem.second)});


If you sort here by the variable (currently "elem.first", then the output order becomes
deterministic for the asterisk (easiest way for the e2e tests).

Of course it should then be commented, that these deterministic orders are not required by the standard.

joka921 · 2022-01-24T09:31:05Z

src/engine/QueryExecutionTree.cpp

+
+  if(selectVarsOrAsterisk.isAsterisk()) {
+    vector<string> vars_names;
+    for(auto const& varName_index: getVariableColumns()) {


Also consider the structured binding here.

This only works, if getVariableColumns() (a hash map) alsways gives us the results in the same order. This should "typically" work, but in general you should either sort them consistently, or write exactly the variables which you have extracted here to the selectedVarsOrAsterisk

joka921 · 2022-01-24T09:33:44Z

src/engine/QueryPlanner.cpp

      }
-      if (!usePatternTrick) {
-        continue;
+      */


Why is this commented out?
it should work as expected.
You can then immediately assign
the selectedVariables to a variable
const auto& selectedVariables = ....getSelectVariables() and use this below to make the code
much more readable.

joka921 · 2022-01-24T09:35:52Z

src/engine/Server.cpp

+      if(query.selectClause()._varsOrAsterisk.isAsterisk()) {
+        string str;
+        str+=(query.selectClause()._varsOrAsterisk.getAsterisk());
+        j["selected"] = std::vector<std::string>{str};


Here you also need the variable names in the (correct!) order,

and not only the asterisk.

joka921 · 2022-01-24T09:40:08Z

src/parser/ParsedQuery.h

+    [[nodiscard]] SelectVarsOrAsterisk get() const {
+        // return clone();
+        return SelectVarsOrAsterisk{_varsOrAsterisk};
+    }


If you need this functionality,
You should simply use the copy constructor, which
I think in this case even exists implicitly.
(you don't need "clone" or "get" for this)

src/parser/ParsedQuery.h

joka921 · 2022-01-24T09:44:18Z

src/parser/ParsedQuery.h

+    [[nodiscard]] char getAsterisk() const {
+      return std::get<char>(_varsOrAsterisk);;
+    }


I don't think we want this method.
Because "isAsterisk" means "export all Variables"
and we don't really need the * which is an implementation detail.
In the one method were you print it, you can just hardcode the *

joka921 · 2022-01-24T09:45:49Z

src/parser/ParsedQuery.h

  struct SelectClause {
-    vector<string> _selectedVariables;
+    // Aliases will be empty if Selector '*' is set


More explicit comment:

// `_aliases` will be empty if `_varsOrAsterisk.isAsterisk()` is true. This means that there was a // `SELECT *` clause in the query.

TODO: add Unit Tests for SparqlParserTest/e2e

Updated _variablesOrder type from List to Set, Reviewed asString() function in case of Selector asterisk TODO: add Unit Tests for SparqlParserTest/e2e

De-factor from set to list (by input & unique) Result_Head_Vars are now ordered Should the results_bindings be in the same order? TODO: add Unit Tests for SparqlParserTest/e2e

removed backup code as well added comment for 'nlohmann' object for having object keys alphabetically sorted

joka921

It is getting better.
I have formulated some improved comments and names
and a few suggestions for types.

joka921 · 2022-01-27T14:19:18Z

src/engine/QueryExecutionTree.cpp

-      validIndices.emplace_back(pair<size_t, ResultTable::ResultType>(
-          elem.second, resultTable->getResultType(elem.second)));
+  if(selectedVarsOrAsterisk.isAsterisk()) {
+    list<string> orderedVariables = selectedVarsOrAsterisk.retrieveOrder();


call them orderedVariablesFromQuery instead of orderedVariables

joka921 · 2022-01-27T14:20:24Z

src/engine/QueryExecutionTree.cpp

+  if(selectedVarsOrAsterisk.isAsterisk()) {
+    list<string> orderedVariables = selectedVarsOrAsterisk.retrieveOrder();
+    auto allVars = getVariableColumns();
+    for (const auto& var : orderedVariables) {


var -> variableFromQuery

joka921 · 2022-01-27T14:20:43Z

src/engine/QueryExecutionTree.cpp

-          elem.second, resultTable->getResultType(elem.second)));
+  if(selectedVarsOrAsterisk.isAsterisk()) {
+    list<string> orderedVariables = selectedVarsOrAsterisk.retrieveOrder();
+    auto allVars = getVariableColumns();


allVars -> variablesFromExecutionTree

joka921 · 2022-01-27T14:23:07Z

src/engine/QueryExecutionTree.cpp

+      }
+    }
+    for(const auto& var : allVars){
+      LOG(DEBUG) << "Variable " << var.first << " was not parsed!! \n";


LOG(WARN) << "The variable \"" << var.first << "\" was found in the execution tree, but not in the original query. This is likely a bug\n";

joka921 · 2022-01-27T14:24:39Z

src/engine/QueryExecutionTree.cpp

+  if(selectedVarsOrAsterisk.isAsterisk()) {
+    for(auto var: selectedVarsOrAsterisk.retrieveOrder()){
+      if (getVariableColumns().contains(var)) {
+        auto columnIndex = getVariableColumns().at(var);
+        exportColumns.push_back(VariableAndColumnIndex{
+            var, columnIndex, resultTable.getResultType(columnIndex)});
+      } else {
+        exportColumns.emplace_back(std::nullopt);
+      }
    }


Also use your code from above here (including the warning etc.)
We have another PR by someone else upcoming, that will soon remove this duplication.

joka921 · 2022-01-27T14:39:17Z

src/parser/ParsedQuery.h

@@ -357,11 +359,29 @@ class ParsedQuery {
    [[nodiscard]] auto& getSelectVariables()  {
      return std::get<std::vector<string>>(_varsOrAsterisk);
    }
+
+    void pushVariablesOrder(const string& variable) {


Call this function addVariableFromQueryBody and document it.

// Add a variable, that was found in the query body. The added variables will only be used if `isAsterisk` is true.

src/parser/ParsedQuery.h

joka921 · 2022-01-27T14:40:45Z

src/parser/ParsedQuery.h

+    [[nodiscard]] std::list<string>& retrieveOrder() {
+      return _variablesOrder;
+    }


I think you should delete the non-const overload. If someone modifies the variables from outside,
this class is not valid anymore.

joka921 · 2022-01-27T14:43:25Z

src/parser/ParsedQuery.h

+      return _variablesOrder;
+    }
+
+    [[nodiscard]] std::list<string> retrieveOrder() const {


call this orderedVariablesFromQueryBody and comment

// Return the variables that were added by the addVariableFromQueryBody` function. The return value does not contain duplicates.

joka921 · 2022-01-27T14:44:02Z

src/parser/ParsedQuery.h

+    // `_aliases` will be empty if Selector '*' is present.
+    // Essentially, there is a `SELECT *` clause in the query.


// This means, that there is a .......
(instead of the "Essentially")

@joka921

Thank you for your comments and help @joka921 !

joka921

We are almost there.

joka921 · 2022-01-27T15:58:14Z

src/engine/QueryExecutionTree.cpp

        validIndices.emplace_back(pair<size_t, ResultTable::ResultType>(
            it->second, resultTable->getResultType(it->second)));
-        allVars.erase(it);
+        variablesFromExecutionTree.erase(it);
      } else {


This else branch should also warn:
OG(WARN) << "The variable "" << variableFromQuery <<
"" was found in the original, query, but not in the execution tree. "
"This is likely a bug\n";

joka921 · 2022-01-27T16:00:35Z

src/engine/QueryExecutionTree.cpp

        exportColumns.push_back(VariableAndColumnIndex{
-            var, columnIndex, resultTable.getResultType(columnIndex)});
+            variableFromQuery, columnIndex, resultTable.getResultType(columnIndex)});
+        variablesFromExecutionTree.erase(variableFromQuery);
      } else {
        exportColumns.emplace_back(std::nullopt);


Also add the complementary warning here.

joka921 · 2022-01-27T16:01:14Z

src/parser/ParsedQuery.cpp

@@ -41,7 +41,7 @@ string ParsedQuery::asString() const {
    os << "\nSELECT: {\n\t";
    if(usesAsterisk) {
      auto list = selectClause._varsOrAsterisk.retrieveOrder();
-      std::list<string>::iterator it;
+      std::vector<string>::iterator it;


still auto

(I'm sorry, I think one of my comments got lost here).

joka921 · 2022-01-27T16:03:35Z

src/parser/ParsedQuery.h

-    void setAsterisk() {
-      _varsOrAsterisk = '*';
-    }
+    std::vector<string> _variablesOrder;


Call this member _variablesFromQueryBody

joka921 · 2022-01-27T16:06:59Z

src/parser/ParsedQuery.h

-    }
-
-    [[nodiscard]] std::list<string> retrieveOrder() const {
+    [[nodiscard]] auto retrieveOrder() const {


Here one of my comments disappeared:
Call this method orderedVariablesFromQueryBody and comment it:
// get the variables which addVariableFromQueryBody` was previously called. The result contains no duplicates and is ordered by the first appearance in the query body.

joaomarques90 added 4 commits January 19, 2022 15:54

Starting 'Select *' implementation

3ada215

Update SparqlLexer.cpp

fe6577e

reintroducing '_re_string.size() > 0'

redraw implementation (mainly after exec-results)

7b8c3d8

Restored code, Implementing 'variant<_selectedVariables,Asterisk>' throughout the files e2e -> accept whitespace in vars-paths TODO: test/SparqlParserTest

update sparqlParserTest

c45ad7a

updating to the '_varsOrAsterisk' variant type

joka921 reviewed Jan 21, 2022

View reviewed changes

joaomarques90 closed this Jan 21, 2022

joaomarques90 deleted the latest branch January 21, 2022 15:34

joaomarques90 restored the latest branch January 21, 2022 15:47

joaomarques90 reopened this Jan 21, 2022

Sugestions from @joka921 mostly implemented

c176e1f

TODO: Unit tests for SparqlParserTest e2e tests

joka921 reviewed Jan 25, 2022

View reviewed changes

RobinTF mentioned this pull request Jan 26, 2022

Introduce CSV/TSV header row #554

Merged

joaomarques90 added 4 commits January 26, 2022 17:15

Continuing the re-factoring of the code

8cb8570

TODO: add Unit Tests for SparqlParserTest/e2e

Re-factor from list to set

3bb4aaa

Updated _variablesOrder type from List to Set, Reviewed asString() function in case of Selector asterisk TODO: add Unit Tests for SparqlParserTest/e2e

Ordering the variables selected

085f23d

De-factor from set to list (by input & unique) Result_Head_Vars are now ordered Should the results_bindings be in the same order? TODO: add Unit Tests for SparqlParserTest/e2e

Log warning implemented

4054695

removed backup code as well added comment for 'nlohmann' object for having object keys alphabetically sorted

joaomarques90 marked this pull request as ready for review January 27, 2022 13:19

joka921 reviewed Jan 27, 2022

View reviewed changes

Implementing the suggestions made by @joka921

43d7f9c

Thank you for your comments and help @joka921 !

joka921 reviewed Jan 27, 2022

View reviewed changes

joka921 and others added 4 commits January 27, 2022 17:11

Merge branch 'master' into latest

ed8ea69

syncing with the merge & implementing latest suggestions

c331fc4

run clang-format before merging.

afdbb93

Merge branch 'master' into latest

c40cb3f

joka921 merged commit d9d162b into ad-freiburg:master Jan 27, 2022

hannahbast mentioned this pull request Feb 26, 2022

select * #492

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Starting 'Select *' implementation #546

Starting 'Select *' implementation #546

joaomarques90 commented Jan 19, 2022

joka921 left a comment

joka921 Jan 21, 2022

joka921 Jan 21, 2022

joka921 Jan 21, 2022

joaomarques90 commented Jan 21, 2022

joka921 left a comment

joka921 Jan 24, 2022

joka921 Jan 24, 2022

joka921 Jan 24, 2022

joka921 Jan 24, 2022

joka921 Jan 24, 2022

joka921 Jan 24, 2022

joka921 Jan 24, 2022

joka921 Jan 24, 2022

joka921 Jan 24, 2022

joka921 Jan 24, 2022

joka921 left a comment

joka921 Jan 27, 2022

joka921 Jan 27, 2022

joka921 Jan 27, 2022

joka921 Jan 27, 2022

joka921 Jan 27, 2022

joka921 Jan 27, 2022

joka921 Jan 27, 2022

joka921 Jan 27, 2022

joka921 Jan 27, 2022

joka921 left a comment

joka921 Jan 27, 2022

joka921 Jan 27, 2022

joka921 Jan 27, 2022

joka921 Jan 27, 2022

joka921 Jan 27, 2022

joka921 Jan 27, 2022

		// `_aliases` will be empty if Selector '*' is present.
		// Essentially, there is a `SELECT *` clause in the query.

Starting 'Select *' implementation #546

Starting 'Select *' implementation #546

Conversation

joaomarques90 commented Jan 19, 2022

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

joaomarques90 commented Jan 21, 2022

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

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

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