Index optimization: the code.

Below is an implementation of index optimization algorithm implemented in Clojure. Perhaps it is not an example of good Clojure style but it leaves less ambiguities than plain words description from my previous post. The GitHub's gist is below, I hope that it is self-explanatory:

	(ns lab.indexes)
	(defn fields-prefix?
	"All fields of b are prefix of a"
	[a b]
	(= (set (take (count (:fields b)) (:fields a))) (set (:fields b))))
	(defn implies?
	"Optimizations allowed by index a include ones allowed by index b (MySql)"
	[a b]
	(or
	(and
	(= (set (:fields a)) (set (:fields b)))
	(or
	(= (:type a) (:type b))
	(= (:type b) :plain)
	(and (= (:type a) :primary) (= (:type b) :unique))))
	(and
	(fields-prefix? a b)
	(= (:type b) :plain))))
	(defn optimize-indexes
	([indexes]
	(optimize-indexes [] indexes))
	([r [x & xs]]
	(let [pred #(implies? x %)
	fr (remove pred r)
	fxs (remove pred xs)
	l (conj fr x)]
	(if (empty? fxs)
	l
	(optimize-indexes l fxs)))))
	(defn check-indexes [indexes]
	(let [pri-keys (filter #(= (:type %) :primary) indexes)]
	(if (< 1 (count pri-keys))
	{:conflicting-primary-keys pri-keys}
	{})))
	; ---------------------------------------------------------
	; Tests
	(let [ia {:type :primary :fields [:a :b :c]}
	ib {:type :plain :fields [:a :b]}
	ic {:type :primary :fields [:a :b]}
	id {:type :unique :fields [:b :a :c :d]}
	ie {:type :plain :fields [:b :a]}]
	(assert (fields-prefix? id ib))
	(assert (fields-prefix? id ia))
	(assert (implies? ia ib))
	(assert (not (implies? ib ia)))
	(assert (implies? ib ib))
	(assert (not (implies? ib ic)))
	(assert (not (implies? id ia)))
	(assert (implies? id ib))
	(assert (implies? ie ib))
	(assert (implies? ib ie))
	(assert (not (implies? id ia)))
	(assert (not (implies? ia id)))
	(println)
	(let [optimized (optimize-indexes [ia ib ic id ie])]
	(println optimized)
	(println (check-indexes optimized)))
	(println)
	(let [optimized2 (optimize-indexes [ia ib id ie])]
	(println optimized2)
	(println (check-indexes optimized2))))

view raw index-optimizer.clj hosted with ❤ by GitHub

Optimizing set of SQL indexes.

In my current project we generating lots of code including DDL for MySQL database. To make generator code cleaner and DB happier I have added optimization procedure that takes set of indexes that cover all necessary query cases and outputs only those indexes that are really needed. For example there is no need  to add two indexes with same specification, if you have unique and non unique index with same fields then unique index is sufficient and so on. One more observation is that  if you have index on fields [a, b, c, d] then you do not need separate indexes [a, b, c],  [a, b] and [a]. There are lso 3 kinds of indexes that are important here

1. Plain, normal index
2. Unique index (is also a plain index)
3. Primary key index (is also a unique index)

So the algorithm that optimizes indexes uses

1. Some partial order on index specifications, that can be implemented as predicate that says "this index is covered by other"/"this index adds new query optimizations compared to other"
2. Procedure that finds "supremum" of given index set

There is one further optimization that I have not implemeneted because improvements from it would be minimal for our project. This optimizaation would re-order fields to try to reduce number of indexes. For example if there is laready indexes [a, b, c, d] and [a, d] then one may leave [a, d, b, c] instead.

Note that if you you use indexes not only for query/filtering but also for ordering queries then reordering filelds in indexes can be not appropriate. In this case one should also consider "ascending"/"descending" property of indexes (and do not mix them).

Showing dependency cycle in Eclipse.

Here is tiny plug-in that gathers complete build path dependency tree of a Java project in Eclipse. Eclipse tells only that there is some build path cycle but does not tell which projects are involved. If your workspace is crowded this could be a problem. The plugin allows to automatically find out cycles in project dependencies.