Great work so far! Really excited about the PR.

My main comment is that this needs way more tests. Encoding is very subtle (as I'm sure you have found out already :). The only way to make sure that we've gotten it correct is to write tests.

Does @mjibson's column family randomizer tool help here? Or maybe it's already doing its magic?

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @danhhz, @jordanlewis, @RaduBerinde, @rohany, and @solongordon)

docs/tech-notes/encoding.md, line 286 at r1 (raw file):

for each indexed column, the data therein are non-null and equal.

Secondary indexes have been extended to include support for column families.

Be more clear about when this change is happening. Imagine someone reading this doc in its entirety without knowledge of this migration.

docs/tech-notes/encoding.md, line 321 at r1 (raw file):

### Value encoding

If the value corresponds to column family 0:

This is still for secondary indexes right? Leave that in.

docs/tech-notes/encoding.md, line 323 at r1 (raw file):

If the value corresponds to column family 0:

The KV value will have value type bytes, and consists of

nit: grammar - tense doesn't agree (will have vs consists of)

docs/tech-notes/encoding.md, line 339 at r1 (raw file):

KV key and the KV value. (Ditto for stored column data in the old format.)

Else the KV Value will have value type `TUPLE` and consists of all stored

Be more explicit about this else - this is a text document not a program. Say "For indexes with more than 1 column family, the non-0th column families KV values will..."

docs/tech-notes/encoding.md, line 342 at r1 (raw file):

columns in that family in the `TUPLE` encoded format.

### Backwards Compatibility

For what? Be more explicit here so it's clear to future readers.

pkg/sql/colencoding/key_encoding.go, line 238 at r1 (raw file):

// TODO(jordan): each type could be optimized here.
// TODO(jordan): should use this approach in the normal row fetcher.
// TODO(rohany): what is the approach in the normal row fetcher?

I think the normal row fetcher doesn't try to skip table key values at all if they're not necessary. It just decodes everything. Look at DecodeKeyVals.

pkg/sql/colexec/cfetcher.go, line 374 at r1 (raw file):

			// Primary indexes only contain ascendingly-encoded
			// values. If this ever changes, we'll probably have to
			// figure out the directions here too.

Hmm... do we have to worry about this? Can you test your new code with descending index columns too? Same comment for fetcher.go.

pkg/sql/colexec/cfetcher.go, line 661 at r1 (raw file):

			// is that the extra columns are not always there, and are used to unique-ify
			// the index key, rather than provide the primary key column values.
			if rf.table.isSecondaryIndex && rf.table.index.Unique && len(rf.table.desc.Families) != 1 {

We should only do this logic if the secondary index has nullable columns. Also, if this condition gets much more complex, you shouldn't recheck it for every single key. It's statically known, so you can figure it out at the start of the run of the fetcher and cache it as a single boolean.

pkg/sql/colexec/cfetcher.go, line 664 at r1 (raw file):

				// TODO (rohany): we don't want to have to look at each indexed value twice (once
				//  while decoding and once here). A possible optimization is to pass whether a
				//  null was encountered while decoding and use that information here instead.

Yeah, this is going to make scans signinficantly slower I'm pretty sure. I think this optimization is very worthwhile. The fetchers are very performance sensitive and it's worth checking the impact here.

pkg/sql/sqlbase/index_encoding.go, line 813 at r1 (raw file):

		}

		// TODO (rohany): do I need to skip this logic for an inverted index?

Good question... do you? Inverted indexes I don't think should have column families at all. And you definitely won't be able to make them primary later - they're fundamentally different beasts (a single database row can have more than one corresponding entries in a single inverted index).

pkg/sql/sqlbase/index_encoding.go, line 820 at r1 (raw file):

			// Copy the key, as we will modify it and move it into the resulting IndexEntry.
			entryKey := make([]byte, len(key))
			copy(entryKey, key)

This isn't necessary on the first iteration (which is the most common case). Can we avoid?

pkg/sql/sqlbase/index_encoding.go, line 825 at r1 (raw file):

			// TODO (rohany): make this faster by computing this up front with
			//  fastIntSets? I wonder if there was a way to reuse this computed
			//  information across calls to EncodeSecondaryIndex.

You should definitely precompute this. Otherwise it's like a duplicate N^2 loop on every key we're encoding. Also, it's pointless in the common case of 1 column family. Should we just have a special case for that vs more than 1?

Yeah, matts column family randomizer is running already -- it caught a bunch of bugs already!

I updated the PR with alot of the TODO optimizations implemented, and added a bunch of more detailed k/v trace tests that helped find some more bugs.

Working on this more opened some more TODO's, so PTAL!

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @danhhz, @jordanlewis, @RaduBerinde, and @solongordon)

docs/tech-notes/encoding.md, line 286 at r1 (raw file):

Done.

docs/tech-notes/encoding.md, line 321 at r1 (raw file):

Done.

docs/tech-notes/encoding.md, line 339 at r1 (raw file):

Done.

docs/tech-notes/encoding.md, line 342 at r1 (raw file):

Done.

pkg/sql/colencoding/key_encoding.go, line 238 at r1 (raw file):

oh ok -- i think i read this originally as "should use the approach in the normal row fetcher" and was confused why we didn't want to skip columns

pkg/sql/colexec/cfetcher.go, line 374 at r1 (raw file):

I don't think we have to worry about this for this PR -- will have to double check this once the primary key compatibility changes in the fetcher go through. Either way, we can ensure that the new candidate primary key has ascending columns as well (as a first step).

pkg/sql/colexec/cfetcher.go, line 661 at r1 (raw file):

I added the optimization below, so the check here can remain simple -- these current booleans and whether or not a null was actually decoded.

pkg/sql/colexec/cfetcher.go, line 664 at r1 (raw file):

Done.

pkg/sql/sqlbase/index_encoding.go, line 813 at r1 (raw file):

Makes sense -- i'll move back to the existing logic for the inverted indexes just to be safe.

pkg/sql/sqlbase/index_encoding.go, line 820 at r1 (raw file):

Done.

pkg/sql/sqlbase/index_encoding.go, line 825 at r1 (raw file):

Done -- I have to look into how to precompute this information across calls to EncodeSecondaryIndex. That might have to be the work of a future PR.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @jordanlewis, @RaduBerinde, @rohany, and @solongordon)

docs/tech-notes/encoding.md, line 347 at r2 (raw file):

Because the key and value encodings for column family 0 have not changed,
we can read indexes encoded without column family support without any changes.

How does this work exactly? If I have an index that has the old encoding on-disk and I want to read a specific family (being able to do that is kind of the point of families), I won't scan family 0. I would need to know that I can't scan specific families with this index.

besides the unknown about the thing @dt is tagged on.

Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @dt, @jordanlewis, and @solongordon)

pkg/sql/sqlbase/system.go, line 324 at r4 (raw file):

Ping @dt

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @jordanlewis, @rohany, and @solongordon)

pkg/sql/sqlbase/system.go, line 324 at r4 (raw file):

Uhh. I'm pretty out of the loop on descriptors and bootstrapping but I'm pretty sure this will only affect what is written on initial cluster creation and then what is used in a handful of unit tests. I don't know if you need to change this since you need a migration for existing descriptors anyway but I don't think it hurts anything either.

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @jordanlewis, @rohany, and @solongordon)

pkg/sql/sqlbase/system.go, line 324 at r4 (raw file):

to clarify, changing this would be expected to make the unit test that the descriptor matches the result of CREATE TABLE pass, but my point above was that this only affects new clusters -- on existing clusters, these tables already exist, so depending on what tests are failing, that could be an indication that it is actually important that existing descriptors get migrated too?