Nice! The main feedback is that we actually want this "hint" to be a requirement. I guess the name "hint" is a bit misleading, but all the other index and join hints we support work this way: If a particular plan is hinted, we must use that plan or return an error if it's not possible.

Note that this is a breaking change, if customer has an index called zigzag ...

One option could be to change the hint to FORCE_ZIGZAG, which seems less likely to be used as a name

Reviewed 7 of 19 files at r1.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @cucaroach and @RaduBerinde)

pkg/sql/opt/xform/coster.go, line 1063 at r1 (raw file):

	cost += filterSetup

	if join.HintProvided {

This is a different kind of hint, and not what we'll want to use here. I think you'll actually want to update this section, to return hugeCost if we plan a scan when a zigzag join was hinted:

Then you'll also want to return hugeCost from computeZigzagJoinCost if the hinted indexes are not used.

You'll probably also need to update the code in execbuilder to return an error if the best plan used a scan when a zigzag join was forced.

Basically, if a user uses the ZIGZAG join flag, we want to force that plan, and return an error if it's not possible to plan the zig zag join.

pkg/sql/sem/tree/select.go, line 291 at r1 (raw file):

	IgnoreUniqueWithoutIndexKeys bool
	// HintZigzag enables costing hints to prefer a zigzag join.
	HintZigzag bool

I think we want this to be ForceZigzag

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @cucaroach and @rytaft)

pkg/sql/opt/memo/expr.go, line 358 at r2 (raw file):

	Direction  tree.Direction

	// index is a uint32 to allow optimal packing of this structure, use Index()

You can consider making flags a pointer in ScanPrivate instead. You can have a singleton instance with zero flags that is used when there are no flags (the common case). The same flags structure can be shared between multiple Scans (eg in

pkg/sql/opt/memo/expr.go, line 370 at r2 (raw file):

	// For cases 2 and 3 if we can't generate a suitable plan an error will
	// result.
	ZigzagIndices *util.FastIntSet

Consider having a ForceZigzag flag here as well instead of the pointer (if it's next to the other bools, it shouldn't increase the struct size).

pkg/sql/sem/tree/select.go, line 293 at r2 (raw file):

	// There are three possibilities:
	// 1) nil means no hint, business as usual
	// 2) empty slice means force a Zigzag join but any index will do

Differentiating between nil and empty slice is pretty error prone. I'd consider adding a ForceZigZag bool flag.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @RaduBerinde and @rytaft)

pkg/sql/opt/memo/expr.go, line 358 at r2 (raw file):

Great idea, that will affect the memo memory usage sizes in a good way no doubt.

pkg/sql/opt/memo/expr.go, line 370 at r2 (raw file):

👍

pkg/sql/opt/xform/coster.go, line 1063 at r1 (raw file):

Done.

pkg/sql/sem/tree/select.go, line 291 at r1 (raw file):

Done.

pkg/sql/sem/tree/select.go, line 293 at r2 (raw file):

👍 It felt dirty

Nice! once you address the feedback from @RaduBerinde

Reviewed 2 of 19 files at r1, 21 of 21 files at r2.
Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @cucaroach and @RaduBerinde)

pkg/sql/opt/xform/select_funcs.go, line 1087 at r2 (raw file):

				indices := util.MakeFastIntSet(leftIndex.Ordinal(), rightIndex.Ordinal())
				forceIndices := scanPrivate.Flags.ZigzagIndices
				if !forceIndices.Intersection(indices).Equals(*forceIndices) {

Isn't this equivalent to if !forceIndices.SubsetOf(indices)?

RFAL, I kiboshed any attempts at memory savings, if we feel strongly about that we can address with a separate PR. I also added some sql parser tests and dealt with inverted zigzag joins.

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @mgartner, @RaduBerinde, and @rytaft)

pkg/sql/opt/xform/testdata/rules/join, line 8643 at r4 (raw file):

Done

Reviewed 28 of 28 files at r5.
Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @cucaroach, @mgartner, @RaduBerinde, and @rytaft)

pkg/sql/logictest/testdata/logic_test/zigzag_join, line 203 at r5 (raw file):

statement error syntax error
SELECT * FROM a@{FORCE_ZIGZAG=foo,bar} WHERE a = 3 AND b = 7;

nit: these syntax tests probably aren't necessary here if you have these cases in pkg/sql/parser/testdata tests.

pkg/sql/logictest/testdata/logic_test/zigzag_join, line 220 at r5 (raw file):

# Basic form w/o indices.
statement ok
SELECT * FROM a@{FORCE_ZIGZAG} WHERE a = 3 AND b = 7;

nit: add a test where a zig zag can't be planned like SELECT * FROM a@{FORCE_ZIGZAG} WHERE a = 3 AND c = 'foo'

