Ruby's hash implementation

Authentication

Login with:New JS-Kit AccountMy Google ProfileMy Twitter AccountMy FriendFeed AccountMy Yahoo! AccountMy Blogger AccountMy JS-Kit AccountMy Haloscan AccountMy OpenID

Ruby's Hash class is implemented using the same engine that it uses for symbol table.

It is not meant for high-volume usage.

/tmp $ ruby testspeed.rb 
Rehearsal ----------------------------------------------------------------------------------------------
reading with while, name=1million                            1.240000   0.030000   1.270000 (  1.272282)
reading with readline, name=1million                         0.980000   0.210000   1.190000 (  1.215839)
reading with while and inserting into hash, name=1million    5.330000   0.200000   5.530000 (  5.715192)
reading with while and inserting into array, name=1million   5.640000   0.210000   5.850000 (  5.975710)
------------------------------------------------------------------------------------ total: 13.840000sec

                                                                 user     system      total        real
reading with while, name=1million                            1.750000   0.020000   1.770000 (  1.785138)
reading with readline, name=1million                         1.440000   0.010000   1.450000 (  1.454656)
reading with while and inserting into hash, name=1million    4.050000   0.020000   4.070000 (  4.102691)
reading with while and inserting into array, name=1million   2.290000   0.020000   2.310000 (  2.320377)

def create_file(name, size)
  File.open("/tmp/largefile_#{name}", "w") {|f| size.times {|i|f.puts "foo#{i}"; } }
end

# do these once
# create_file("1million", 1*1000*1000)
# create_file("5million", 5*1000*1000)

def read_with_while(name)
  File.open("/tmp/largefile_#{name}") {|fh|
    while line = fh.gets
      line.chomp!
    end
  }
end

def read_with_readlines(name)
  File.readlines("/tmp/largefile_#{name}")
end

def read_into_hash(name)
  hash={}; array=[]; File.open("/tmp/largefile_#{name}"){ |fh| while line = fh.gets; line.chomp!; 
                                                                 hash[line] = 1; 
                                                               end} 
end
def read_into_array(name)
  array=[]; File.open("/tmp/largefile_#{name}"){ |fh| while line = fh.gets; line.chomp!; 
                                                                 array << line
                                                               end} 
end

require 'benchmark'
Benchmark.bmbm {|r|
  ["1million"].each{|name|
    GC.start
    r.report("reading with while, name=#{name}") {read_with_while(name)}
    GC.start
    r.report("reading with readline, name=#{name}") {read_with_readlines(name)}
    GC.start
    r.report("reading with while and inserting into hash, name=#{name}") { read_into_hash(name)}
    GC.start
    r.report("reading with while and inserting into array, name=#{name}") { read_into_array(name)}
  }
} 

