Better result tables #193

floriankramer · 2019-02-25T13:33:34Z

This pr replaces std::vector<std::array> and std::vector<std::vector> as the data type used by result tables to a new IdTable type. This ensures that the result data is always stored dense and makes the templating of operations easier.

niklas88

Wow, that's what I call a giant Pull Request. Reviewing and testing this will take some time but here is what I noticed on a quick first pass. Overall this already looks very nice

src/engine/CallFixedSize.h

src/engine/ResultTable.h

niklas88 · 2019-02-25T15:42:10Z

src/engine/Comparators.h

 class OBComp {
 public:
  OBComp(const vector<pair<size_t, bool>>& sortIndices)
      : _sortIndices(sortIndices) {}

-  bool operator()(const E& a, const E& b) const {
+  template <int I>
+  bool operator()(const typename IdTableImpl<I>::Row& a,


I think this should take the Row type from IdTableStatic instead of from the …Impl

That's what I tried out initially, but because the Row type in IdTableStatic is declared using a using statement the compiler had trouble inferring the value of I (which must be found using template argument deduction). Templating the entire comparator on the other hand leads to the problem, that the I needs to be determined within the OrderBy operation, which would require a set of 5 if clauses to determine the value of I for the comparator (as the CALL_WITH_FIXED... macros don't support this case).

Interesting that using changes the behavior like that, do you think that is intended/correct or rather a compiler problem?

I actually am not certain if this should work or not, but I think it might fall into the 'Aliases are never deduced' rule (cppreference).

src/engine/IdTable.h

src/engine/MultiColumnJoin.cpp

src/engine/OptionalJoin.cpp

src/engine/ResultTable.h

src/engine/Sort.cpp

src/engine/IdTable.h

niklas88 · 2019-03-01T11:25:36Z

src/engine/IdTable.h

+    if (IdTableImpl<COLS>::_size + 1 >= IdTableImpl<COLS>::_capacity) {
+      grow();
+    }
+    std::memcpy(IdTableImpl<COLS>::_data +


I think a normal assignment might be preferable to forcing a memcpy here?

Using memcpy avoids the less efficient row based access here (which would construct and object). As this is part of the internals of the IdTable I went for efficiency over simplicity here.

src/engine/IdTable.h

…plate args.

ghost · 2019-03-01T13:11:29Z

DeepCode encountered a problem when analyzing this pull request. If you want to retry, create a comment: "Retry Deepcode".

niklas88 · 2019-03-01T14:16:19Z

src/engine/IdTable.h

+  /**
+   * This is simply an Id* which has some additional methods.
+   **/
+  class ConstRow {


Shouldn't this have a Id* field so that as a struct it does indeed have the same size as an Id*? Also I think it should be specified final then we can also drop the virtual destructor

I thought about this and then realized that the custom Row type for tables with a fixed with doesn't make any sense. The latest commit changes it to std::array<Id, COLS>, which should make the operator[] perform significantly more standard conform for IdTableStatic with fixed width.

niklas88 · 2019-03-01T14:27:38Z

@floriankramer somehow your commits look like GitHub sees two identies for you. You might want to check if you have all your mail addresses in your GitHub profile

niklas88

A few nitpicks/questions other than that I think this is almost ready to merge. Great work!

niklas88 · 2019-03-08T10:38:20Z

src/engine/IdTable.h

-    iterator(Id* data, size_t row, size_t cols)
-        : _data(data), _row(row), _rowView(data + (cols * row), cols) {}
+    iterator() : _data(nullptr), _row(0) {}
+    iterator(Id* data, size_t row, size_t) : _data(data), _row(row) {}


What's with the last unnamed parameter here?

The iterator has to take the number of columns as a parameter to allow for compatibility between the fixed width and variable with IdTable. To prevent the compiler from complaining about an unused parameter we can either not give the parameter a name, or cast it to void in the constructors body (e.g. (void)cols;).
I've added a comment explaining the unnamed parameter.

you could also use

iterator(Id* data, size_t row, size_t /* cols */) : _data(data), _row(row) {}

niklas88 · 2019-03-08T10:59:08Z

src/engine/IdTable.h

+      }
+    }
+
+    Row& operator=(const Row& other) {


Do we need a check for self assignment here?

I added the check

niklas88 · 2019-03-08T10:59:24Z

src/engine/IdTable.h

+      return *this;
+    }
+
+    Row& operator=(Row&& other) {


Self assignment?

I added the check

niklas88 · 2019-03-08T11:04:53Z

src/engine/IdTable.h

+    IdTableImpl<COLS>::setCols(cols);
+  }
+
+  void emplace_back() { push_back(); }


Do we need the no param emplace_back() if we don't have one with params?

I've added the no params version for convenience (and because it was used in several places in the code and made porting that to IdTables easier). I haven't yet found a nice way of implementing an emplace with arguments that doesn't rely on c style va_args.

niklas88 · 2019-03-08T11:18:01Z

src/engine/IndexScan.cpp

 }

 // _____________________________________________________________________________
 void IndexScan::computeSOPfreeO(ResultTable* result) const {
  result->_nofColumns = 2;
+  result->_data.setCols(result->_nofColumns);


I think we could remove the _nofColumns member from ResultTable that would only save 8 bytes but also remove the line above this line

src/engine/OrderBy.cpp

niklas88 · 2019-03-08T15:33:56Z

@floriankramer any idea what killed the QLever instance during the end-to-end tests with the latest changes?

Locally it seems to hang at

Sort result computation...

of the first query

niklas88 · 2019-03-08T16:20:04Z

@floriankramer I was able to reproduce this running under gdb

Fri Mar  8 17:14:42.340 - INFO:  ---------- WAITING FOR QUERY AT PORT "7,001" ...
Fri Mar  8 17:14:45.820 - INFO:  Incoming connection, processing...
Fri Mar  8 17:14:45.822 - INFO:  Query:
SELECT ?x SCORE(?t) TEXT(?t) WHERE {
          ?x <is-a> <Scientist> .
          ?t ql:contains-entity ?x .
          ?t ql:contains-word "relati*"
      }
      ORDER BY DESC(SCORE(?t))
ServerMain: /home/schnelle/projects/QLever/src/engine/../index/../engine/IdTable.h:643: void IdTableStatic<COLS>::insert(const iterator&, const iterator&, const iterator&) [with int COLS = 0; IdTableStatic<COLS>::iterator = IdTableImpl<0>::iterator]: Assertion `begin.cols() == cols()' failed.

Thread 2 "ServerMain" received signal SIGABRT, Aborted.
[Switching to Thread 0x7ffff6395700 (LWP 26864)]
0x00007ffff7a91d7f in raise () from /usr/lib/libc.so.6
(gdb) bt
#0  0x00007ffff7a91d7f in raise () from /usr/lib/libc.so.6
#1  0x00007ffff7a7c672 in abort () from /usr/lib/libc.so.6
#2  0x00007ffff7a7c548 in __assert_fail_base.cold.0 () from /usr/lib/libc.so.6
#3  0x00007ffff7a8a396 in __assert_fail () from /usr/lib/libc.so.6
#4  0x0000555555dd73fa in IdTableStatic<0>::insert (this=0x7ffff0007b60, pos=..., begin=..., end=...)
    at /home/schnelle/projects/QLever/src/engine/../index/../engine/IdTable.h:643
#5  0x0000555556044245 in Sort::computeResult (this=0x7ffff000bdd0, result=0x7ffff0007b40)
    at /home/schnelle/projects/QLever/src/engine/Sort.cpp:52
#6  0x0000555555ae81b9 in Operation::getResult (this=0x7ffff000bdd0)
    at /home/schnelle/projects/QLever/src/engine/./././Operation.h:52
#7  0x0000555555ae8b81 in QueryExecutionTree::getResult (this=0x7ffff000d560)
    at /home/schnelle/projects/QLever/src/engine/././QueryExecutionTree.h:81
#8  0x0000555555e80c84 in Join::computeResult (this=0x7ffff000b9c0, result=0x7ffff00067a0)
    at /home/schnelle/projects/QLever/src/engine/Join.cpp:103
#9  0x0000555555ae81b9 in Operation::getResult (this=0x7ffff000b9c0)
    at /home/schnelle/projects/QLever/src/engine/./././Operation.h:52
#10 0x0000555555ae8b81 in QueryExecutionTree::getResult (this=0x7ffff000cf20)
    at /home/schnelle/projects/QLever/src/engine/././QueryExecutionTree.h:81
#11 0x0000555556062fca in OrderBy::computeResult (this=0x7ffff00096a0, result=0x7ffff0006590)
    at /home/schnelle/projects/QLever/src/engine/OrderBy.cpp:54
#12 0x0000555555ae81b9 in Operation::getResult (this=0x7ffff00096a0)
    at /home/schnelle/projects/QLever/src/engine/./././Operation.h:52
#13 0x0000555555ae8b81 in QueryExecutionTree::getResult (this=0x7ffff6394ac0)
    at /home/schnelle/projects/QLever/src/engine/././QueryExecutionTree.h:81
#14 0x0000555555adf919 in Server::composeResponseJson[abi:cxx11](ParsedQuery const&, QueryExecutionTree const&, unsigned long) const (this=0x7fffffffaff0, query=..., qet=..., maxSend=100) at /home/schnelle/projects/QLever/src/engine/Server.cpp:324
#15 0x0000555555adda1e in Server::process (this=0x7fffffffaff0, client=0x7ffff6394db0, qec=0x7fffffffadd0)
    at /home/schnelle/projects/QLever/src/engine/Server.cpp:183
#16 0x0000555555add068 in Server::runAcceptLoop (this=0x7fffffffaff0, qec=0x7fffffffadd0)
    at /home/schnelle/projects/QLever/src/engine/Server.cpp:80
#17 0x0000555555b00762 in std::__invoke_impl<void, void (Server::*)(QueryExecutionContext*), Server*, QueryExecutionContext*> (__f=
    @0x5555569fa4d8: (void (Server::*)(Server * const, QueryExecutionContext *)) 0x555555adcf2e <Server::runAcceptLoop(QueryExecutionContext*)>, __t=@0x5555569fa4d0: 0x7fffffffaff0, __args#0=@0x5555569fa4c8: 0x7fffffffadd0)
    at /usr/include/c++/8.2.1/bits/invoke.h:73
#18 0x0000555555afc732 in std::__invoke<void (Server::*)(QueryExecutionContext*), Server*, QueryExecutionContext*> (__fn=
    @0x5555569fa4d8: (void (Server::*)(Server * const, QueryExecutionContext *)) 0x555555adcf2e <Server::runAcceptLoop(QueryExecutionContext*)>, __args#0=@0x5555569fa4d0: 0x7fffffffaff0, __args#1=@0x5555569fa4c8: 0x7fffffffadd0)
    at /usr/include/c++/8.2.1/bits/invoke.h:95
#19 0x0000555555b09865 in std::thread::_Invoker<std::tuple<void (Server::*)(QueryExecutionContext*), Server*, QueryExecutionContext*> >::_M_invoke<0ul, 1ul, 2ul> (this=0x5555569fa4c8) at /usr/include/c++/8.2.1/thread:244
#20 0x0000555555b09732 in std::thread::_Invoker<std::tuple<void (Server::*)(QueryExecutionContext*), Server*, QueryExecutionContext*> >::operator() (this=0x5555569fa4c8) at /usr/include/c++/8.2.1/thread:253
#21 0x0000555555b094aa in std::thread::_State_impl<std::thread::_Invoker<std::tuple<void (Server::*)(QueryExecutionContext*), Server*, QueryExecutionContext*> > >::_M_run (this=0x5555569fa4c0) at /usr/include/c++/8.2.1/thread:196
#22 0x00007ffff7e79063 in std::execute_native_thread_routine (__p=0x5555569fa4c0)
    at /build/gcc/src/gcc/libstdc++-v3/src/c++11/thread.cc:80
#23 0x00007ffff7f66a9d in start_thread () from /usr/lib/libpthread.so.0
#24 0x00007ffff7b55b23 in clone () from /usr/lib/libc.so.6

This seems to indicate that somewhere the columns did indeed get mixed up

../engine/IdTable.h:643: 
void IdTableStatic<COLS>::insert(const iterator&, const iterator&, const iterator&) 
[with int COLS = 0; IdTableStatic<COLS>::iterator = IdTableImpl<0>::iterator]: 
Assertion `begin.cols() == cols()' failed

floriankramer requested a review from niklas88 February 25, 2019 13:33

niklas88 reviewed Feb 25, 2019

View reviewed changes

niklas88 reviewed Mar 1, 2019

View reviewed changes

src/engine/IdTable.h Outdated Show resolved Hide resolved

niklas88 reviewed Mar 1, 2019

View reviewed changes

src/engine/IdTable.h Show resolved Hide resolved

niklas88 reviewed Mar 1, 2019

View reviewed changes

src/engine/IdTable.h Outdated Show resolved Hide resolved

niklas88 reviewed Mar 1, 2019

View reviewed changes

src/engine/IdTable.h Outdated Show resolved Hide resolved

floriankramer and others added 6 commits March 1, 2019 13:56

Implemented a first version of an IdTable

9c09f8a

Added tests for the IdTable

b6c398e

Replaced the old ResultTable data structures with IdTable

69b99f1

Cleaned up the static and dynamic versions of the IdTable.

4159cca

Added a macro that allows for easily converting IdTable widths to tem…

dfea799

…plate args.

Changed all operations to using the new macro

1f65a85

floriankramer force-pushed the better_result_tables branch from 341aca9 to 1f65a85 Compare March 1, 2019 13:11

niklas88 reviewed Mar 1, 2019

View reviewed changes

floriankramer force-pushed the better_result_tables branch from ec729e8 to 1b202ce Compare March 1, 2019 14:32

Several bug and typo fixes.

effdcc7

floriankramer force-pushed the better_result_tables branch from 1b202ce to effdcc7 Compare March 1, 2019 15:32

floriankramer added 4 commits March 4, 2019 16:01

Minor code cleanups.

93e34bd

Changed the type of rows of IdTableStatic to std::array

94e581d

Removed commented code

bd6077b

Removed uneccessary templating for some FTSAlgorithms.

8b8bec9

niklas88 reviewed Mar 8, 2019

View reviewed changes

Removed _nofColumns. Some code cleanup.

2e1ac17

floriankramer force-pushed the better_result_tables branch from 92eebe4 to 2e1ac17 Compare March 9, 2019 09:48

niklas88 merged commit 6b71b66 into ad-freiburg:master Mar 9, 2019

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Better result tables #193

Better result tables #193

floriankramer commented Feb 25, 2019

niklas88 left a comment

niklas88 Feb 25, 2019

floriankramer Feb 27, 2019

niklas88 Feb 28, 2019

floriankramer Mar 4, 2019

niklas88 Mar 1, 2019

floriankramer Mar 1, 2019

ghost commented Mar 1, 2019

niklas88 Mar 1, 2019

floriankramer Mar 4, 2019

niklas88 commented Mar 1, 2019

niklas88 left a comment

niklas88 Mar 8, 2019

floriankramer Mar 8, 2019

niklas88 Mar 8, 2019

niklas88 Mar 8, 2019

floriankramer Mar 8, 2019

niklas88 Mar 8, 2019

floriankramer Mar 8, 2019

niklas88 Mar 8, 2019

floriankramer Mar 8, 2019

niklas88 Mar 8, 2019

floriankramer Mar 8, 2019

niklas88 commented Mar 8, 2019 •

edited

niklas88 commented Mar 8, 2019 •

edited

Better result tables #193

Better result tables #193

Conversation

floriankramer commented Feb 25, 2019

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

ghost commented Mar 1, 2019

Choose a reason for hiding this comment

Choose a reason for hiding this comment

niklas88 commented Mar 1, 2019

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

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

niklas88 commented Mar 8, 2019 • edited

niklas88 commented Mar 8, 2019 • edited

niklas88 commented Mar 8, 2019 •

edited

niklas88 commented Mar 8, 2019 •

edited