index-optimizer.clj

(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))))