FR: Use composite indexes in the query planner

[twitchyliquid64]

./ql 'create table t(thing int, t time);'
./ql 'create index x on t(thing,t);'
./ql 'explain SELECT * FROM t WHERE thing = 3 AND t = now();'

┌Iterate all rows of table "t"
└Output field names ["thing" "t"]
┌Filter on thing == 3 && t == now()
│Possibly useful indices
│CREATE INDEX xt_thing ON t(thing);
└Output field names ["thing" "t"]

The idea behaviour would be for x to be a composite index, and for it to be used for all queries which have comparisons to thing and t.

This is a very common pattern for most customer-facing databases, where you need to filter on (at minimum) a user identifier and a timestamp, which should ideally have O(log n) performance (a customer with 1mil records should minimially impact the performance of another customer with only a few hundred records).

Based on my reading of ql/design implementing this is not possible without changing the low-level table representation.

[cznic]

Based on my reading of ql/design implementing this is not possible without changing the low-level table representation.

Not sure about that. Composite indices are supported but not yet used beyond enforcing the UNIQUE constraint. I think that the only missing piece is to teach the planner to use composite indices at all.

Do you feel like giving it a try? 😉

[twitchyliquid64]

I would like to. I am trying to wrap my head around the internals ATM.

From what I can tell, I need to:

• Make a new plan type, compositeIndexPlan, which can be very similar to indexPlan
• Update ____Rset.plan() functions in ql.go to use the composite index at the right times

Is this correct?

Where in the codebase are the composite indexes written to?

[cznic]

Is this correct?

From the top of my head: yes.

Where in the codebase are the composite indexes written to?

These interface methods are of your interest

• storage.CreateIndex(unique bool) (handle int64, x btreeIndex, err error)
• storage.OpenIndex(unique bool, handle int64) (btreeIndex, error)
• btreeIndex.Create(indexedValues []interface{}, h int64) error
• btreeIndex.Delete(indexedValues []interface{}, h int64) error

Look for the implemetations of the above in {file,mem}.go

[twitchyliquid64]

Ok thanks. I'm still getting the lay of the land a little, one more set of conclusions it would be helpful if you could double check. This is my end-to-end understanding of a QL statement execution:

1. parser.go is an autogenerated file, which reads QL statements and constructs an AST of stmt nodes. These nodes are defined in stmt.go and self describe with polymorphic methods.
2. A query context is created by calling db.Execute(), which sets up the state/transaction in ql.go:run1. Query planning is done on compilation by calling exec() on a stmt node which then calls plan(). It then uses a polymorphic method exec to generate a query plan, which is returned as a recordset, which itself is a tuple of a query plan and context.
3. Actual execution is done by calling do() on the recordset, which yields to do() on the query plan, which itself calls child plans polymorphically. Records are returned by calling a callback which is implemented in recordset.Do().

Based on this, I think I only need to modify the logic in whereRset.plan, and make a compositeIndexPlan, along with a metric fuckton of tests.

[cznic]

I'm still getting the lay of the land a little, one more set of conclusions it would be helpful if you could double check.

Will do, but only later today as I don't want to mislead you by providing a quick, but incorrect answer.

Based on this, I think I only need to modify the logic in whereRset.plan, and make a compositeIndexPlan, along with a metric fuckton of tests.

Sounds easy, which is in my experience seldom confirmed when actually implementing the plan ;-)

[cznic]

This is my end-to-end understanding of a QL statement execution:

1. ...

Yes, it's an AST, nodes are stmt or expression.

2. ...

Seems correct.

3. ...

Ditto.

---

Even if I really tried to verify the correctness of your understanding, it's a long time the code was written. Apologies if I've got something wrong.