Use in-memory join when one of the tables is small enough

[erizocosmico]

This is just a future idea that I thought of leaving here for the future, as I was researching how to improve perf of the joins.

If we have two sides on a join we could try to use an in-memory cache for the smaller side instead of iterating it over and over. Depending on how expensive the underlying implementation is of iterating all over the rows, this might be a big performance boost.

What we need for this:

• Be able to estimate the size of each side (which will be more accurate the less filters and so on you have) if it's possible (inner join of an inner join might be tricky, for example).
• Optimisation rule that checks the size of each inner join side and if it can, replace it with an inner join that keeps the smaller side in memory instead of iterating it again and again.

Caveats:

• Estimating the size will be real hard and it's not portable, each impl must provide their own.
• Hard to decide a limit set in stone that's sensible for the in-memory join.

Sadly, this does not solve #454, because it can't and shouldn't be applied in every case. I've been digging on how to make a join not iterate one side N times, but it's the only way to do it without having a whole side in memory, which is not viable for large datasets.

[erizocosmico]

This should not be on TODO, it cannot be done without a cost estimation component.

[smola]

Does vitess parser support query hints?
Would it be feasible to implement a query hint for this in a comment?

[ajnavarro]

@smola query hints are comments and we are removing them: https://github.com/src-d/go-mysql-server/blob/master/sql/parse/parse.go#L59 , so they might not be supported by vitess.

The other day I had an idea to avoid cost estimation component.

Right now we are iterating from every row of one side of the join all the rows from the other side.

We can check on the first pass if all the rows of the right will fit in memory (available memory will be defined by configuration) and if true we will put it on memory on the next pass.

The problem with that is that we don't know which part of the join is the smallest one, so we can only apply this logic to one of the join children always.