Regarding the first commit. I had to go and look at the source code because obviously EXPLAIN(VERBOSE) also lists a set of columns in the "result" part. There's something strange going on with scanNode, which is that it both has a set of columns in cols/resultColumns and a separate "optimization" by means of valNeededForCol. At first I did not understand why these two things are split; in my opinion if a value is not needed then the corresponding entries should be removed entirely from cols and resultColumns and surely the separate field valNeededForCol would not be needed at all.

Now after reading this code, I seem to understand (please correct me if I'm wrong) that even though we do not return values for the other columns, we need them to be listed by Columns() because they may appear in the ordering information. The key concept here is, I believe, the idea that we can have columns that participate in the ordering but are not returned as values by the node.

If my understanding is correct then:

1. please extend the commit message for this first commit to explain all this (perhaps copy-paste the 2nd paragraph above?)

2. add a comment on the IR RFC PR directed to me with a link to this issue; I think this idea to separate "columns with values" and "ghost columns that may participate in sorting" is not specific to scanNode and should be applied everywhere, and I want to make a note of that with examples in the RFC.

LGTM for the 1st commit if my understanding is correct, otherwise I'd like to see your explanation.

Reviewed 6 of 6 files at r1.
Review status: 6 of 34 files reviewed at latest revision, all discussions resolved, some commit checks failed.

Comments from Reviewable

Regarding the 2nd commit. Please also add a field in ResultColumn to mirror the information provided by setNeededColumn. I think the new filed should be called ValueOmitted.

Reviewed 26 of 26 files at r2.
Review status: 30 of 34 files reviewed at latest revision, all discussions resolved, some commit checks failed.

Comments from Reviewable

Reviewed 1 of 1 files at r3.
Review status: 31 of 34 files reviewed at latest revision, 1 unresolved discussion, some commit checks failed.

pkg/sql/select.go, line 408 at r3 (raw file):

		neededCols[i] = s.ivarHelper.IndexedVarUsed(i)
	}
	s.source.plan.setNeededColumns(neededCols)

Excellent. Truth be told I've been wanting this optimization for ages! 👍

Comments from Reviewable

Excellent initiative. I miss the following two things:

• the default implementation for setNeededColumns should recurse in the sub-node. Right now the code won't do the right thing if you have say select * from (select * from a limit 10) join b
• marking of columns not needed in ResultColumns

Reviewed 3 of 3 files at r4.
Review status: all files reviewed at latest revision, all discussions resolved, some commit checks failed.

Comments from Reviewable

I don't think it was driven by ordering, it was just easier to implement it this way. It is easier if the scanNode columns are always the table columns. It would be a pain if the Columns() changed when you set the needed cols; e.g. all the indexed vars in the expressions will need to be remapped; the ordering info will also need to change, etc. Imagine if we did that for the join node - once we get the "needed" cols, we can no longer prepare rows in the same way, we would always need to go through some kind of map. Perhaps it's possible to make all this easier with some heavy refactoring and do it the other way, I don't know.

I will add the ValueOmitted field, I think that's a good idea, and then this information can just show up as part of the existing column info.

I think the ghost sorting thing is not relevant for the current codebase - any columns we sort on will be marked as "needed" because they are added as renders by the sort node. We may want to do the same in the IR, at least for starters. But yeah it's definitely a thing to keep in mind.

On recursing in the sub-node: the aim of this PR is to improve the common case of table joins; implementation of the new primitive for all nodes can be done later. In particular, it's not so easy to recurse through select nodes - you have to figure out which source columns are needed in whatever subset of renders is needed by the higher node.

Review status: all files reviewed at latest revision, all discussions resolved, some commit checks failed.

Comments from Reviewable

Ok I agree that having the return value of Columns() stable is useful for multiple reasons.
Also I agree that we can improve the new method setNeededColumns for the other nodes in a subsequent PR.
Regarding the implementation of it for selectNode, I foresee that the work needed for #11723 will help here too.

Regarding the sort node the reason why I mentioned that ghost columns are useful is because this is the information that the sort node needs to decide whether to add the additional renders or not. If the data is already sorted on the required column, even if the data for that column is not present, then there is no additional render required. We already have this optimization in place by the way so if you have SELECT v FROM kv ORDER BY k and the ordering info on kv says the data is already ordered by k, the sort node will vanish. However its applicability is limited, due to the lack of proper "ghost column" annotations, for example in this case: SELECT v FROM (SELECT v+1 AS v FROM FROM kv LIMIT 3 UNION SELECT v+2 AS v FROM kv) ORDER BY k. Here, even though the data source is already ordered by k, this information is lost because the column information only reports v, and the optimization above does not apply. It would be nice to indicate the additional sorting columns as ghost columns even when they are not rendered.

Review status: all files reviewed at latest revision, all discussions resolved, some commit checks failed.

Comments from Reviewable

I agree. Maybe what we want is the ordering info to refer to columns not as indices in Columns() but directly (by name?), in a way that is independent of what columns happen to be in Columns().

Anyway, about the case you mentioned, didn't we talk about this yesterday and concluded that we do add the k render and the sort node doesn't vanish? I agree it could be optimized as you say but currently it isn't (and we're kind of relying on the render being there for distsql planning, unfortunately).

root@:26257> EXPLAIN (VERBOSE) SELECT v FROM kv ORDER BY k;
+-------+---------------+-----------------------------+---------+-----------+
| Level |     Type      |         Description         | Columns | Ordering  |
+-------+---------------+-----------------------------+---------+-----------+
|     0 | select        |                             | (v)     | +@2       |
|     1 | nosort        | +k                          | (v)     | +@2       |
|     2 | render/filter | from (test.kv.k, test.kv.v) | (v, k)  | +k,unique |
|     3 | scan          | kv@primary -                | (k, v)  | +k,unique |
+-------+---------------+-----------------------------+---------+-----------+

Review status: all files reviewed at latest revision, all discussions resolved, some commit checks failed.

Comments from Reviewable

Yes currently it isn't but I wanted to share the thought anyway :)

Looking forward to your extended commit message, the rest LGTM.

Haha, it looks like the EXPLAIN (VERBOSE) output is non-deterministic

EXPLAIN (VERBOSE) SELECT b.y FROM (twocolumn AS a JOIN twocolumn AS b USING(x))
Sometimes:
1  render/filter  from ("".a.x, "".a.y, *"".a.rowid, "".b.y, *"".b.rowid)  (y)
Other times:
1  render/filter  from ("".b.x, "".a.y, *"".a.rowid, "".b.y, *"".b.rowid)  (y)                                        

Any ideas? How are we deciding which column shows up for the "equals", is there a map somewhere perhaps?

Yes there is a map. It's the tableAlias map in the dataSourceInfo. If you can pinpoint where the problem is occurring I can perhaps suggest a better approach.

Ah. I think it's findTableAlias. It says it returns the "first table alias" but the information of which was first is lost. I can't think of what to do other than maybe choosing by table name.. Do you see any problem with changing sourceAliases to a simple slice?

No problem! (as long as the lookups still work fine...)

Updated - added omitted field (first commit), and added a commit that changes the map for a slice.

@knz - let me know if the last commit and the new version of the first commit look ok.

Reviewed 8 of 37 files at r5, 1 of 1 files at r6, 23 of 26 files at r7, 1 of 1 files at r8, 1 of 3 files at r9, 4 of 4 files at r10.
Review status: all files reviewed at latest revision, all discussions resolved, all commit checks successful.

Comments from Reviewable

TFTR!

Comments from Reviewable