For virtual tables it would make sense to not distinguish costs between "random" access and sequential access. But I'd rather not complicate things too much. With no stats, we pretend they have 1000 rows, which should be plenty to prefer lookup joins in most cases (and we can increase it for vtables if need be). The query you pasted above looks like this with your change:

  sort
   └── project
        ├── inner-join (hash)
        │    ├── select
        │    │    ├── scan t3
        │    │    └── filters
        │    │         └── nspname = ANY current_schemas(false)
        │    ├── inner-join (lookup pg_attribute@pg_attribute_attrelid_idx)
        │    │    ├── lookup columns are key
        │    │    ├── project
        │    │    │    ├── inner-join (lookup pg_attribute@pg_attribute_attrelid_idx)
        │    │    │    │    ├── lookup columns are key
        │    │    │    │    ├── project
        │    │    │    │    │    ├── inner-join (lookup pg_class@pg_class_oid_idx)
        │    │    │    │    │    │    ├── lookup columns are key
        │    │    │    │    │    │    ├── inner-join (lookup pg_class@pg_class_oid_idx)
        │    │    │    │    │    │    │    ├── lookup columns are key
        │    │    │    │    │    │    │    ├── select
        │    │    │    │    │    │    │    │    ├── scan c
        │    │    │    │    │    │    │    │    └── filters
        │    │    │    │    │    │    │    │         ├── conrelid = 'b'::REGCLASS
        │    │    │    │    │    │    │    │         └── contype = 'f'
        │    │    │    │    │    │    │    └── filters (true)
        │    │    │    │    │    │    └── filters
        │    │    │    │    │    │         └── t1.oid = 'b'::REGCLASS
        │    │    │    │    │    └── projections
        │    │    │    │    │         └── conkey[1]
        │    │    │    │    └── filters
        │    │    │    │         ├── column108 = a1.attnum
        │    │    │    │         └── a1.attrelid = 'b'::REGCLASS
        │    │    │    └── projections
        │    │    │         └── confkey[1]
        │    │    └── filters
        │    │         └── column131 = a2.attnum
        │    └── filters
        │         └── connamespace = t3.oid
        └── projections

It's all lookup joins except one at the top (pg_namespace has no index).

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

No real comments on the SQL exec portion -- this is super slick!

Sorry for the delay, I've been pretty swamped. This looks great, nice work!

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

pkg/sql/opt_exec_factory.go, line 718 at r1 (raw file):

		onCond = nil
	}
	var n exec.Node

[nit] can just do n := below

pkg/sql/opt_exec_factory.go, line 692 at r3 (raw file):

}

func (ef *execFactory) constructVirtualLookupJoin(

[nit] add a short comment or improve the naming to constructVirtualTableLookupJoin

pkg/sql/opt_exec_factory.go, line 707 at r3 (raw file):

	}
	if len(eqCols) > 1 {
		panic("vtable indexes with more than one column aren't supported yet")

why not just return an AssertionFailedf error

pkg/sql/virtual_schema.go, line 307 at r3 (raw file):

		return errors.AssertionFailedf("datum row count and column count differ: %d vs %d", r, c)
	}
	for i, col := range columns {

[nit] since this gets evaluated per row, maybe avoid the ResultColumn copy into col

pkg/sql/virtual_schema.go, line 320 at r3 (raw file):

	}
	return nil

[nit] extra line

pkg/sql/virtual_table.go, line 216 at r3 (raw file):

	// lookupCols is the projection on vtableCols to apply.
	lookupCols exec.TableColumnOrdinalSet

[nit] In other nodes, we separated the "runtime" state into another struct (which can be embedded). I think it has been helpful especially when just looking at planning/opt-factory side code.

pkg/sql/walk.go, line 945 at r3 (raw file):

	reflect.TypeOf(&valuesNode{}):            "values",
	reflect.TypeOf(&virtualTableNode{}):      "virtual table values",
	reflect.TypeOf(&vTableLookupJoinNode{}):  "virtual table lookup",

[nit] virtual table lookup join or virtual-table-lookup-join (for consistency with lookup-join)

pkg/sql/logictest/testdata/logic_test/orms, line 75 at r3 (raw file):

----
name              primary  unique  indkey  column_indexes  column_names  definition
customers_id_idx  false    false   2       {1,2}           {name,id}     CREATE INDEX customers_id_idx ON test.public.customers USING btree (id ASC)

Isn't this flaky, at least in principle? May want to add ORDER BY to the array_aggs

pkg/sql/opt/xform/custom_funcs.go, line 1323 at r3 (raw file):

	if md.Table(scanPrivate.Table).IsVirtualTable() {
		if joinType != opt.InnerJoinOp {
			return

It wouldn't be hard to support LeftJoin no? Not sure how useful though

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

pkg/sql/opt_exec_factory.go, line 707 at r3 (raw file):

If this error fires it means the binary is basically corrupted, haha - if someone defines a vtable w/ composite index it should really blow up badly in tests rather than make a usable binary. I made this an assertion error though, i think we will fail with this same problem elsewhere loudly.

pkg/sql/virtual_table.go, line 274 at r2 (raw file):

Done.

pkg/sql/virtual_table.go, line 216 at r3 (raw file):

Good point, thanks. Done.

pkg/sql/logictest/testdata/logic_test/orms, line 75 at r3 (raw file):

I want to keep this query as-is, it's a copy of a real world orm query. The fact that this changed is a little sad but I think ok.

pkg/sql/opt/xform/custom_funcs.go, line 1323 at r3 (raw file):

Fair, was just being lazy. Done, and added some tests (and a giant ORM query that uses outer lookup join, yay)

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

pkg/sql/opt_exec_factory.go, line 707 at r3 (raw file):

Thanks! There could in principle be bugs anywhere along the way (in the catalog, in the optimizer, in the exec builder, in the exec factory). An assertion error should be no less visible than a panic, especially in tests.

pkg/sql/logictest/testdata/logic_test/orms, line 75 at r3 (raw file):

Fine with me, if you think the output is deterministic (I don't see why not since it's all executed on a single node).

pkg/sql/opt/xform/custom_funcs.go, line 1323 at r3 (raw file):

Awesome!!j