pkg/sql/opt/memo/expr_format.go, line 430 at r5 (raw file):

						b.WriteString(string(idx.Name()))
						if _, needComma := s.Next(i + 1); needComma {
							b.WriteByte(',')

nit: rather than looking ahead you could print the comma before the index name for each index except the first.

needComma := false
for ... {
   if needComma {
       b.WriteByte(',')
    }
    b.WriteString(...)
    needComma = true
}

pkg/sql/opt/memo/testdata/format, line 352 at r5 (raw file):

# Verify naked hint.
opt
SELECT * FROM zigzag@{FORCE_ZIGZAG} WHERE a = 3 AND b = 7;

There's no force_zigzag printed because they are only printed for scan expressions. To test your changes in expr_format.go you need scans to show up in the plan. You could either remove the secondary indexes from the zigzag table or use the norm directive instead of the opt directive so that there is no exploration performed (or both!).

pkg/sql/opt/optbuilder/select.go, line 540 at r5 (raw file):

		private.Flags.ForceZigzag = indexFlags.ForceZigzag
		if indexFlags.ZigzagIndices != nil {
			private.Flags.ForceZigzag = true

Would it be simpler if the parser set indexFlags.ForceZigzag to true in the FORCE_ZIGZAG=foo case? Then the fields in these flags map directly to the fields in the AST struct.

pkg/sql/opt/xform/select_funcs.go, line 1093 at r5 (raw file):

				forceIndices := scanPrivate.Flags.ZigzagIndices
				if !forceIndices.SubsetOf(indices) {
					return

Can we move this into 2 checks at the top of the ForEach and ForEachStartingAfter callbacks to avoid unnecessary work?

pkg/sql/opt/xform/select_funcs.go, line 1447 at r5 (raw file):

		if !scanPrivate.Flags.ZigzagIndices.Empty() && !scanPrivate.Flags.ZigzagIndices.Contains(index.Ordinal()) {
			return

Can we put this at the top of this ForEach callback to avoid unnecessary work in this case?

pkg/sql/opt/xform/testdata/coster/join, line 998 at r5 (raw file):

----

# Verify huge cost with bogus hint.

nit: make this a little more clear like: "Verify that a huge cost is added to a scan when there is a zigzag join hint"

pkg/sql/opt/xform/testdata/rules/join, line 8643 at r4 (raw file):

Looks like these tests still need to be moved to pkg/sql/opt/xform/testdata/rules/select. We have zigzag join tests there because the rules for generating zigzag joins operate on Select expressions, not on joins.

pkg/sql/parser/sql.y, line 9577 at r5 (raw file):

  }
|
  FORCE_ZIGZAG '=' index_name

I think we should be consistent with FORCE_INDEX and handle a syntax like FORCE_ZIGZAG '=' '[' iconst64 ']' which allows forcing a specific index by its descriptor ID. There's some parser tests in pkg/sql/parser/testdata/table_by_id which you can add on to.

pkg/sql/parser/testdata/select_clauses, line 424 at r5 (raw file):

at or near "}": syntax error: FORCE_ZIGZAG specified multiple times
DETAIL: source SQL:
SELECT a FROM foo@{FORCE_ZIGZAG,FORCE_ZIGZAG}

What is expected with foo@{FORCE_ZIGZAG,FORCE_ZIGZAG=a}? An error? Can you add a test for that case and maybe foo@{FORCE_ZIGZAG=a,FORCE_ZIGZAG} as well.

pkg/sql/sem/tree/select.go, line 293 at r5 (raw file):

	// index constraints.
	IgnoreUniqueWithoutIndexKeys bool
	ForceZigzag                  bool

nit: Add a comment explaining what this does and how it relates to ZigzagIndices.

pkg/sql/sem/tree/select.go, line 296 at r5 (raw file):

	// ZigzagIndices forces a zigzag plan, with (optionally) particular indices.
	// There are three possibilities:
	// 1) nil means no hint, business as usual

nit: update this comment, a nil and empty slice have the same meaning now, correct?

Reviewed 28 of 28 files at r5.
Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @cucaroach, @mgartner, and @RaduBerinde)

pkg/sql/opt/memo/expr.go, line 354 at r4 (raw file):

Now that I added NoZigzagJoin, you should also add a test to make sure that it's not combined with ForceZigzag. Sorry to give you more work!

pkg/sql/opt/memo/expr_format.go, line 413 at r3 (raw file):

I think it will be printed here in the case where you tried to force a zigzag but it was not successful (looks like you have a test that confirms this).

That's not a bad idea to add the flags to ZigzagJoinPrivate... although if it's only for the purpose of printing this stuff then maybe it's overkill. Up to you...

pkg/sql/opt/xform/testdata/rules/select, line 6387 at r5 (raw file):

           └── j @> '{"a": 1, "b": 2}'

# Generate a zigzag join on with a hint.

nit: on with a hint -> with a hint

pkg/sql/sem/tree/select.go, line 374 at r5 (raw file):

	}
	if ih.ForceZigzag && ih.NoIndexJoin {
		return errors.New("FORCE_ZIGZAG cannot be specified in conjunction with NO_INDEX_JOIN")

also add a similar check for NoZigzagJoin

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @mgartner, @RaduBerinde, and @rytaft)

pkg/sql/logictest/testdata/logic_test/zigzag_join, line 220 at r5 (raw file):

That's a valid query from what I can tell, did you mean if like c didn't have an index?

pkg/sql/opt/memo/expr.go, line 354 at r4 (raw file):

No problem!

pkg/sql/opt/memo/expr_format.go, line 413 at r3 (raw file):

Seems like overkill.

pkg/sql/opt/memo/expr_format.go, line 430 at r5 (raw file):

👍

pkg/sql/opt/memo/testdata/format, line 352 at r5 (raw file):

Ah, was wondering how that code would get triggered. Should I care that the ZigzagJoinExpr doesn't print out anything related to the hint?

pkg/sql/opt/optbuilder/select.go, line 540 at r5 (raw file):

Good thought but doesn't really help. I'm treating FORCE_ZIGZAG,FORCE_ZIGZAG as an error and also setting ForceZigzag to true would complicate that error handling.

pkg/sql/opt/xform/select_funcs.go, line 1093 at r5 (raw file):

👍

pkg/sql/opt/xform/select_funcs.go, line 1447 at r5 (raw file):

👍

pkg/sql/opt/xform/testdata/rules/join, line 8643 at r4 (raw file):

Boo, I moved these but forgot to push, sorry!.

pkg/sql/opt/xform/testdata/rules/select, line 6387 at r5 (raw file):

👍

pkg/sql/parser/sql.y, line 9577 at r5 (raw file):

👍

pkg/sql/parser/testdata/select_clauses, line 424 at r5 (raw file):

Yeah I think it should be a "duplicate hint" kind of error.

pkg/sql/sem/tree/select.go, line 293 at r5 (raw file):

👍

pkg/sql/sem/tree/select.go, line 374 at r5 (raw file):

👍

pkg/sql/opt/xform/testdata/coster/join, line 998 at r5 (raw file):

👍

Reviewed 16 of 25 files at r6, 6 of 6 files at r7.
Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @mgartner, @RaduBerinde, and @rytaft)

