Update of /project/elephant/cvsroot/elephant/src/query In directory clnet:/tmp/cvs-serv27096/query
Added Files: algebra.lisp compile.lisp execute.lisp merge.lisp planning.lisp query.lisp syntax.lisp Log Message: Placeholders and notes for query engine
--- /project/elephant/cvsroot/elephant/src/query/algebra.lisp 2007/03/06 04:15:27 NONE +++ /project/elephant/cvsroot/elephant/src/query/algebra.lisp 2007/03/06 04:15:27 1.1 ;;; -*- Mode: Lisp; Syntax: ANSI-Common-Lisp; Base: 10 -*- ;;; ;;; query.lisp -- Implement syntax for the elephant query engine ;;; ;;; Copyright (c) 2007 by Ian S. Eslick ;;; <ieslick at common-lisp.net> ;;; ;;; Elephant users are granted the rights to distribute and use this software ;;; as governed by the terms of the Lisp Limited General Public License ;;; (http://opensource.franz.com/preamble.html), also known as the LLGPL. ;;;
(in-package :elephant)
;; ;; Relational algebra ;;
(defparameter *relation-algebra-grammar* '((select <op> <attr> <attr or value> <nset>) (project <op> <attr-list> <nset>) (rename <attr> <attr> <nset>) (union <nset> <nset>) (intersection <nset> <nset>) (difference <nset> <nset>) (divide <nset> <nset>) (natural-join <attr> <nset> <attr> <nset>) (theta-join op <attr> <nset> <attr> <nset>) (semi-join <attr> <nset> <attr> <nset>) (anti-join <attr> <nset> <attr> <nset>)))
;; ;; Theorems ;;
;; (select op <attr> <nset>) = (select op <attr> (select op <attr> <nset>)) ;; idempotence ;; (select (and op1 op2) <attr> <nset>) = (select op1 <attr> (select op2 <attr> <nset>)) ;; commutivity ;; (select (or op1 op2) <attr> <nset>) = (union (select op1 <attr> <nset>) (select op1 <attr> <nset>)) ;; commutivity ;; (select op <attr1> <value> (union <nset1> <nset2>)) = (union (select op <attr1> <value> <nset1>) (select ...)) ;; distributivity ;; (select opA (intersection <nset1> <nset2>)) = (intersection <nset1> (select opA <nset2>))) ;; distributivity ;; (select opA (intersection <nset1> <nset2>)) = (intersection (select opA <nset1>) <nset2>) ;; (select opA (intersection <nset1> <nset2>)) = (intersection (select opA <nset1>) (select opA <nset1>))
;; ;; Optimize/Rewrite - reduce estimated set sizes ;; ;; Exercise theorems to perform certain heuristic optimizations (push selects through joins)
--- /project/elephant/cvsroot/elephant/src/query/compile.lisp 2007/03/06 04:15:27 NONE +++ /project/elephant/cvsroot/elephant/src/query/compile.lisp 2007/03/06 04:15:27 1.1 ;;; -*- Mode: Lisp; Syntax: ANSI-Common-Lisp; Base: 10 -*- ;;; ;;; query.lisp -- Implement syntax for the elephant query engine ;;; ;;; Copyright (c) 2007 by Ian S. Eslick ;;; <ieslick at common-lisp.net> ;;; ;;; Elephant users are granted the rights to distribute and use this software ;;; as governed by the terms of the Lisp Limited General Public License ;;; (http://opensource.franz.com/preamble.html), also known as the LLGPL. ;;;
(in-package :elephant)
;; ;; Compilation ;; ;; Inline execution operators using interpetive plan as template ;; as part of a macro operation
--- /project/elephant/cvsroot/elephant/src/query/execute.lisp 2007/03/06 04:15:27 NONE +++ /project/elephant/cvsroot/elephant/src/query/execute.lisp 2007/03/06 04:15:27 1.1 ;;; -*- Mode: Lisp; Syntax: ANSI-Common-Lisp; Base: 10 -*- ;;; ;;; query.lisp -- Implement syntax for the elephant query engine ;;; ;;; Copyright (c) 2007 by Ian S. Eslick ;;; <ieslick at common-lisp.net> ;;; ;;; Elephant users are granted the rights to distribute and use this software ;;; as governed by the terms of the Lisp Limited General Public License ;;; (http://opensource.franz.com/preamble.html), also known as the LLGPL. ;;;
(in-package :elephant)
;; ;; Execution ;; ;; Generate interpretive template for execution of plan; execute so ;; internal map does not require more than one in-memory tuple at a time
--- /project/elephant/cvsroot/elephant/src/query/merge.lisp 2007/03/06 04:15:27 NONE +++ /project/elephant/cvsroot/elephant/src/query/merge.lisp 2007/03/06 04:15:27 1.1 ;;; -*- Mode: Lisp; Syntax: ANSI-Common-Lisp; Base: 10 -*- ;;; ;;; merge.lisp -- Implement efficient OID lists for merge-sort ;;; ;;; Copyright (c) 2007 by Ian S. Eslick ;;; <ieslick at common-lisp.net> ;;; ;;; Elephant users are granted the rights to distribute and use this software ;;; as governed by the terms of the Lisp Limited General Public License ;;; (http://opensource.franz.com/preamble.html), also known as the LLGPL. ;;;
(in-package :elephant)
;; ;; Quick and dirty oid-set abstraction ;;
;; Notes: ;; Add pool abstraction later to reuse tenured arrays ;; Use foreign memory? ;; Paged-to-disk approaches for when we blow out main memory?
(defparameter *initial-set-size* 1000) (defparameter *set-growth-factor* 1.5)
;; ;; Create sets ;;
(defun default-oid-set-elements () (make-array 1000 :element-type 'fixnum :initial-element 0 :fill-pointer 0 :adjustable t))
(defclass oid-set () ((elements :accessor set-elements :initarg :elements :initform (default-oid-set-elements)) (oid-order :accessor set-ordered-p :initarg :ordered-p :initform nil)))
(defmethod push-oid (oid (set oid-set)) "If values are ascending, set is built in sorted order" (vector-push-extend oid (set-elements set) (floor (* *set-growth-factor* (length (set-elements set))))) (setf (set-ordered-p set) nil) oid)
(defmethod pop-oid ((set oid-set)) (vector-pop (set-elements set)))
;; do we need remove/insert?
;; ;; Operations on sets ;;
(defmethod sorted-elements ((set oid-set)) (if (set-ordered-p set) (set-elements set) (sort-set set)))
(defmethod sort-set ((set oid-set)) "Sort the set elements and return the elements" (sort (set-elements set) #'<) (setf (set-ordered-p set) t) (set-elements set))
(defmethod sort-merge-sets ((set1 oid-set) (set2 oid-set) &optional (remove-duplicates t)) (let ((new-elements (merge '(array fixnum (*) :adjustable t :fill-pointer t) (sorted-elements set1) (sorted-elements set2) #'<))) (make-instance 'oid-set :elements (if remove-duplicates (delete-duplicates new-elements) new-elements) :ordered-p t)))
(defmethod merge-sets ((set1 oid-set) (set2 oid-set) &optional (remove-duplicates t)) (let ((target (make-instance 'oid-set :ordered-p t))) (let ((elts1 (sorted-elements set1)) (elts2 (sorted-elements set2)) (offset1 0) (offset2 0) (last nil)) (loop until (or (= offset1 (fill-pointer elts1)) (= offset2 (fill-pointer elts2))) do (let ((elt1 (aref elts1 offset1)) (elt2 (aref elts2 offset2))) (cond ((= elt1 elt2) (incf offset1) (incf offset2) (unless (and remove-duplicates (eq last elt1)) (push-oid elt1 target) (setf last elt1))) ((< elt1 elt2) (push-oid elt1 target) (incf offset1)) ((< elt2 elt1) (push-oid elt2 target) (incf offset2)))))) target))
(defmethod intersect-sets ((set1 oid-set) (set2 oid-set)) (let ((target (make-instance 'oid-set :ordered-p t))) (let ((elts1 (sorted-elements set1)) (elts2 (sorted-elements set2)) (offset1 0) (offset2 0)) (loop until (or (= offset1 (fill-pointer elts1)) (= offset2 (fill-pointer elts2))) do (let ((elt1 (aref elts1 offset1)) (elt2 (aref elts2 offset2))) (cond ((= elt1 elt2) (incf offset1) (incf offset2) (push-oid elt1 target)) ((< elt1 elt2) (incf offset1)) ((< elt2 elt1) (incf offset2)))))) target))
;; ;; Test code ;;
(defun push-random-oids (set amount &optional (max 1000)) (loop for i from 0 upto amount do (push-oid (random max) set)) set)
--- /project/elephant/cvsroot/elephant/src/query/planning.lisp 2007/03/06 04:15:27 NONE +++ /project/elephant/cvsroot/elephant/src/query/planning.lisp 2007/03/06 04:15:27 1.1 ;;; -*- Mode: Lisp; Syntax: ANSI-Common-Lisp; Base: 10 -*- ;;; ;;; query.lisp -- Implement syntax for the elephant query engine ;;; ;;; Copyright (c) 2007 by Ian S. Eslick ;;; <ieslick at common-lisp.net> ;;; ;;; Elephant users are granted the rights to distribute and use this software ;;; as governed by the terms of the Lisp Limited General Public License ;;; (http://opensource.franz.com/preamble.html), also known as the LLGPL. ;;;
(in-package :elephant)
;; ;; Planner ;; ;; Generate all possible access plans to O-relations ;; Generate all possible joins of O-relations ;; Organize into equiv. classes ;; Evaluate the cost of options in equiv classes ;; Select best in each class ;; Roll cost upto whole join tree ;; Iterate each join tree to repeat with other joins ;; Do best-first through equiv classes?
--- /project/elephant/cvsroot/elephant/src/query/query.lisp 2007/03/06 04:15:27 NONE +++ /project/elephant/cvsroot/elephant/src/query/query.lisp 2007/03/06 04:15:27 1.1 ;;; -*- Mode: Lisp; Syntax: ANSI-Common-Lisp; Base: 10 -*- ;;; ;;; query.lisp -- Implement syntax for the elephant query engine ;;; ;;; Copyright (c) 2007 by Ian S. Eslick ;;; <ieslick at common-lisp.net> ;;; ;;; Elephant users are granted the rights to distribute and use this software ;;; as governed by the terms of the Lisp Limited General Public License ;;; (http://opensource.franz.com/preamble.html), also known as the LLGPL. ;;;
(in-package :elephant)
;; ;; User query API ;;
(defmacro map-query (fn constraints) (let ((classes (constraint-expr-classes constraints)) (plan (compile-query-plan (parse-constraints constraints)))) `(map-query-plan ,fn ,plan)))
;;(defun map-constraints (fn classes plan) ;; (declare (dynamic-extent sc))
;; ;; Wrappers and standard operations for map-constraints ;;
(defmacro with-collector ((collector-var &key function init expr) &body body) "Instantiates a list collector to pass to a mapping function and the whole expression returns the result of the collector. For something other than list construction, expr can be used. If function is used, it is assumed to be the name of a function of two variables of two arguments where the first argument is the collector variable and the second is the current value being mapped. It should return the new value of the collector variable. Otherwise it is an expression containing a followed by a function body has the form of an flet entry with one parameter (name (arg) body). Init is the initial value of the result variable" (with-gensyms (result-var elt) `(let ((,result-var ,init)) (flet ((,collector-var ,@(cond ((and (null expr) (null function)) `((,elt) (push ,elt ,result-var))) (function `((,elt) (setf ,result-var (funcall ,function ,result-var ,elt)))) (expr (multiple-value-bind (arg &body body) expr `((,arg) ,@body)))))) (declare (dynamic-extent ,collector-var)) ,@body)))) --- /project/elephant/cvsroot/elephant/src/query/syntax.lisp 2007/03/06 04:15:27 NONE +++ /project/elephant/cvsroot/elephant/src/query/syntax.lisp 2007/03/06 04:15:27 1.1 ;;; -*- Mode: Lisp; Syntax: ANSI-Common-Lisp; Base: 10 -*- ;;; ;;; syntax.lisp -- Implement syntax for the elephant query engine ;;; ;;; Copyright (c) 2007 by Ian S. Eslick ;;; <ieslick at common-lisp.net> ;;; ;;; Elephant users are granted the rights to distribute and use this software ;;; as governed by the terms of the Lisp Limited General Public License ;;; (http://opensource.franz.com/preamble.html), also known as the LLGPL. ;;;
(in-package :elephant)
;; ;; Operations and aggregators ;;
(defvar *legal-operators* '(= /= < > <= >= string= string/= string< string> string>= string<= string-equalp string-not-equal string-lessp string-not-lessp string-greaterp string-not-greaterp map member type-p subtype-p))
(defun legal-operator-p (op) (member op *legal-operators*))
(defparameter *legal-aggregation-operators* '(and or xor))
(defun aggregation-operator-p (atom) (member op *legal-aggregation-operators*))
;; ;; Parser ;; ;; Transform surface expressions to RA expressions with set object-relation closure property
;; (map-query fn (a b) ;; (:with ((mgr person) (job job))) ;; (:declare (type person emp) ;; (type project proj) ;; (type department (department person))) ;; (:constraints or :where ;; (between (start-date proj) (convert-date "July 5th 1996") (convert-date "November 1st 1996")) ;; (eq (project emp) proj) ;; (member (name (department emp)) '("Marketing" "Administration")) ;; (eq (supervisor emp) mgr) ;; (>= (slot salary mgr) 100000)))
;; Parser entry
(defun get-clause (namelist clauses &optional error) (assert namelist) (setf namelist (mklist namelist)) (aif (assoc (car namelist) clauses) (cdr it) (if (null (cdr namelist)) (when error (error error)) (get-clause (cdr namelist) clauses error))))
(defun parse-query-syntax (query) (construct-ra-graph (parse-constraints (get-clause '(:constraints constraints :where where) query) (parse-declarations (get-clause '(:declare declare) query) (parse-targets (get-clause '(:with with) query) (make-relation-dictionary))))))
;; Dictionary
(defun make-relation-dictionary () (cons nil nil))
(defun add-set (name class stmt dictionary &optional annotations) (push (list name class stmt annotations) (car dictionary)))
(defun lookup-set (name dict) (awhen (assoc name (car dict)) it))
(defun set-name (setrec) (first setrec))
(defun set-type (setrec) (second setrec))
(defun set-statement (setrec) (third setrec))
[145 lines skipped]
-
ieslick