But based on the code, it is checking if originColIDs is the prefix of the index's KeyColumnIDs. I'm not sure if that's what we want. Consider the following case: a, b might not be a, c, b's prefix, but it's still useful for constraint check that reference column a, b.

Great example. Yes, looks like IsValidOriginIndex will miss some useful indexes. (I suspect it was written back when FK checks were more picky about the indexes they used.)

If originColIDs is not an ordered list but just in the same order that the user specified, this might cause problems mentioned in the screenshot.

Yes, I think it's just the order the user specified.

I'm not exactly sure how IsValidOriginIndex and HasPrefix are being used right now; I took a quick look at it, but I need more time to understand better.

Looks like IsValidOriginIndex is currently only used in one place, this check in DROP INDEX:

cockroach/pkg/sql/drop_index.go

Lines 415 to 429 in 3aea0c4

	// Check for foreign key mutations referencing this index.
	for _, m := range tableDesc.Mutations {
	if c := m.GetConstraint(); c != nil &&
	c.ConstraintType == descpb.ConstraintToUpdate_FOREIGN_KEY &&
	// If the index being deleted could be used as a index for this outbound
	// foreign key mutation, then make sure that we have another index that
	// could be used for this mutation.
	idx.IsValidOriginIndex(c.ForeignKey.OriginColumnIDs) &&
	!indexHasReplacementCandidate(func(idx catalog.Index) bool {
	return idx.IsValidOriginIndex(c.ForeignKey.OriginColumnIDs)
	}) {
	return pgerror.Newf(pgcode.ObjectNotInPrerequisiteState,
	"referencing constraint %q in the middle of being added, try again later", c.ForeignKey.Name)
	}
	}

I'm not sure if this is supposed to happen. When the table gets really large, will it ever favour the the secondary index and perform a look up join?

Sometimes it will. Here's an example: https://gist.github.com/michae2/2bf255b183b529bea28f25aa82b5f561 which results in this for me:

                                                 info
------------------------------------------------------------------------------------------------------
  distribution: local
  vectorized: true

  • root
  │
  ├── • update
  │   │ table: p
  │   │ set: y
  │   │
  │   └── • buffer
  │       │ label: buffer 1
  │       │
  │       └── • render
  │           │
  │           └── • filter
  │               │ estimated row count: 1
  │               │ filter: y = 3
  │               │
  │               └── • scan
  │                     estimated row count: 100 (100% of the table; stats collected 20 minutes ago)
  │                     table: p@p_pkey
  │                     spans: FULL SCAN
  │
  └── • constraint-check
      │
      └── • error if rows
          │
          └── • lookup join (semi)
              │ estimated row count: 1
              │ table: t@t_pkey
              │ equality: (rowid) = (rowid)
              │ equality cols are key
              │ pred: x = a
              │
              └── • lookup join
                  │ estimated row count: 1
                  │ table: t@t_b_idx
                  │ equality: (y) = (b)
                  │
                  └── • except
                      │ estimated row count: 1
                      │
                      ├── • scan buffer
                      │     estimated row count: 1
                      │     label: buffer 1
                      │
                      └── • scan buffer
                            estimated row count: 1
                            label: buffer 1

So I don't think we need KeyColumnIDs to cover originColIDs. An intersection will work, as you've done. Or checking that the prefix of KeyColumnIDs is in originColIDs would also work, as @mgartner pointed out.

Sorry if I am making things really confusing here.

Not confusing at all! This is great! 🙂

That's a good idea. We should also look into where HasPrefix are used. Their use cases have been really similar to the logic in IsValidOriginIndex .

nit: police => enforce

Can we have more specific notices for two cases. For example:

1. "some queries may read from a unique, not visible index to enforce uniqueness of the columns"
2. "some queries may read from a not visible index to enforce foreign key constraints"

Is this supposed to be NOT VISIBLE?

This notice is confusing in this context.

If you use regular EXPLAIN without (OPT) it'll print information about the cascade which would be useful for these tests.

I think this test is supposed to check that the partial NOT VISIBLE index is not used.