Slow SQLite query in kine

[miro-balaz]

I was doing a test, and found that SQL query

listSQL = fmt.Sprintf(`
		SELECT %s
		FROM kine AS kv
			LEFT JOIN kine kv2 
				ON kv.name = kv2.name
				AND kv.id < kv2.id
		WHERE kv2.name IS NULL
			AND kv.name >= ? AND kv.name < ?
			AND (? OR kv.deleted = 0)
			%%s
		ORDER BY kv.id ASC
	`, columns)

from

https://github.com/canonical/kine/tree/v0.4.1-k8s-dqlite.9

performs very badly in situations where there are many rows with the same name. I do not know how long it takes, I stopped it after few seconds. I think it might have quadratic complexity. This situation can arise in k8s after some problems. That is how I discovered it.

Is this something that is known? Are there any plans to change it?

[ktsakalozos]

Thank you for reporting this @miro-balaz . I think we should start with a test in [1] that would expose/reproduce this behavior. There is a make rule to trigger the dqlite tests [2].

[1] https://github.com/canonical/k8s-dqlite/blob/master/test/list_test.go#L13
[2] https://github.com/canonical/k8s-dqlite/blob/master/Makefile#L14

[miro-balaz]

@ktsakalozos I created a branch to my fork. I am not sure where to finally put it, maybe into benchmarks. I never created unit test for performance before.

https://github.com/miro-balaz/k8s-dqlite/tree/miro-balaz/issues/82
just this file is changed

I also have fix for that, but I do not want to rush it. Lets make sure this test is right.
After it is completed, it should be fixed also in previous versions, in kine repo.

Edit: But the test works and shows expected behaviour.

[ktsakalozos]

Since you want to improve the performance of updateEntry (make it linear) you could measure the time of the first 1000 calls to it and then assert that the time it takes to make the next 1000 batches is similar to what you expect. Fail the test if it takes more than expected. This way you can show the fix to the behavior you observe.

I would suggest you open a PR and mark it as draft.