Thanks for the reviews! We've decided not to put this in 21.2, I'll merge it in post branch for 22.1 once Marcus is back and can check it out.

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @mgartner, @RaduBerinde, and @rytaft)

Rebased and updated commit message, I think this is ready to go, @mgartner did I address all your concerns?

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @mgartner and @rytaft)

pkg/sql/logictest/testdata/logic_test/zigzag_join, line 220 at r5 (raw file):

Nevermind, I was confused. Done.

Reviewed 16 of 25 files at r6, 6 of 6 files at r7.
Reviewable status: complete! 1 of 0 LGTMs obtained (and 1 stale) (waiting on @cucaroach, @mgartner, and @rytaft)

pkg/sql/opt/memo/testdata/format, line 352 at r5 (raw file):

It might be a bit confusing, but I don't see it as a huge problem. I think its fine to leave as-is for now.

pkg/sql/opt/xform/select_funcs.go, line 1065 at r9 (raw file):

				forceIndexes := scanPrivate.Flags.ZigzagIndexes
				if !forceIndexes.SubsetOf(indexes) {
					return

nit: I think this could still go up higher to avoid unnecessary work, right below:

iter2.ForEachStartingAfter(leftIndex.Ordinal(), func(rightIndex cat.Index, innerFilters memo.FiltersExpr, rightCols opt.ColSet, _ bool, _ memo.ProjectionsExpr) {

pkg/sql/opt/xform/select_funcs.go, line 1369 at r9 (raw file):

		// Check if we have zigzag hints.
		if !scanPrivate.Flags.ZigzagIndexes.Empty() && !scanPrivate.Flags.ZigzagIndexes.Contains(index.Ordinal()) {

nit: I think this could still go up higher to avoid unnecessary work, right below:

iter.ForEach(func(index cat.Index, filters memo.FiltersExpr, indexCols opt.ColSet, _ bool, _ memo.ProjectionsExpr) {

pkg/sql/opt/xform/testdata/rules/select, line 6072 at r9 (raw file):

# Zigzag join hinting tests
exec-ddl
CREATE TABLE zigzag (n INT PRIMARY KEY, a INT, b INT, c STRING, INDEX a_idx(a), INDEX b_idx(b), UNIQUE INDEX c_idx(b,c), INDEX ba_idx(b));

nit: put this on multiple lines

Also, is ba_idx suppose to index (b, a)?

Reviewed 2 of 2 files at r10.
Reviewable status: complete! 0 of 0 LGTMs obtained (and 2 stale) (waiting on @mgartner and @rytaft)

Reviewable status: complete! 0 of 0 LGTMs obtained (and 2 stale) (waiting on @mgartner and @rytaft)

pkg/sql/opt/memo/testdata/format, line 352 at r5 (raw file):

👍

pkg/sql/opt/xform/testdata/rules/select, line 6072 at r9 (raw file):

I think I had it as b,a but then it didn't use zigzag, so I changed it to back to b. But I think relying on duplicate indexes like that isn't good so I made it b,c.