(originally from http://microjet.ath.cx/WebWiki/2006.04.15_Ruby%27sHash.html)

Linksys WRE54G version 2.0 (repeater/extender)

Authentication

Login with:New JS-Kit AccountMy Google ProfileMy Twitter AccountMy FriendFeed AccountMy Yahoo! AccountMy Blogger AccountMy JS-Kit AccountMy Haloscan AccountMy OpenID

I finally did something to address weak signals from my wireless router, a 2-year old Netgear device. I went to CompUSA thinking of buying Linksys WRT54G router, but instead ended up buying the Linksys WRE54G version 2.0.

Toms Hardware reviewed this device sometimes ago. They were not really impressed by the product and the setup was painful. They were reviewing version 1.0.

True enough, things have changed in version 2.0. The device now includes a RJ-45 port for wired setup. This makes the setup easier somehow.

Setup was not difficult, except for the following:

1. The SSID must be the same as the router's SSID. This is an annoyance since that means I can't choose which device to connect to for comparison purposes.
2. The router has been setup to use 64bit WEP. But the expander's WEP implementation seems to not be compatible as it couldn't connect to the router. Fortunately, its WPA Personal implementation is compatible with the router's.

I put the expander in the middle of the signal edge and the router in contrary to putting it at the edge as written in the manual. Putting it at the edge does not really make much sense since at the expander would have difficulty communicating with the router. I bought the device to expand range but I do not want to sacrifice signal quality.

With the expander activated, I now can go beyond the previous range. However, interactive session sucked real bad. It seems the device is buffering data, which is bad for interactive session.
I returned it after several days because I work with interactive session most of the time.

(originally from http://microjet.ath.cx/WebWiki/2006.03.25_Linksys_WRE54G_v2.html)

Hexifier and XML entities escaper

Happy belated Valentine's day.



I have a present for Emacser out there: a hexifier and XML Entities
escapers.

ys-hex306.el

(require 'hexl)

(defun ys/escape (string to-escape-char &optional escape-char)
  ;; Escapes all instances of to-escape-char in the given string by prefixing each instance with escape-char (default to backslash ``\``).
  ;;
  ;; (let ((str "/ \\/ \\\\/ \\n"))
  ;;   (insert (concat "\n" str "\n" (ys/escape str ?/))))
  ;; / \/ \\/ \n
  ;; \/ \\\/ \\\\\/ \\n



"  Escapes all instances of to-escape-char in the given string by prefixing each instance with escape-char (default to backslash ``\\``).
  
  (let ((str \"/ \\\\/ \\\\\\\\/ \\\\n\"))
    (insert (concat \"\\n\" str \"\\n\" (ys/escape str ?/))))
  / \\/ \\\\/ \\n
  \\/ \\\\\\/ \\\\\\\\\\/ \\\\n
"
  (if (eq escape-char nil)
      (setq escape-char ?\\))
  (with-temp-buffer
    (insert string)
    (goto-char (point-min))
    (save-match-data
      (let ((regexp (concat (regexp-quote (char-to-string to-escape-char))
                                   "\\|"
                                   (regexp-quote (char-to-string escape-char)))))
        (while (re-search-forward regexp (point-max) t)
          (replace-match (concat (char-to-string escape-char)
                                 (match-string 0)) t t))))
    (buffer-substring (point-min) (point-max))))











(defun ys/unescape (string &optional escape-char) 
  ;; Converts ``\/ \n \\\/`` to ``/ n \/``. Basically converts ``\x`` to ``x`` where x is any single character and \ is the escape-char."
  ;; (let ((str "/ \\/ \\\\/ \\n"))
  ;;   (insert (concat "\n" str
  ;;              "\n" (ys/escape str ?/)
  ;;              "\n" (ys/unescape (ys/escape str ?/)))))
  ;; / \/ \\/ \n
  ;; \/ \\\/ \\\\\/ \\n
  ;; / \/ \\/ \n


"  Converts ``\\/ \\n \\\\\\/`` to ``/ n \\/``. Basically converts ``\\x`` to ``x`` where x is any single character and \\ is the escape-char.\"
  (let ((str \"/ \\\\/ \\\\\\\\/ \\\\n\"))
    (insert (concat \"\\n\" str
                  \"\\n\" (ys/escape str ?/)
                  \"\\n\" (ys/unescape (ys/escape str ?/)))))
  / \\/ \\\\/ \\n
  \\/ \\\\\\/ \\\\\\\\\\/ \\\\n
  / \\/ \\\\/ \\n

"
  (if (eq escape-char nil)
      (setq escape-char ?\\))
  (with-temp-buffer
    (insert string)
    (goto-char (point-min))
    (save-match-data
      (let ((regexp (concat (regexp-quote (char-to-string escape-char))
                            "\\(.\\)")))
        (while (re-search-forward regexp (point-max) t)
          (replace-match (match-string 1) t t))))
    (buffer-substring (point-min) (point-max))))
  





(defun ys/hexstring-to-charstring (hexstring)
;(insert (concat "\n" (ys/hexstring-to-charstring "039900000000000000000000000046")))
; ™������������F
"(insert (concat \"\\n\" (ys/hexstring-to-charstring \"039900000000000000000000000046\")))
 \231������������F
"
  (let ((expected-length (/ (length hexstring) 2)))
    (save-excursion
        (let ((result 
               (with-temp-buffer
                 (insert hexstring)
                 (goto-char (point-min))
                 (save-match-data
                   (while (and (not (eobp))
                               (looking-at "\\([0-9A-Fa-f]\\)\\([0-9A-Fa-f]\\)"))
                     (replace-match (char-to-string (hexl-htoi (string-to-char (match-string 1))
                                                               (string-to-char (match-string 2)))) 
                                    t 
                                    t)))
                 (buffer-substring (point-min) (point-max)))))
          ;; check if the conversion is valid
          (let ((result-length (length result)))
            (if (/= result-length expected-length)
                (error "Expected a charstring of length %d, but instead the length is %d" expected-length result-length)))
          result))))



(defun ys/charstring-to-hexstring (charstring)
                                        ;(insert (concat "\n" (ys/charstring-to-hexstring " ™������������F")))
                                        ;039900000000000000000000000046
  "(insert (concat \"\\n\" (ys/charstring-to-hexstring \" \231������������F\")))
039900000000000000000000000046

"
  (mapconcat #'(lambda (char) 
                 (format "%02x" char))
             charstring
             ""))





(defun ys/hex306string-to-char306string (hex306string)
                                        ;(insert (concat "\n" (ys/hex306string-to-char306string "303132332f636f6e7665727420746869732f2062757420/don't convert this/2066696e616c6c79202f636f6e7665727420746869732f")))
                                        ;0123\/convert this\/ but /don't convert this/ finally \/convert this\/
  "(insert (concat \"\\n\" (ys/hex306string-to-char306string \"303132332f636f6e7665727420746869732f2062757420/don't convert this/2066696e616c6c79202f636f6e7665727420746869732f\")))
0123\\/convert this\\/ but /don't convert this/ finally \\/convert this\\/
"
  (save-excursion
    (with-temp-buffer
        (insert hex306string)
        (goto-char (point-min))
        (save-match-data
          (while (and (not (eobp)) ;; needed because the regexp below won't fail due to *
                      (re-search-forward "\\([0-9A-Fa-f]*\\)" (point-max) t))
                                        ;(message (match-string 0))
            (let* ((hexstring (match-string 0))
                   (charstring (ys/hexstring-to-charstring (match-string 0)))
                   (escapedcharstring (ys/escape charstring ?/)))
                                        ;(message (format "hexstring:%s\ncharstring:%s\nescaped:%s" hexstring charstring escapedcharstring))
              (replace-match escapedcharstring t t))
                                        ;(message (format "reminder:%s" (buffer-substring (point) (point-max))))
            (if (looking-at "/.*?/") 
                (goto-char (match-end 0))
              (if (< (point) (point-max))
                  (error "Invalid hex306 string. Encountered a non-hexchar char but also not surrounded with //")))))
        (buffer-substring (point-min) (point-max)))))





(defun ys/char306string-to-hex306string (char306string)
;(insert (concat "\n" (ys/char306string-to-hex306string "\n0123\\/convert this\\/ but /don't convert this/ finally \\/convert this\\/")))
;0a303132332f636f6e7665727420746869732f2062757420/don't convert this/2066696e616c6c79202f636f6e7665727420746869732f

  "(insert (concat \"\\n\" (ys/char306string-to-hex306string \"\\n0123\\\\/convert this\\\\/ but /don't convert this/ finally \\\\/convert this\\\\/\")))
0a303132332f636f6e7665727420746869732f2062757420/don't convert this/2066696e616c6c79202f636f6e7665727420746869732f

"
  (save-excursion
    (with-temp-buffer 
      (insert char306string)
      (goto-char (point-min))
      (save-match-data
        (let ((charstring-begin (point-min)))
          (while (not (eobp)) 
            (cond ((looking-at "\\\\.") ; skip over escaped char. we must consume escaped char first so when we scan for a don't-convert-region, we won't get a false positive
                   )
                  ((looking-at "/\\(.*?\\)/") ; leave the don't-convert-this-region alone, but convert previous characters to hex
                   (let ((charstring (buffer-substring charstring-begin (match-beginning 0))))
                     (re-search-backward (regexp-quote charstring))
                     (replace-match (ys/charstring-to-hexstring (ys/unescape charstring)))
                                        ;(message (format "remaining:%s" (buffer-substring (point) (point-max))))
                                        ; the match-data info would have changed (because the length of charstring changed) , so we re-run the search
                     (if (looking-at "/\\(.*?\\)/")
                         (setq charstring-begin (match-end 0))
                       (error "Lost pointer to the don't-convert-region"))))
                  ((looking-at ".\\|\n") ; skip over other char
                   )
                  (t (error "Shouldn't have happened")))
            ;(message (format "going to %d/%d, remaining:%s" (match-end 0) (point-max) (buffer-substring (match-end 0) (point-max))))
            (goto-char (match-end 0)))
          (let ((charstring (buffer-substring charstring-begin (match-end 0))))
            (re-search-backward (regexp-quote charstring))
            (replace-match (ys/charstring-to-hexstring (ys/unescape charstring))))))
      ;(message (format "End-state:%s" (buffer-substring (point-min) (point-max))))
      (buffer-substring (point-min) (point-max)))))








;; ys/charstring-to-hexstring-region and ys/hexstring-to-charstring-region converts between these two forms:
;; 0123\/convert this\/ but /don't convert this/ finally \/convert this\/ 
;; 303132335c2f636f6e7665727420746869735c2f20627574202f646f6e277420636f6e7665727420746869732f2066696e616c6c79205c2f636f6e7665727420746869735c2f


(defun ys/hexstring-to-charstring-region (region-begin region-end)
  "Converts ``039900000000000000000000000046`` to `` ™������������F``"
  (interactive "r")
  (save-excursion
    (let ((charstring (ys/hexstring-to-charstring (buffer-substring region-begin region-end))))
      (delete-region region-begin region-end)
      (goto-char region-begin)
      (insert charstring))))


(defun ys/charstring-to-hexstring-region (region-begin region-end)
  "Converts `` ™������������F`` to ``039900000000000000000000000046``"
  (interactive "r")
  (save-excursion
    (let* ((charstring (buffer-substring region-begin region-end))
           (hexstring (ys/charstring-to-hexstring charstring)))
      (delete-region region-begin region-end)
      (goto-char region-begin)
      (insert hexstring))))




;; ys/char306string-to-hex306string-region and ys/hex306string-to-char306string-region converts between these two forms:
;; 0123\/convert this\/ but /don't convert this/ finally \/convert this\/
;; 303132332f636f6e7665727420746869732f2062757420/don't convert this/2066696e616c6c79202f636f6e7665727420746869732f

(defun ys/char306string-to-hex306string-region (region-begin region-end)
  "Converts ``0123\/convert this\/ but /don't convert this/ finally \/convert this\/`` to 
``303132332f636f6e7665727420746869732f2062757420/don't convert this/2066696e616c6c79202f636f6e7665727420746869732f``"
  (interactive "r")
  (save-excursion (let* ((char306string (buffer-substring region-begin region-end))
                         (hex306string (ys/char306string-to-hex306string char306string)))
                    (delete-region region-begin region-end)
                    (goto-char region-begin)
                    (insert hex306string))))

(defun ys/hex306string-to-char306string-region (region-begin region-end)
  "Converts ``303132332f636f6e7665727420746869732f2062757420/don't convert this/2066696e616c6c79202f636f6e7665727420746869732f`` to
``0123\/convert this\/ but /don't convert this/ finally \/convert this\/``"
  (interactive "r")
  (save-excursion
    (let ((char306string (ys/hex306string-to-char306string (buffer-substring region-begin region-end))))
      (delete-region region-begin region-end)
      (goto-char region-begin)
      (insert char306string))))



(provide 'ys-hex306)

ys-xml-escape.el

(require 'cl)
(defun ys/xml-escape-entities-and-non-printable-ascii (string)
  "Escapes XML entities and any non-ascii characters and also ascii characters that are not ``printable`` ( 32 < x < 126 )."
  (mapconcat 
   #'(lambda (char)
       (case char
         (?< "&lt;")
         (?> "&gt;")
         (?& "&amp;")
         (?' "&apos;")
         (?\" "&quot;")
         (t  (if (and (<= 32 char)
                      (<= char 126))
                 (char-to-string char)
               (format "&#%02d;" char)))))
   string
   ""))
;(insert (concat "\n" (ys/xml-escape-entities-and-non-printable-ascii "<goo&ten, \"'night\", he said>�")))
;&lt;goo&amp;ten, &quot;&apos;night&quot;, he said&gt;&#00;

(defun ys/xml-unescape-entities (string)
  "Unescapes XML entities"

  (save-excursion
    (with-temp-buffer
      (insert string)
      (goto-char (point-min))
      (while (not (eobp))
        (cond ((looking-at "&#\\([[:digit:]]+?\\);")
               (let ((char (string-to-number (match-string 1) 16)))
                 (replace-match (char-to-string char))
                 (goto-char (match-end 0))))
              ((looking-at "&\\(.+?\\);") 
               (let ((entity (match-string 1)))
                 (replace-match (case (intern entity)
                                  ('lt "<")
                                  ('gt ">")
                                  ('amp "&")
                                  ('apos "'")
                                  ('quot "\"")
                                  (t (error "Unknown XML entity: %s" entity))))))
              (t (goto-char (+ 1 (point))))))
      (buffer-substring (point-min) (point-max)))))
;(insert (concat "\n" (ys/xml-unescape-entities "&lt;goo&amp;ten, &quot;&apos;night&quot;, he said&gt;&#00;")))
;<goo&ten, "'night", he said>�

(eql (intern "lt") 'lt)


(defun ys/xml-escape-entities-and-non-printable-ascii-region (region-begin region-end)
  "Escapes XML entities and any non-ascii characters and also ascii characters that are not ``printable``."
  (interactive "r")
  (save-excursion
    (let ((escaped (ys/xml-escape-entities-and-non-printable-ascii (buffer-substring region-begin region-end))))
      (delete-region region-begin region-end)
      (goto-char region-begin)
      (insert escaped))))

(defun ys/xml-unescape-entities-region (region-begin region-end)
  "Unescapes XML entities"
  (interactive "r")
  (save-excursion
    (let ((unescaped (ys/xml-unescape-entities (buffer-substring region-begin region-end))))
      (delete-region region-begin region-end)
      (goto-char region-begin)
      (insert unescaped))))

(provide 'ys-xml-escape)

What I put into my .emacs for these two utils:

(require 'ys-hex306)
(global-set-key "\C-chc" 'ys/hex306string-to-char306string-region)
(global-set-key "\C-chh" 'ys/char306string-to-hex306string-region)
(require 'ys-xml-escape)
(global-set-key "\C-cxe"
'ys/xml-escape-entities-and-non-printable-ascii-region)
(global-set-key "\C-cxu" 'ys/xml-unescape-entities-region)

(defun ys/quote-for-docstring (region-begin region-end)
  (interactive "r")
  (save-excursion
    (let* ((original-mode-name mode-name)
           (commented (buffer-substring-no-properties region-begin
  region-end))
           (uncommented (with-temp-buffer
                          (funcall (symbol-function (intern (format
  "%s-mode" (downcase original-mode-name)))))
                          (insert commented)
                          (uncomment-region (point-min) (point-max))
                          (buffer-substring-no-properties (point-min)
  (point-max))))
           (quoted (with-output-to-string (print uncommented))))
      (insert quoted))))

The function ys/quote-for-docstring= is especially handy for
constructing a docstring with a lot of backslashes.


(originally from http://microjet.ath.cx/WebWiki/2006.02.15_Hexifier_and_XML_Entities_Escaper.html)

RSS and VSZ are not an accurate measure of memory usage

Yesterday I had the honour to chat with Bosko Milekic, a FreeBSD developer, regarding his concern of the outrageous VSS and RSS (virtual memory size and resident size, respectively) of a ruby app. I remembered that I had some code showing that VSS and RSS do not accurately measure an app's memory usage.
Since this was Bosko Milekic I was talking with, he was able to use the code to further investigate the problem matter. The best part is, he wrote a write-up (Ruby on Rails and Application Memory Consumption Patterns) of what he has learnt including what his further investigation revealed. As a result, now I know more than yesterday.
Isn't collaboration simply wonderful?

Updated 2007-04-20: updated linked URI.

(originally from http://microjet.ath.cx/WebWiki/2006.01.12_RSS_and_VSZ_AreNotAccurateMeasureOfMemoryUse.html)

Using symbols for the wrong reason

Authentication

Login with:New JS-Kit AccountMy Google ProfileMy Twitter AccountMy FriendFeed AccountMy Yahoo! AccountMy Blogger AccountMy JS-Kit AccountMy Haloscan AccountMy OpenID

The concept of symbols have been popular among the lisp community, yet not many people know about it mainly due to the general ignorance.
Then ruby came and made symbols be a commodity programming construct. People who were not aware of symbols now are.

And they are asking about it numerous times. There is not a week in the ruby mailing list that there isn't a question about symbols: what are they and what are they good for?

Many people have tried to answer that, but the answer has been along the lines presented in these two articles: http://glu.ttono.us/articles/2005/08/19/understanding-ruby-symbols and http://zephyrfalcon.org/weblog2/arch_e10_00850.html#e857.

The answer has been putting undue emphasise on the way current ruby VM implements symbols. Ruby string is mutable, and it is not efficiently implemented in current ruby VM. So, use symbols for efficient, immutable, and string-like objects.

It is not wrong and it is correct for current ruby VM. However, I think, that is a misguided answer to the questions. The answer should, on the other hand, put an emphasise on the programmer's intention.
rubyists uses #each() method more frequently than a for loop because it clarifies their intention of iterating over some sequence even though they could have used the more efficient for loop or even the if and goto constructs.

One does not tell another to use if and goto over for loop for iterating a sequence simply because if and goto may be more efficient. No matter how inefficient a compiler/interpreter implements the for loop construct, the possibility of an efficient for loop implementation remains. In fact, by using the for construct, the compiler could have an easier time deducing your intent of looping, and if some conditions are met (e.g., closed looping of certain numbers of times), it could unroll your loop for a better performance if your systems allows it.

In short, any answer that depends on a particular implementation is doomed to be short-lived. What happens if the next ruby VM implements COW (copy-on-write) strings? A COW string would share initial instances. Only f there is a modification to the instance, then the initial instance is copied and the modification is performed on the copy. As long as one does not try to modify COW string instance, it can be as efficient as how the current VM implements symbols. IOW, any answer that rallies around so-called efficiency while abandoning intent would become obsolete and there is a new scramble to get at an updated answer.

Thus, I finally come to say that one should not use symbols just for efficiency gain. Symbols are not meant to be an immutable string-like object. It is really meant to be used to construct user-defined identifiers. The user in this case would be the programmers.

Consider:

foo1 = { 
   :host => 'localhost',
   :port => 80
}
foo2 = {
   'host' => 'localhost',
   'port' => 80

In foo1, symbols are being used to identify the following data. The string 'localhost' is identified as a host, and 80 is not just any number, but rather a port number.

In foo2, it is a bit unclear as to what purpose 'host' and 'port' serves. Is foo2 a macro replacement list? That is, if the program reads the string 'host', would it be replaced to 'localhost'? What is the purpose of 'host' there? Is it an identifier for the string 'localhost'?

The programming world should borrow the real estate's adage of "location, location, location". It should be translated to: "intention, intention, intention". It is the main reason why comments that clarifies the intention of the programmer are so valuable. It is the main reason why there are a variety language constructs. It should also be the main reason for you to decide whether or not to use symbols.

2005.12.28 update: I am joyful that not everyone resorted to dumbing down the concept of symbols. http://onestepback.org/index.cgi/Tech/Ruby/SymbolsAreNotImmutableStrings.red
2006.01.06 update: What an amazing interest on symbol! I don't think I've seen any one topic in ruby that has generated 142 posts in a single thread before this.
http://groups.google.com/group/comp.lang.ruby/browse_frm/thread/164ae5f5cbbac02e?q=differences+between+%3Afoo&hl=en&
2007.07.03 update: a related article: 2007.07.03_WhatAreSymbols

(originally from http://microjet.ath.cx/WebWiki/2005.12.27_UsingSymbolsForTheWrongReason.html)

Preferring natural to surrogate key

Authentication

Login with:New JS-Kit AccountMy Google ProfileMy Twitter AccountMy FriendFeed AccountMy Yahoo! AccountMy Blogger AccountMy JS-Kit AccountMy Haloscan AccountMy OpenID

I was reading an article at The Daily WTF today. The OP (original posts) sparked a debate on the use of surrogate vs. natural key.


It is really sad to see Jeff S. et. al fighting the horde of ignorants, but that is a battle that has been fought many times before and is not what I want to write about here.

What I want to show here is the difference in query time you'd expect to see by trimming down on unnecessary usage of surrogate keys.

A schema with unnecessary surrogate keys.

-- Done on postgresql 8.1

dms3_test=> \d document
                                         Table "dms4.document"
    Column     |           Type           |                          Modifiers                          
---------------+--------------------------+-------------------------------------------------------------
 id            | integer                  | not null default nextval('document_id_seq'::regclass)
 state         | text                     | not null
 modified_who  | text                     | not null
 modified_when | timestamp with time zone | not null default ('now'::text)::timestamp(6) with time zone
 created_who   | text                     | not null
 created_when  | timestamp with time zone | not null default ('now'::text)::timestamp(6) with time zone
Indexes:
    "document_pkey" PRIMARY KEY, btree (id)
    "document_created_when" btree (created_when)
    "document_created_who" btree (created_who)
    "document_modified_when" btree (modified_when)
    "document_modified_who" btree (modified_who)
    "document_state" btree (state)
Foreign-key constraints:
    "document_created_who_fkey" FOREIGN KEY (created_who) REFERENCES who(name)
    "document_modified_who_fkey" FOREIGN KEY (modified_who) REFERENCES who(name)
    "document_state_fkey" FOREIGN KEY (state) REFERENCES state(name)

dms3_test=> \d attribute_name
                            Table "public.attribute_name"
 Column |  Type   |                            Modifiers                             
--------+---------+------------------------------------------------------------------
 id     | integer | not null default nextval(('attribute_name_seq'::text)::regclass)
 name   | text    | not null
Indexes:
    "attribute_name_pkey" PRIMARY KEY, btree (id)
    "an_name_idx" UNIQUE, btree (name)

dms3_test=> \d attribute
                          Table "public.attribute"
 Column  |  Type   |                       Modifiers                        
---------+---------+--------------------------------------------------------
 id      | integer | not null default nextval('attribute_id_seq'::regclass)
 name_id | integer | not null
 value   | text    | not null
Indexes:
    "attribute_pkey" PRIMARY KEY, btree (id)
    "attr_nv_idx" UNIQUE, btree (name_id, value)
Foreign-key constraints:
    "$1" FOREIGN KEY (name_id) REFERENCES attribute_name(id)


dms3_test=> \d document_attribute
 Table "public.document_attribute"
    Column    |  Type   | Modifiers 
--------------+---------+-----------
 doc_id       | integer | not null
 attribute_id | integer | not null
Indexes:
    "document_attribute_pkey" PRIMARY KEY, btree (doc_id, attribute_id) CLUSTER
    "da_ad_idx" UNIQUE, btree (attribute_id, doc_id)
    "da_attr_idx" btree (attribute_id)
Foreign-key constraints:
    "$1" FOREIGN KEY (doc_id) REFERENCES public.document(id)
    "$2" FOREIGN KEY (attribute_id) REFERENCES attribute(id)


dms3_test=> 

explain analyze SELECT doc.id FROM attribute as attr0, attribute_name
as an0, attribute_name as an2, document_attribute as da2, document as
doc, attribute_name as an1, attribute as attr3, document_attribute as
da1, attribute as attr2, document_attribute as da0, attribute_name as
an3, attribute as attr1, document_attribute as da3

WHERE 
da0.doc_id = doc.id AND attr0.id = da0.attribute_id AND an0.id = attr0.name_id AND 
da1.doc_id = doc.id AND attr1.id = da1.attribute_id AND an1.id = attr1.name_id AND 
da2.doc_id = doc.id AND attr2.id = da2.attribute_id AND an2.id = attr2.name_id AND 
da3.doc_id = doc.id AND attr3.id = da3.attribute_id AND an3.id = attr3.name_id AND 
an0.name = 'ssis_client' AND attr0.value = 'client1' AND
an1.name = 'ssis_group' AND attr1.value = 'group1' AND
an2.name = 'ssis_type' AND attr2.value = 'type1' AND
an3.name = 'ssis_subtype' AND attr3.value = 'subtype1'
;


                                                                                                                         QUERY PLAN                                                                                                                          
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=655695.94..886471.16 rows=1 width=4) (actual time=188571.542..217327.467 rows=3 loops=1)
   Join Filter: ("outer".id = "inner".name_id)
   ->  Seq Scan on attribute_name an0  (cost=0.00..1.07 rows=1 width=4) (actual time=0.045..0.048 rows=1 loops=1)
         Filter: (name = 'ssis_client'::text)
   ->  Nested Loop  (cost=655695.94..886470.07 rows=1 width=8) (actual time=188571.488..217327.404 rows=3 loops=1)
         Join Filter: ("outer".id = "inner".name_id)
         ->  Seq Scan on attribute_name an5  (cost=0.00..1.07 rows=1 width=4) (actual time=0.008..0.015 rows=1 loops=1)
               Filter: (name = 'ssis_e2xkey'::text)
         ->  Nested Loop  (cost=655695.94..886468.99 rows=1 width=12) (actual time=188571.475..217327.378 rows=3 loops=1)
               Join Filter: ("outer".id = "inner".name_id)
               ->  Seq Scan on attribute_name an4  (cost=0.00..1.07 rows=1 width=4) (actual time=0.007..0.009 rows=1 loops=1)
                     Filter: (name = 'ssis_comment'::text)
               ->  Nested Loop  (cost=655695.94..886467.90 rows=1 width=16) (actual time=188571.453..217327.346 rows=3 loops=1)
                     ->  Hash Join  (cost=655695.94..886463.56 rows=1 width=40) (actual time=183814.259..217326.874 rows=11 loops=1)
                           Hash Cond: ("outer".name_id = "inner".id)
                           ->  Hash Join  (cost=655694.86..886462.45 rows=4 width=44) (actual time=183814.220..217326.774 rows=11 loops=1)
                                 Hash Cond: (("outer".id = "inner".name_id) AND ("outer".attribute_id = "inner".id))
                                 ->  Hash Join  (cost=655692.89..886452.06 rows=838 width=52) (actual time=183795.378..217307.410 rows=951 loops=1)
                                       Hash Cond: ("outer".attribute_id = "inner".id)
                                       ->  Nested Loop  (cost=655690.92..886280.53 rows=32236 width=52) (actual time=183664.609..217269.300 rows=97785 loops=1)
                                             ->  Hash Join  (cost=655688.96..885633.84 rows=16118 width=44) (actual time=183640.064..217012.129 rows=97785 loops=1)
                                                   Hash Cond: ("outer".doc_id = "inner".id)
                                                   ->  Nested Loop  (cost=0.00..191997.58 rows=7557225 width=12) (actual time=12.250..10810.601 rows=7557225 loops=1)
                                                         ->  Index Scan using attribute_name_pkey on attribute_name an3  (cost=0.00..3.08 rows=1 width=4) (actual time=12.218..12.232 rows=1 loops=1)
                                                               Filter: (name = 'ssis_subtype'::text)
                                                         ->  Seq Scan on document_attribute da1  (cost=0.00..116422.25 rows=7557225 width=8) (actual time=0.021..4547.481 rows=7557225 loops=1)
                                                   ->  Hash  (cost=655683.57..655683.57 rows=2155 width=32) (actual time=183565.310..183565.310 rows=0 loops=1)
                                                         ->  Nested Loop  (cost=462162.26..655683.57 rows=2155 width=32) (actual time=128403.334..183556.998 rows=9257 loops=1)
                                                               ->  Hash Join  (cost=462162.26..650853.43 rows=288 width=24) (actual time=128403.319..183498.454 rows=906 loops=1)
                                                                     Hash Cond: ("outer".attribute_id = "inner".id)
                                                                     ->  Hash Join  (cost=462160.29..650793.18 rows=11080 width=24) (actual time=128337.287..183447.336 rows=90804 loops=1)
                                                                           Hash Cond: ("outer".name_id = "inner".id)
                                                                           ->  Nested Loop  (cost=462159.22..650348.93 rows=66476 width=28) (actual time=128337.257..183307.650 rows=90804 loops=1)
                                                                                 ->  Hash Join  (cost=462159.22..501285.43 rows=8888 width=20) (actual time=128306.517..132366.000 rows=8840 loops=1)
                                                                                       Hash Cond: ("outer".id = "inner".doc_id)
                                                                                       ->  Hash Join  (cost=1.06..25599.40 rows=202087 width=4) (actual time=41.568..2754.244 rows=329853 loops=1)
                                                                                             Hash Cond: ("outer".state_id = "inner".id)
                                                                                             ->  Seq Scan on document doc  (cost=0.00..18525.31 rows=1010431 width=8) (actual time=18.767..2089.253 rows=1010431 loops=1)
                                                                                             ->  Hash  (cost=1.06..1.06 rows=1 width=4) (actual time=14.681..14.681 rows=0 loops=1)
                                                                                                   ->  Seq Scan on state  (cost=0.00..1.06 rows=1 width=4) (actual time=0.031..0.035 rows=1 loops=1)
                                                                                                         Filter: (name = 'associated'::text)
                                                                                       ->  Hash  (cost=461808.06..461808.06 rows=44437 width=16) (actual time=128239.687..128239.687 rows=0 loops=1)
                                                                                             ->  Hash Join  (cost=157528.96..461808.06 rows=44437 width=16) (actual time=15479.239..128139.028 rows=27087 loops=1)
                                                                                                   Hash Cond: ("outer".attribute_id = "inner".id)
                                                                                                   ->  Hash Join  (cost=157526.99..452807.67 rows=1710811 width=16) (actual time=15478.512..127203.588 rows=2313438 loops=1)
                                                                                                         Hash Cond: ("outer".doc_id = "inner".doc_id)
                                                                                                         ->  Seq Scan on document_attribute da2  (cost=0.00..116422.25 rows=7557225 width=8) (actual time=0.019..37889.434 rows=7557225 loops=1)
                                                                                                         ->  Hash  (cost=156173.26..156173.26 rows=196292 width=8) (actual time=14908.286..14908.286 rows=0 loops=1)
                                                                                                               ->  Hash Join  (cost=1.97..156173.26 rows=196292 width=8) (actual time=7.750..14650.188 rows=269366 loops=1)
                                                                                                                     Hash Cond: ("outer".attribute_id = "inner".id)
                                                                                                                     ->  Seq Scan on document_attribute da4  (cost=0.00..116422.25 rows=7557225 width=8) (actual time=7.678..11635.892 rows=7557225 loops=1)
                                                                                                                     ->  Hash  (cost=1.96..1.96 rows=2 width=8) (actual time=0.049..0.049 rows=0 loops=1)
                                                                                                                           ->  Seq Scan on attribute attr4  (cost=0.00..1.96 rows=2 width=8) (actual time=0.008..0.047 rows=1 loops=1)
                                                                                                                                 Filter: (value = 'comment1'::text)
                                                                                                   ->  Hash  (cost=1.96..1.96 rows=2 width=8) (actual time=0.046..0.046 rows=0 loops=1)
                                                                                                         ->  Seq Scan on attribute attr2  (cost=0.00..1.96 rows=2 width=8) (actual time=0.007..0.044 rows=1 loops=1)
                                                                                                               Filter: (value = 'type1'::text)
                                                                                 ->  Index Scan using document_attribute_pkey on document_attribute da0  (cost=0.00..16.67 rows=8 width=8) (actual time=5.713..5.748 rows=10 loops=8840)
                                                                                       Index Cond: ("outer".doc_id = da0.doc_id)
                                                                           ->  Hash  (cost=1.07..1.07 rows=1 width=4) (actual time=0.011..0.011 rows=0 loops=1)
                                                                                 ->  Seq Scan on attribute_name an2  (cost=0.00..1.07 rows=1 width=4) (actual time=0.007..0.010 rows=1 loops=1)
                                                                                       Filter: (name = 'ssis_type'::text)
                                                                     ->  Hash  (cost=1.96..1.96 rows=2 width=8) (actual time=0.052..0.052 rows=0 loops=1)
                                                                           ->  Seq Scan on attribute attr0  (cost=0.00..1.96 rows=2 width=8) (actual time=0.014..0.050 rows=1 loops=1)
                                                                                 Filter: (value = 'client1'::text)
                                                               ->  Index Scan using document_attribute_pkey on document_attribute da3  (cost=0.00..16.67 rows=8 width=8) (actual time=0.005..0.049 rows=10 loops=906)
                                                                     Index Cond: (da3.doc_id = "outer".doc_id)
                                             ->  Materialize  (cost=1.96..1.98 rows=2 width=8) (actual time=0.000..0.001 rows=1 loops=97785)
                                                   ->  Seq Scan on attribute attr5  (cost=0.00..1.96 rows=2 width=8) (actual time=18.498..18.537 rows=1 loops=1)
                                                         Filter: (value = 'e2xkey1'::text)
                                       ->  Hash  (cost=1.96..1.96 rows=2 width=8) (actual time=0.045..0.045 rows=0 loops=1)
                                             ->  Seq Scan on attribute attr1  (cost=0.00..1.96 rows=2 width=8) (actual time=0.007..0.044 rows=1 loops=1)
                                                   Filter: (value = 'group1'::text)
                                 ->  Hash  (cost=1.96..1.96 rows=2 width=8) (actual time=18.781..18.781 rows=0 loops=1)
                                       ->  Seq Scan on attribute attr3  (cost=0.00..1.96 rows=2 width=8) (actual time=18.739..18.779 rows=1 loops=1)
                                             Filter: (value = 'subtype1'::text)
                           ->  Hash  (cost=1.07..1.07 rows=1 width=4) (actual time=0.018..0.018 rows=0 loops=1)
                                 ->  Seq Scan on attribute_name an1  (cost=0.00..1.07 rows=1 width=4) (actual time=0.007..0.009 rows=1 loops=1)
                                       Filter: (name = 'ssis_group'::text)
                     ->  Index Scan using document_attribute_pkey on document_attribute da5  (cost=0.00..4.33 rows=1 width=8) (actual time=0.037..0.037 rows=0 loops=11)
                           Index Cond: ((da5.doc_id = "outer".doc_id) AND ("outer".id = da5.attribute_id))
 Total runtime: 217405.692 ms
(82 rows)

Time: 217885.006 ms

The same data but in a schema without trimmed-down surrogate keys.

-- Done on postgresql 8.1

dms3_test=> \d document
                                         Table "dms4.document"
    Column     |           Type           |                          Modifiers                          
---------------+--------------------------+-------------------------------------------------------------
 id            | integer                  | not null default nextval('document_id_seq'::regclass)
 state         | text                     | not null
 modified_who  | text                     | not null
 modified_when | timestamp with time zone | not null default ('now'::text)::timestamp(6) with time zone
 created_who   | text                     | not null
 created_when  | timestamp with time zone | not null default ('now'::text)::timestamp(6) with time zone
Indexes:
    "document_pkey" PRIMARY KEY, btree (id)
    "document_created_when" btree (created_when)
    "document_created_who" btree (created_who)
    "document_modified_when" btree (modified_when)
    "document_modified_who" btree (modified_who)
    "document_state" btree (state)
Foreign-key constraints:
    "document_created_who_fkey" FOREIGN KEY (created_who) REFERENCES who(name)
    "document_modified_who_fkey" FOREIGN KEY (modified_who) REFERENCES who(name)
    "document_state_fkey" FOREIGN KEY (state) REFERENCES state(name)

dms3_test=> \d temp20051206.da
   Table "temp20051206.da"
 Column |  Type   | Modifiers 
--------+---------+-----------
 doc_id | integer | not null
 an     | text    | not null
 av     | text    | not null
Indexes:
    "da_pkey" PRIMARY KEY, btree (doc_id, an, av)
    "da_an_av_idx" UNIQUE, btree (an, av, doc_id)
Foreign-key constraints:
    "da_an_fkey" FOREIGN KEY (an, av) REFERENCES attr(name, value) DEFERRABLE INITIALLY DEFERRED
    "da_doc_id_fkey" FOREIGN KEY (doc_id) REFERENCES public.document(id) DEFERRABLE INITIALLY DEFERRED

dms3_test=> 

explain analyze select doc.id from document as doc, da
da_client, da da_group, da da_type, da da_subtype 

WHERE
doc.id=da_client.doc_id and doc.id=da_group.doc_id and
doc.id=da_type.doc_id and doc.id=da_subtype.doc_id and
da_client.an='ssis_client' and da_client.av='client1' and 
da_group.an='ssis_group' and da_group.av='group1' and
da_type.an='ssis_type' and da_type.av='type1' and 
da_subtype.an='ssis_subtype' and da_subtype.av='subtype1'
;

                                                                             QUERY PLAN                                                                             
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=40335.69..53871.76 rows=1 width=4) (actual time=17319.458..50292.429 rows=140 loops=1)
   ->  Nested Loop  (cost=40335.69..53864.64 rows=2 width=16) (actual time=17319.392..50260.780 rows=1072 loops=1)
         ->  Nested Loop  (cost=40335.69..53330.49 rows=150 width=12) (actual time=17289.476..35508.467 rows=10153 loops=1)
               ->  Merge Join  (cost=40335.69..40494.44 rows=3558 width=8) (actual time=17263.290..17594.400 rows=10153 loops=1)
                     Merge Cond: ("outer".doc_id = "inner".doc_id)
                     ->  Sort  (cost=20817.14..20849.19 rows=12818 width=4) (actual time=10145.947..10314.729 rows=101159 loops=1)
                           Sort Key: da_client.doc_id
                           ->  Bitmap Heap Scan on da da_client  (cost=155.91..19942.58 rows=12818 width=4) (actual time=1165.917..9800.025 rows=101159 loops=1)
                                 Recheck Cond: ((an = 'ssis_client'::text) AND (av = 'client1'::text))
                                 ->  Bitmap Index Scan on da_an_av_idx  (cost=0.00..155.91 rows=12818 width=0) (actual time=1156.362..1156.362 rows=101159 loops=1)
                                       Index Cond: ((an = 'ssis_client'::text) AND (av = 'client1'::text))
                     ->  Sort  (cost=19518.54..19548.09 rows=11817 width=4) (actual time=7117.330..7188.340 rows=101190 loops=1)
                           Sort Key: da_subtype.doc_id
                           ->  Bitmap Heap Scan on da da_subtype  (cost=143.90..18719.21 rows=11817 width=4) (actual time=913.707..6798.627 rows=101190 loops=1)
                                 Recheck Cond: ((an = 'ssis_subtype'::text) AND (av = 'subtype1'::text))
                                 ->  Bitmap Index Scan on da_an_av_idx  (cost=0.00..143.90 rows=11817 width=0) (actual time=904.720..904.720 rows=101190 loops=1)
                                       Index Cond: ((an = 'ssis_subtype'::text) AND (av = 'subtype1'::text))
               ->  Index Scan using document_pkey on document doc  (cost=0.00..3.60 rows=1 width=4) (actual time=1.762..1.763 rows=1 loops=10153)
                     Index Cond: (doc.id = "outer".doc_id)
         ->  Index Scan using da_pkey on da da_type  (cost=0.00..3.55 rows=1 width=4) (actual time=1.451..1.452 rows=0 loops=10153)
               Index Cond: (("outer".id = da_type.doc_id) AND (da_type.an = 'ssis_type'::text) AND (da_type.av = 'type1'::text))
   ->  Index Scan using da_pkey on da da_group  (cost=0.00..3.55 rows=1 width=4) (actual time=0.028..0.028 rows=0 loops=1072)
         Index Cond: (("outer".id = da_group.doc_id) AND (da_group.an = 'ssis_group'::text) AND (da_group.av = 'group1'::text))
 Total runtime: 50296.288 ms
(24 rows)

Time: 50301.853 ms

(originally from http://microjet.ath.cx/WebWiki/2005.12.11_PreferringNaturalToSurrogateKey.html)

Table partitioning

Authentication

Login with:New JS-Kit AccountMy Google ProfileMy Twitter AccountMy FriendFeed AccountMy Yahoo! AccountMy Blogger AccountMy JS-Kit AccountMy Haloscan AccountMy OpenID

Postgresql could benefit from an implementation of table partitioning. Also see: http://groups.google.com/group/pgsql.general/tree/browse_frm/thread/e72ead84aa16bc8e/64d61f78425b119b?rnum=1&q=partition&_done=%2Fgroup%2Fpgsql.general%2Fbrowse_frm%2Fthread%2Fe72ead84aa16bc8e%2F121bab4de037ce6a%3Fq%3Dpartition%26rnum%3D7%26#doc_64d61f78425b119b

All in one table

dms3_test=> select count(doc.id) from document as doc, da da_client, da
da_group, da da_type, da da_subtype where doc.id=da_client.doc_id and
doc.id=da_group.doc_id and doc.id=da_type.doc_id and
doc.id=da_subtype.doc_id and da_client.an='ssis_client' and
da_group.an='ssis_group' and da_type.an='ssis_type' and
da_subtype.an='ssis_subtype' and da_client.av='client1' and
da_group.av='group1' and da_type.av='type1' and da_subtype.av='subtype1';

 count 
-------
   140
(1 row)

Time: 60882.964 ms

Separated out

dms3_test=> select count(doc.id) from document as doc, ssis_client as sc,
ssis_group as sg, ssis_type as st, ssis_subtype as sst where
doc.id=sc.doc_id and doc.id=sg.doc_id and doc.id=st.doc_id and
doc.id=sst.doc_id and sc.value='client1' and sg.value='group1' and
st.value='type1' and sst.value='subtype1';

 count 
-------
   140
(1 row)

Time: 3912.358 ms

Explain analyze of all in one table

dms3_test=> explain analyze select doc.id from document as doc, da
da_client, da da_group, da da_type, da da_subtype where
doc.id=da_client.doc_id and doc.id=da_group.doc_id and
doc.id=da_type.doc_id and doc.id=da_subtype.doc_id and
da_client.an='ssis_client' and da_group.an='ssis_group' and
da_type.an='ssis_type' and da_subtype.an='ssis_subtype' and
da_client.av='client1' and da_group.av='group1' and da_type.av='type1' and
da_subtype.av='subtype1'

                                                                             QUERY PLAN                                                                             
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=40335.69..53871.76 rows=1 width=4) (actual time=17319.458..50292.429 rows=140 loops=1)
   ->  Nested Loop  (cost=40335.69..53864.64 rows=2 width=16) (actual time=17319.392..50260.780 rows=1072 loops=1)
         ->  Nested Loop  (cost=40335.69..53330.49 rows=150 width=12) (actual time=17289.476..35508.467 rows=10153 loops=1)
               ->  Merge Join  (cost=40335.69..40494.44 rows=3558 width=8) (actual time=17263.290..17594.400 rows=10153 loops=1)
                     Merge Cond: ("outer".doc_id = "inner".doc_id)
                     ->  Sort  (cost=20817.14..20849.19 rows=12818 width=4) (actual time=10145.947..10314.729 rows=101159 loops=1)
                           Sort Key: da_client.doc_id
                           ->  Bitmap Heap Scan on da da_client  (cost=155.91..19942.58 rows=12818 width=4) (actual time=1165.917..9800.025 rows=101159 loops=1)
                                 Recheck Cond: ((an = 'ssis_client'::text) AND (av = 'client1'::text))
                                 ->  Bitmap Index Scan on da_an_av_idx  (cost=0.00..155.91 rows=12818 width=0) (actual time=1156.362..1156.362 rows=101159 loops=1)
                                       Index Cond: ((an = 'ssis_client'::text) AND (av = 'client1'::text))
                     ->  Sort  (cost=19518.54..19548.09 rows=11817 width=4) (actual time=7117.330..7188.340 rows=101190 loops=1)
                           Sort Key: da_subtype.doc_id
                           ->  Bitmap Heap Scan on da da_subtype  (cost=143.90..18719.21 rows=11817 width=4) (actual time=913.707..6798.627 rows=101190 loops=1)
                                 Recheck Cond: ((an = 'ssis_subtype'::text) AND (av = 'subtype1'::text))
                                 ->  Bitmap Index Scan on da_an_av_idx  (cost=0.00..143.90 rows=11817 width=0) (actual time=904.720..904.720 rows=101190 loops=1)
                                       Index Cond: ((an = 'ssis_subtype'::text) AND (av = 'subtype1'::text))
               ->  Index Scan using document_pkey on document doc  (cost=0.00..3.60 rows=1 width=4) (actual time=1.762..1.763 rows=1 loops=10153)
                     Index Cond: (doc.id = "outer".doc_id)
         ->  Index Scan using da_pkey on da da_type  (cost=0.00..3.55 rows=1 width=4) (actual time=1.451..1.452 rows=0 loops=10153)
               Index Cond: (("outer".id = da_type.doc_id) AND (da_type.an = 'ssis_type'::text) AND (da_type.av = 'type1'::text))
   ->  Index Scan using da_pkey on da da_group  (cost=0.00..3.55 rows=1 width=4) (actual time=0.028..0.028 rows=0 loops=1072)
         Index Cond: (("outer".id = da_group.doc_id) AND (da_group.an = 'ssis_group'::text) AND (da_group.av = 'group1'::text))
 Total runtime: 50296.288 ms
(24 rows)

Time: 50301.853 ms

Explain analyze of separated out

dms3_test=> explain analyze select doc.id from document as doc, ssis_client
as sc, ssis_group as sg, ssis_type as st, ssis_subtype as sst where
doc.id=sc.doc_id and doc.id=sg.doc_id and doc.id=st.doc_id and
doc.id=sst.doc_id and sc.value='client1' and sg.value='group1' and
st.value='type1' and sst.value='subtype1';

                                                                           QUERY PLAN                                                                           
----------------------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=48763.53..76529.21 rows=108 width=4) (actual time=3947.647..5401.517 rows=140 loops=1)
   ->  Nested Loop  (cost=48763.53..76139.59 rows=108 width=16) (actual time=3947.592..5377.496 rows=140 loops=1)
         ->  Hash Join  (cost=48763.53..71836.53 rows=1019 width=12) (actual time=3947.454..5027.993 rows=993 loops=1)
               Hash Cond: ("outer".doc_id = "inner".doc_id)
               ->  Seq Scan on ssis_group sg  (cost=0.00..22537.39 rows=105085 width=4) (actual time=169.102..1161.228 rows=100924 loops=1)
                     Filter: (value = 'group1'::text)
               ->  Hash  (cost=48739.02..48739.02 rows=9802 width=8) (actual time=3777.630..3777.630 rows=10153 loops=1)
                     ->  Hash Join  (cost=23168.26..48739.02 rows=9802 width=8) (actual time=2108.108..3770.001 rows=10153 loops=1)
                           Hash Cond: ("outer".doc_id = "inner".doc_id)
                           ->  Seq Scan on ssis_client sc  (cost=0.00..22537.39 rows=100706 width=4) (actual time=201.259..1662.239 rows=101159 loops=1)
                                 Filter: (value = 'client1'::text)
                           ->  Hash  (cost=22537.39..22537.39 rows=98349 width=4) (actual time=1904.210..1904.210 rows=101190 loops=1)
                                 ->  Seq Scan on ssis_subtype sst  (cost=0.00..22537.39 rows=98349 width=4) (actual time=234.704..1828.887 rows=101190 loops=1)
                                       Filter: (value = 'subtype1'::text)
         ->  Index Scan using ssis_type_pkey on ssis_type st  (cost=0.00..4.21 rows=1 width=4) (actual time=0.351..0.351 rows=0 loops=993)
               Index Cond: ("outer".doc_id = st.doc_id)
               Filter: (value = 'type1'::text)
   ->  Index Scan using document_pkey on document doc  (cost=0.00..3.60 rows=1 width=4) (actual time=0.169..0.169 rows=1 loops=140)
         Index Cond: (doc.id = "outer".doc_id)
 Total runtime: 5401.958 ms
(20 rows)

Time: 5406.568 ms 

(originally from http://microjet.ath.cx/WebWiki/2005.12.11_TablePartitioning.html)

Implementing application-level timeout

Authentication

Login with:New JS-Kit AccountMy Google ProfileMy Twitter AccountMy FriendFeed AccountMy Yahoo! AccountMy Blogger AccountMy JS-Kit AccountMy Haloscan AccountMy OpenID

I was tasked to fix an app that had been in production for two years. The app was having trouble communicating with a server of a new customer. At times, it would just stuck in read() call even though it was supposed to have timed out in 2 minutes.
So I took a look at the source:

public void createConnection()
  {
    socket = Socket.new(/*....*/);
    s.setSocketTimeout(TWO_MINUTES);
    output = socket.getOutputStream();
    input = socket.getInputStream();
  }

  public void sendPing(Socket s) 
  {
    output.write(PING_MESSAGE);
    /* ... */
    input.read();
    /* ... */
  }

This is the wrong way to implement application-level timeout. For, you see, it turned out this particular server was sending a TCP Keep Alive packet every 1 minutes 15 seconds. I have no idea why they did that (the default value should be around 2 hours), but they did anyway, and they were a valuable customer.
Telling the customer, 'you are incapable of configuring server' just wouldn't do, and it was also not totally their fault.


Our fault was in using socket's timeout for application-level timeout. Java's Socket#setSocketTimeout method corresponds to setting SO_RCVTIMEO and SO_SNDTIMEO socket options in BSD Socket API.
Each packet received, whether it contains application level data or not, reset the time out timer. Those Keep Alive packets were preventing the timeout timer from reaching the two minutes mark.

The easiest solution to this problem was to create a timer service. Each time you want to do a socket operation, you register to the timer service and unregister afterward.

import javautils.fun.VoidToVoid;


public class TimerService extends Thread
{
  /* a singleton */
  public synchronized TimerService getInstance() { /* ... */ }

  public void run()
  {
    while (true) {
     mutex.acquire();
     try {
       interruptTimedOutThread();
     } finally {
       mutex.release();
     }
     sleep(ONE_SECOND);
    }
  }

  public void timeout(int timeout_millisecond, VoidToVoid func)
  {
    try {
      register(Thread.current, timeout_millisecond);
      try {
        func.call();
      } finally {
        unregister(Thread.current);      
      }
    /* 
       Convert exceptions caused by interruption outside
       of the register-unregister block because we don't want
       exception handling to be interrupted
    */
    } catch (ClosedByInterruptException e) {
      throw new TimedOutException("timed out", e);
    } catch (InterruptException e) {
      throw new TimedOutException("timed out", e);
    }
  }
}

public class ConnectionToServer 
{
  public void sendPing(Socket s)
  {
    TimerService timer = TimerService.getInstance();
    try {
      timer.timeout(TWO_SECONDS, new VoidToVoid() {
        public void with() 
        {
          output.write(PING_MESSAGE);
          /* ... */
          input.read();
          /* ... */
        }});
    } catch (TimedOutException e) {
      /* ... */
    }
  }
} 

(originally from http://microjet.ath.cx/WebWiki/2005.12.09_Implementing_Application-Level_Timeout.html)

Authentication

Login with:New JS-Kit AccountMy Google ProfileMy Twitter AccountMy FriendFeed AccountMy Yahoo! AccountMy Blogger AccountMy JS-Kit AccountMy Haloscan AccountMy OpenID

2005.12.11_Index Clustering

Index clustering can improve your query time, if your query can take advantage of the ordering.
Following are the queries from 2005.12.11_TablePartitioning.html redone with index clustering.

The all in one table. A 10x improvement.

dms3_test=> \d da
   Table "temp20051206.da"
 Column |  Type   | Modifiers 
--------+---------+-----------
 doc_id | integer | not null
 an     | text    | not null
 av     | text    | not null
Indexes:
    "da_pkey" PRIMARY KEY, btree (doc_id, an, av)
    "da_an_av_idx" UNIQUE, btree (an, av, doc_id) CLUSTER
Foreign-key constraints:
    "da_an_fkey" FOREIGN KEY (an, av) REFERENCES attr(name, value) DEFERRABLE INITIALLY DEFERRED
    "da_doc_id_fkey" FOREIGN KEY (doc_id) REFERENCES public.document(id) DEFERRABLE INITIALLY DEFERRED



dms3_test=> explain analyze select doc.id from document as doc, da
da_client, da da_group, da da_type, da da_subtype where
doc.id=da_client.doc_id and doc.id=da_group.doc_id and
doc.id=da_type.doc_id and doc.id=da_subtype.doc_id and
da_client.an='ssis_client' and da_group.an='ssis_group' and
da_type.an='ssis_type' and da_subtype.an='ssis_subtype' and
da_client.av='client1' and da_group.av='group1' and da_type.av='type1'
and da_subtype.av='subtype1';
                                                                            QUERY PLAN                                                                            
------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=40335.69..53871.76 rows=1 width=4) (actual time=1904.361..5277.128 rows=140 loops=1)
   ->  Nested Loop  (cost=40335.69..53864.64 rows=2 width=16) (actual time=1904.289..5221.572 rows=1072 loops=1)
         ->  Nested Loop  (cost=40335.69..53330.49 rows=150 width=12) (actual time=1904.216..3747.333 rows=10153 loops=1)
               ->  Merge Join  (cost=40335.69..40494.44 rows=3558 width=8) (actual time=1882.068..2082.534 rows=10153 loops=1)
                     Merge Cond: ("outer".doc_id = "inner".doc_id)
                     ->  Sort  (cost=20817.14..20849.19 rows=12818 width=4) (actual time=778.661..835.451 rows=101159 loops=1)
                           Sort Key: da_client.doc_id
                           ->  Bitmap Heap Scan on da da_client  (cost=155.91..19942.58 rows=12818 width=4) (actual time=432.318..521.484 rows=101159 loops=1)
                                 Recheck Cond: ((an = 'ssis_client'::text) AND (av = 'client1'::text))
                                 ->  Bitmap Index Scan on da_an_av_idx  (cost=0.00..155.91 rows=12818 width=0) (actual time=418.064..418.064 rows=101159 loops=1)
                                       Index Cond: ((an = 'ssis_client'::text) AND (av = 'client1'::text))
                     ->  Sort  (cost=19518.54..19548.09 rows=11817 width=4) (actual time=1103.395..1160.311 rows=101190 loops=1)
                           Sort Key: da_subtype.doc_id
                           ->  Bitmap Heap Scan on da da_subtype  (cost=143.90..18719.21 rows=11817 width=4) (actual time=633.951..751.246 rows=101190 loops=1)
                                 Recheck Cond: ((an = 'ssis_subtype'::text) AND (av = 'subtype1'::text))
                                 ->  Bitmap Index Scan on da_an_av_idx  (cost=0.00..143.90 rows=11817 width=0) (actual time=633.700..633.700 rows=101190 loops=1)
                                       Index Cond: ((an = 'ssis_subtype'::text) AND (av = 'subtype1'::text))
               ->  Index Scan using document_pkey on document doc  (cost=0.00..3.60 rows=1 width=4) (actual time=0.162..0.163 rows=1 loops=10153)
                     Index Cond: (doc.id = "outer".doc_id)
         ->  Index Scan using da_pkey on da da_type  (cost=0.00..3.55 rows=1 width=4) (actual time=0.144..0.144 rows=0 loops=10153)
               Index Cond: (("outer".id = da_type.doc_id) AND (da_type.an = 'ssis_type'::text) AND (da_type.av = 'type1'::text))
   ->  Index Scan using da_pkey on da da_group  (cost=0.00..3.55 rows=1 width=4) (actual time=0.050..0.050 rows=0 loops=1072)
         Index Cond: (("outer".id = da_group.doc_id) AND (da_group.an = 'ssis_group'::text) AND (da_group.av = 'group1'::text))
 Total runtime: 5280.891 ms
(24 rows)

Time: 5287.639 ms

The separated out data. About 2x improvement.

dms3_test=> \d ssis_client
                                        Table "attr.ssis_client"
    Column     |           Type           |                          Modifiers                          
---------------+--------------------------+-------------------------------------------------------------
 doc_id        | integer                  | not null
 created_when  | timestamp with time zone | not null default ('now'::text)::timestamp(6) with time zone
 created_who   | integer                  | not null
 modified_when | timestamp with time zone | not null default ('now'::text)::timestamp(6) with time zone
v modified_who  | integer                  | not null
 value         | text                     | not null
 value_id      | integer                  | not null
Indexes:
    "ssis_client_pkey" PRIMARY KEY, btree (doc_id)
    "ssis_client_value_id_idx" btree (value_id)
    "ssis_client_value_idx" btree (value) CLUSTER
Foreign-key constraints:
    "ssis_client_created_who_fkey" FOREIGN KEY (created_who) REFERENCES public.who(id)
    "ssis_client_doc_id_fkey" FOREIGN KEY (doc_id) REFERENCES public.document(id)
    "ssis_client_modified_who_fkey" FOREIGN KEY (modified_who) REFERENCES public.who(id)
    "ssis_client_value_id_fkey" FOREIGN KEY (value_id) REFERENCES ssis_client_value(id)

dms3_test=> explain analyze select doc.id from document as doc,
ssis_client as sc, ssis_group as sg, ssis_type as st, ssis_subtype as
sst where doc.id=sc.doc_id and doc.id=sg.doc_id and doc.id=st.doc_id
and doc.id=sst.doc_id and sc.value='client1' and sg.value='group1' and
st.value='type1' and sst.value='subtype1';

                                                                                            QUERY PLAN                                                                                            
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=12322.80..16099.97 rows=108 width=4) (actual time=1941.188..2329.004 rows=140 loops=1)
   ->  Hash Join  (cost=12322.80..15710.34 rows=108 width=16) (actual time=1941.144..2306.762 rows=140 loops=1)
         Hash Cond: ("outer".doc_id = "inner".doc_id)
         ->  Index Scan using ssis_type_value_idx on ssis_type st  (cost=0.00..2850.93 rows=107106 width=4) (actual time=75.017..406.128 rows=100825 loops=1)
               Index Cond: (value = 'type1'::text)
         ->  Hash  (cost=12320.26..12320.26 rows=1019 width=12) (actual time=1862.846..1862.846 rows=993 loops=1)
               ->  Hash Join  (cost=8986.99..12320.26 rows=1019 width=12) (actual time=1531.920..1861.824 rows=993 loops=1)
                     Hash Cond: ("outer".doc_id = "inner".doc_id)
                     ->  Index Scan using ssis_group_value_idx on ssis_group sg  (cost=0.00..2797.65 rows=105085 width=4) (actual time=39.136..291.236 rows=100924 loops=1)
                           Index Cond: (value = 'group1'::text)
                     ->  Hash  (cost=8962.49..8962.49 rows=9802 width=8) (actual time=1481.859..1481.859 rows=10153 loops=1)
                           ->  Hash Join  (cost=3248.58..8962.49 rows=9802 width=8) (actual time=981.952..1474.601 rows=10153 loops=1)
                                 Hash Cond: ("outer".doc_id = "inner".doc_id)
                                 ->  Index Scan using ssis_client_value_idx on ssis_client sc  (cost=0.00..2680.53 rows=100706 width=4) (actual time=43.766..317.779 rows=101159 loops=1)
                                       Index Cond: (value = 'client1'::text)
                                 ->  Hash  (cost=2617.71..2617.71 rows=98349 width=4) (actual time=918.689..918.689 rows=101190 loops=1)
                                       ->  Index Scan using ssis_subtype_value_idx on ssis_subtype sst  (cost=0.00..2617.71 rows=98349 width=4) (actual time=53.700..820.030 rows=101190 loops=1)
                                             Index Cond: (value = 'subtype1'::text)
   ->  Index Scan using document_pkey on document doc  (cost=0.00..3.60 rows=1 width=4) (actual time=0.156..0.156 rows=1 loops=140)
         Index Cond: (doc.id = "outer".doc_id)
 Total runtime: 2329.395 ms
(21 rows)

Time: 2334.097 ms 

(originally from http://microjet.ath.cx/WebWiki/2005.12.11_IndexClustering.html)

Connection from ruby to MS SQL Server

Authentication

Login with:New JS-Kit AccountMy Google ProfileMy Twitter AccountMy FriendFeed AccountMy Yahoo! AccountMy Blogger AccountMy JS-Kit AccountMy Haloscan AccountMy OpenID

Quick setup guide for: debian, iodbc, ruby, mssql2k

apt-get install libdbi-ruby libdbd-odbc-ruby freetds-dev odbcinst1 iodbc

Installing freetds-dev and odbcinst1 should cause apt-get to offer you a choice of having freetds managed by odbcinst. Say yes. That will create a file /etc/odbcinst.ini

ysantoso@helen:~$ cat /etc/odbcinst.ini
[FreeTDS]
Description     = TDS driver (Sybase/MS SQL)
Driver          = /usr/lib/odbc/libtdsodbc.so
Setup           = /usr/lib/odbc/libtdsS.so
CPTimeout       =
CPReuse         =
FileUsage       = 1

Next thing to do is to setup ~/.freetds.conf. I started with the template at /etc/freetds/freetds.conf.

ysantoso@helen:~$ cat ~/.freetds.conf
[global]
        # Default TDS protocol version. 
        tds version = 4.2

        initial block size = 512

        swap broken dates = no

        swap broken money = no

        # Database server login method, if both server and domain
        # logins are enabled, domain login is tried first if a domain
        # is specified, and if that fails the server login will be
        # used.
        try server login = yes
        try domain login = no

        # Whether to write a TDSDUMP file for diagnostic purposes
        # (setting this to /tmp is insecure on a multi-user system)
;       dump file = /tmp/freetds.log
;       debug level = 10

        # If you get out of memory errors, it may mean that your
          client
        # is trying to allocate a huge buffer for a TEXT field.
        # (Microsoft servers sometimes pretend TEXT columns are
        # 4 GB wide!)   If you have this problem, try setting
        # 'text size' to a more reasonable limit
        text size = 64512


[FooServer]
host            =       fooserver.example.com
port            =       1433
tds version     =       7.0

Then we setup ~/.odbc.ini

ysantoso@helen:~$ cat ~/.odbc.ini
[ODBC Data Sources]
FooDSN = description about FooDSN

[FooDSN]
Driver          = /usr/lib/odbc/libtdsodbc.so
ServerName      = FooServer
Database        = Bar

Next, we test:

ysantoso@helen:~$ iodbctest
iODBC Demonstration program
This program shows an interactive SQL processor
Driver Manager: 03.52.0205.0204

Enter ODBC connect string (? shows list): ?

DSN                              | Driver
------------------------------------------------------------------------------
FooDSN                           | FooDSN

Enter ODBC connect string (? shows list):
DSN=FooDSN;UID=sa;PWD=lookmanopassword

SQL>select * from tablebaz;
.
.
.
.

Alright, ODBC is setup. Let's try connecting from Ruby. There are two ways: one is to use the ODBC driver directly or using DBI.

I am not familiar with the ODBC driver's API. Looks similar to DBI, but I'm sure it differs in places. So, I just did a quick trial at it just to ensure that the DSN is seen.

irb(main):002:0> require 'odbc'
true
irb(main):005:0> ODBC.datasources
[#]

irb(main):006:0> require 'dbi'
true
irb(main):008:0> dbh=DBI.connect('dbi:ODBC:FooDSN', 'sa', 'lookmanopassword')
#, @attr={}>, @trace_output=#, @trace_mode=\ 2>
irb(main):015:0> dbh.select_one('select count(*) from websession')
[2495950] 

(originally from http://microjet.ath.cx/WebWiki/2005.11.03_Connecting_From_Ruby_To_MSSQL.html)