Search

OakieTags

Who's online

There are currently 0 users and 27 guests online.

Recent comments

Oakies Blog Aggregator

Presentations now downloadable

Every now and then I am asked about the availability of the presentations I have delivered. Recently somebody asked about a presentation I delivered at the OUG Scotland about multiblock reads, and I promised to make it available. I’ve now uploaded a PDF version of all my old presentations them and put them in the ‘Whitepapers and presentation’ section.

Enjoy!

OTN Tour of Latin America…

All the flights and hotels are booked, so it now feels very real. In a little over a week I will be taking part in the OTN Tour of Latin America.

I’m a little nervous because there are so many legs in such a short time. The tour lasts 13 days. In that time I’ll be taking 11 flights and visiting 6 locations.

  • Colombia
  • Ecuador
  • Trinidad & Tobago
  • Guatemala
  • Honduras
  • Costa Rica

I feel my stomach twisting as I look at the list. With so many locations in such a short time, the possibility of hiccups in transit seems rather high. Miss one connection and things get tricky…

I’m looking forward to meeting people, but I would be a liar if I said I’m happy about spending 2 weeks on a plane. :)

Cheers

Tim…


OTN Tour of Latin America… was first posted on June 22, 2012 at 7:43 am.
©2012 "The ORACLE-BASE Blog". Use of this feed is for personal non-commercial use only. If you are not reading this article in your feed reader, then the site is guilty of copyright infringement.




VirtualBox 4.1.18 Released…

VirtualBox 4.1.18 has been released. It’s a maintenance release and the downloads and changelogs are in the normal places.

It’s been about 2 years since I switched across to VirtualBox (when the shared virtual disks feature was introduced). In that time there have been loads of updates to the product. In the same time frame, VMware Server has had zero releases. I still get a lot of people writing to me about issues with VMware Server installations. I immediately tell them to ditch it. :)

Cheers

Tim…

PS. I’ve got nothing against VMware’s paid-for offerings, which do get updates. I just don’t see the point in using them when VirtualBox is free and works great for me.


VirtualBox 4.1.18 Released… was first posted on June 21, 2012 at 7:51 am.
©2012 "The ORACLE-BASE Blog". Use of this feed is for personal non-commercial use only. If you are not reading this article in your feed reader, then the site is guilty of copyright infringement.




Why is a Full Table Scan Selected – Will the Execution Plan Provide a Clue?

June 20, 2012 I have not had much time to respond in OTN threads recently, although I do still occasionally read threads on the forum.  I was a little surprised by one of the late responses in one of the recent threads, where one of the responders suggested actually testing the problem with the assistance of [...]

Little things worth knowing-static and dynamic listener registration

As part of  a recent project to remove a vulnerability in relation to CVE-2012-1675 it became apparent that there are certain misconceptions around dynamic and static listener registration which are hard to get rid of. The below is applicable for single instance Oracle only!

Now let’s start with a quiz: what does the following output imply:

$ lsnrctl status

LSNRCTL for Linux: Version 11.2.0.2.0 - Production on 20-JUN-2012 11:22:01

Copyright (c) 1991, 2010, Oracle.  All rights reserved.

Connecting to (ADDRESS=(PROTOCOL=tcp)(HOST=server1)(PORT=1571))
STATUS of the LISTENER
------------------------
Alias                     LISTENER
Version                   TNSLSNR for Linux: Version 11.2.0.2.0 - Production
Start Date                15-JUN-2012 11:14:27
Uptime                    5 days 0 hr. 7 min. 34 sec
Trace Level               off
Security                  ON: Local OS Authentication
SNMP                      OFF
Listener Parameter File   /u01/app/oracle/product/11.2/dbhome_1/network/admin/listener.ora
Listener Log File         /u01/app/oracle/diag/tnslsnr/server1/listener/alert/log.xml
Listening Endpoints Summary...
  (DESCRIPTION=(ADDRESS=(PROTOCOL=tcp)(HOST=server1)(PORT=1571)))
  (DESCRIPTION=(ADDRESS=(PROTOCOL=ipc)(KEY=EXTPROC1571)))
Services Summary...
Service "ORA11202" has 1 instance(s).
  Instance "ORA11202", status UNKNOWN, has 1 handler(s) for this service...
The command completed successfully

Yes, that’s right: the UNKNOWN means that there is no dynamic registration.

How does the listener register with the database?

If memory serves me right then Oracle introduced dynamic listener registration with 9i. This is the reason why there is no listener.ora file required in your $ORACLE_HOME/network/admin/ directory anymore. Simply start the listener and it will use the defaults, binding to port 1521. Of course, every attacker knows about that port number.

Any running database will try to register with the listener on port 1521-completely automatically. If the listener is instructed to start with a different port though, then there won’t be dynamic registration. That is, unless you set the local_listener parameter for a non-Oracle Restart/RAC environment where this is done for you by a HAS/CRS agent.

However, you technically don’t need to allow the database to register with the listener in single instance environments. As in the days before dynamic registration, you can statically register database services with the listener. Even today that is required for any process that cycles the database. As soon as the database is down, any dynamically registered service is removed from the listener. Examples for such processes are the data guard broker controlled switchover operation as well as RMAN duplication from active database. I’m sure there are others too but those are the two that come to mind.

The different methods to configure your listener.ora file

The most basic way to configure the listener is not to configure it at all. Change to $ORACLE_HOME/network/admin and move the listener.ore file out of the way. Then start the listener. However that’s not really recommended-as you will see on many posts on the web the fix to prevent illicit listener registration with a database is to enable the Class of Secure Transport (“COST”). This isn’t part of the defaults. Also, you might want to rethink the listener binding to port 1521. So let’s discard that idea for anything outside your own laptop play area.

A better way is to create a basic listener.ora file, either manually or via netca/netmgr. It will most likely look similar to this one:

LISTENER =
  (ADDRESS_LIST=
        (ADDRESS=(PROTOCOL=tcp)(HOST=server1)(PORT=1571))
        (ADDRESS=(PROTOCOL=ipc)(KEY=EXTPROC1571))
  )

This basic variant now has to be amended with the SECURE_REGISTER_LISTENER parameter (at least). Please refer to My Oracle Support for more information about this parameter and the values it can take.

With the above listener configuration file the listener was instructed to listen on IPC, and the client-facing Ethernet card on port 1571. Now let’s see what effect that has:

$ lsnrctl start listener
...
Listening on: (DESCRIPTION=(ADDRESS=(PROTOCOL=tcp)(HOST=server1)(PORT=1571)))
Listening on: (DESCRIPTION=(ADDRESS=(PROTOCOL=ipc)(KEY=EXTPROC1571)))

Connecting to (ADDRESS=(PROTOCOL=tcp)(HOST=server1)(PORT=1571))
STATUS of the LISTENER
------------------------
Alias                     listener
Version                   TNSLSNR for Linux: Version 11.2.0.2.0 - Production
Start Date                19-JUN-2012 19:46:36
Uptime                    0 days 0 hr. 0 min. 2 sec
Trace Level               off
Security                  ON: Local OS Authentication
SNMP                      OFF
Listener Parameter File   /u01/app/oracle/product/11.2/dbhome_1/network/admin/listener.ora
Listener Log File         /u01/app/oracle/diag/tnslsnr/server1/listener/alert/log.xml
Listening Endpoints Summary...
  (DESCRIPTION=(ADDRESS=(PROTOCOL=tcp)(HOST=server1)(PORT=1571)))
  (DESCRIPTION=(ADDRESS=(PROTOCOL=ipc)(KEY=EXTPROC1571)))
The listener supports no services
The command completed successfully

Note the line “the listener supports no services”. Since the listener doesn’t listen on port 1521, this will stay this way. Trying to connect to a database will only return the infamous “ORA-12514: TNS:listener does not currently know of service requested in connect descriptor”. Oh and yes, the tnsping will be successful!

To make the listener aware of the database service, you have two options:

  1. Statically register the database service
  2. Modify the local_listener parameter of your single instance/non Oracle Restart database

Option 1 requires a change to the listener.ora to register your database. Consider this example:

LISTENER =
  (ADDRESS_LIST=
        (ADDRESS=(PROTOCOL=tcp)(HOST=server1)(PORT=1571))
        (ADDRESS=(PROTOCOL=ipc)(KEY=EXTPROC1571)))

# this is new
SID_LIST_LISTENER=
   (SID_LIST=
        (SID_DESC=
          (GLOBAL_DBNAME=ORA11202)
          (SID_NAME=ORA11202)
          (ORACLE_HOME=/u01/app/oracle/product/11.2/dbhome_1/)
        )
      )

SECURE_REGISTER_LISTENER = (IPC)

Restarting the listener now shows us the following service information:

Connecting to (ADDRESS=(PROTOCOL=tcp)(HOST=server1)(PORT=1571))
Services Summary...
Service "ORA11202" has 1 instance(s).
  Instance "ORA11202", status UNKNOWN, has 1 handler(s) for this service...
    Handler(s):
      "DEDICATED" established:0 refused:0
         LOCAL SERVER
The command completed successfully

Now here is one of the things I’d like you to take away from this post: statically registered databases will report a status of UNKNOWN. However you can connect to a statically registered database just fine without the listener knowing anything about it. Consider it as a blindfolded person on a train: the person doesn’t see what its doing, but will get there in the end regardless.


$ sqlplus a/b@server1:1571/ORA11202

SQL*Plus: Release 11.2.0.2.0 Production on Wed Jun 20 13:13:40 2012

Copyright (c) 1982, 2010, Oracle.  All rights reserved.

ERROR:
ORA-01017: invalid username/password; logon denied

To prove it, the counters in the listener output is incremented:


Services Summary...
Service "ORA11202" has 1 instance(s).
  Instance "ORA11202", status UNKNOWN, has 1 handler(s) for this service...
    Handler(s):
      "DEDICATED" established:1 refused:0
         LOCAL SERVER
The command completed successfully

The second scenario involved telling the database’s pmon process how to connect to the listener. I’m using IPC here, all other registration attempts are blocked by the COST parameter:

SQL> alter system set local_listener='(DESCRIPTION=(ADDRESS=(PROTOCOL=ipc)(KEY=EXTPROC1571)))';

System altered.

SQL> alter system register;

System altered.

Keeping the static registration in the listener file, I get this:

Services Summary...
Service "ORA11202" has 2 instance(s).
  Instance "ORA11202", status UNKNOWN, has 1 handler(s) for this service...
    Handler(s):
      "DEDICATED" established:1 refused:0
         LOCAL SERVER
  Instance "ORA11202", status READY, has 1 handler(s) for this service...
    Handler(s):
      "DEDICATED" established:0 refused:0 state:ready
         LOCAL SERVER
Service "ORA11202XDB" has 1 instance(s).
  Instance "ORA11202", status READY, has 1 handler(s) for this service...
    Handler(s):
      "D000" established:0 refused:0 current:0 max:1022 state:ready
         DISPATCHER
         (ADDRESS=(PROTOCOL=tcp)(HOST=server1)(PORT=32637))
The command completed successfully

Looking at the output you can see that the same database is now registered a number of times. The top line, with status UNKNOWN is from the static registration.

The next lines are new, and result from the registration of the services with the listener, triggered by my “alter system register” command (I’m impatient, that registration would have happened eventually). The registration can also be seen in the listener.log:

19-JUN-2012 19:19:56 * (CONNECT_DATA=(CID=(PROGRAM=)(HOST=server1)(USER=oracle))(COMMAND=services)(ARGUMENTS=64)(SERVICE=listener)(VERSION=186647040)) * services * 0
2012-06-19 19:19:24.839000 +01:00
19-JUN-2012 19:19:24 * service_register * ORA11202 * 0
2012-06-19 19:19:43.319000 +01:00
19-JUN-2012 19:19:43 * service_update * ORA11202 * 0
2012-06-19 19:19:46.320000 +01:00

Summary

So now when you see an instance with status “READY”, you know that PMON communicates with the listener. An instance with status UNKNOWN is statically registered. Static registration is perfectly sufficient, and indeed necessary when you need to (re)start the database, or cycle the database while connected remotely such as during RMAN duplication or dgmgrl during switchover operations.

Oracle, Proxy, Obfuscation, Cookie Law, Talks, more...

It has been a long while since my last blog post. I have been very busy with Oracle security consulting, data security audits, teaching training courses and of course with my companies Database Security Scanner - PFCLScan . Oracle security....[Read More]

Posted by Pete On 20/06/12 At 02:23 PM

Linux 6 Transparent Huge Pages and Hadoop Workloads

This past week I spent some time setting up and running various Hadoop workloads on my CDH cluster. After some Hadoop jobs had been running for several minutes, I noticed something quite alarming — the system CPU percentages where extremely high.

Platform Details

This cluster is comprised of 2s8c16t Xeon L5630 nodes with 96 GB of RAM running CentOS Linux 6.2 with java 1.6.0_30. The details of those are:

#DDDDDD;display:block;font-family:monospace;font-size:12px;line-height:1.2em;overflow:auto;padding:5px;white-space:pre;width:100%;word-wrap:normal;margin:20px 0;">$ cat /etc/redhat-release
CentOS release 6.2 (Final)

$ uname -a
Linux chaos 2.6.32-220.7.1.el6.x86_64 #1 SMP Wed Mar 7 00:52:02 GMT 2012 x86_64 x86_64 x86_64 GNU/Linux

$ java -version
java version "1.6.0_30"
Java(TM) SE Runtime Environment (build 1.6.0_30-b12)
Java HotSpot(TM) 64-Bit Server VM (build 20.5-b03, mixed mode)

Observations

Shortly after I kicked off some Hadoop jobs, I noticed the system CPU percentages were extremely high. This certainly isn’t normal for this type of workload and is pointing to something being wrong or a bug somewhere. Because the issue was related to kernel code (hence high system times), I fired up perf top and tried to see where in the kernel code all this time was being spent (thanks @kevinclosson). Here is single iteration from perf-top which was representative of what I was seeing:

#DDDDDD;display:block;font-family:monospace;font-size:12px;line-height:1.2em;overflow:auto;padding:5px;white-space:pre;width:100%;word-wrap:normal;margin:20px 0;">PerfTop:   16096 irqs/sec  kernel:92.6%  exact:  0.0% [1000Hz cycles],  (all, 16 CPUs)
-------------------------------------------------------------------------------------------------------------------

             samples  pcnt function                                                              DSO
             _______ _____ _____________________________________________________________________ __________________

           223182.00 93.8% _spin_lock_irq                                                        [kernel.kallsyms] 
             3879.00  1.6% _spin_lock_irqsave                                                    [kernel.kallsyms] 
             3260.00  1.4% compaction_alloc                                                      [kernel.kallsyms] 
             1992.00  0.8% compact_zone                                                          [kernel.kallsyms] 
             1714.00  0.7% SpinPause                                                             libjvm.so
              716.00  0.3% get_pageblock_flags_group                                             [kernel.kallsyms] 
              596.00  0.3% ParallelTaskTerminator::offer_termination(TerminatorTerminator*)      libjvm.so
              169.00  0.1% _cond_resched                                                         [kernel.kallsyms] 
              114.00  0.0% _spin_lock                                                            [kernel.kallsyms] 
              101.00  0.0% hrtimer_interrupt                                                     [kernel.kallsyms]

At this point I decided to take a 60 second capture using perf record using the following command:

#DDDDDD;display:block;font-family:monospace;font-size:12px;line-height:1.2em;overflow:auto;padding:5px;white-space:pre;width:100%;word-wrap:normal;margin:20px 0;">$ sudo perf record -a -g -F 1000 sleep 60

After I had the capture, I built a flame graph using Brendan Gregg’s tools (because I am a big fan of performance data visualizations).

Looking at the functions listed in the Flame Graph (below) it looked like the issue was related to virtual memory and the Linux source shows many of these functions are in linux/mm/compaction.c.

Flame graph cropped

The issue seemed to be around virtual memory, however, this Hadoop job was using just 8 mappers per node and the java heap was set to 1GB, so there was plenty of “leftover” memory on the system, so why would this system be thrashing in the vm kernel code?

Experiment

While eating dinner and having a few beers something came to mind — Linux 6 had a new feature called Transparent Huge Pages, or THP for short. And like all new features that are deemed to add benefit, it is enabled by default. THP can be disabled by running the following command:

#DDDDDD;display:block;font-family:monospace;font-size:12px;line-height:1.2em;overflow:auto;padding:5px;white-space:pre;width:100%;word-wrap:normal;margin:20px 0;">echo never > /sys/kernel/mm/redhat_transparent_hugepage/enabled

And this change, and only this change, is exactly what I did when I returned from dinner. I then fired off my Hadoop job and watched anxiously. To my pleasant surprise, the elevated sys CPU times were now gone and things looked much more like I wanted them to.

I’ve flipped back and forth several times and have had nothing but high sys times with THP enabled, so it’s pretty reproducible on my system.

Thoughts

I’m not 100% sure why THP are choking up my system (maybe bug vs. feature) but I’m certainly interested if others have seen similar behavior on Linux 6 with data intensive workloads like Hadoop and THP enabled. Other thoughts, experiment results, etc. are also very welcome.

To put things into perspective on how bad it gets, here are two screen captures of Cloudera Manager which highlights the ugly sys CPU times (see the middle chart; green = sys, blue = usr) when THP are enabled.

Do note the time scales are not identical.

Transparent Huge Pages enabled:
Transparent Huge Pages enabled

Transparent Huge Pages disabled:
Transparent Huge Pages disabled

Update:

The issue seems to be related to transparent hugepage compaction and is actually documented on the Cloudera Website (but my google foo did not turn it up) here which recommends the following:

#DDDDDD;display:block;font-family:monospace;font-size:12px;line-height:1.2em;overflow:auto;padding:5px;white-space:pre;width:100%;word-wrap:normal;margin:20px 0;">echo never > /sys/kernel/mm/redhat_transparent_hugepage/defrag

I did stumble across the bug listed on the Red Hat Bugzilla site in the google cache but it is not publicly available for some reason (bummer).
https://bugzilla.redhat.com/show_bug.cgi?id=805593

Just confirming after I disabled THP defrag on my cluster the high sys CPU times are not present.

Update 2:

Just for documentation’s sake, here are some performance captures between THP enabled and disabled.

#DDDDDD;display:block;font-family:monospace;font-size:12px;line-height:1.2em;overflow:auto;padding:5px;white-space:pre;width:100%;word-wrap:normal;margin:20px 0;"># echo never > /sys/kernel/mm/redhat_transparent_hugepage/enabled
# collectl -scm -oT -i2
waiting for 2 second sample...
#         <----CPU[HYPER]----->
#Time     cpu sys inter  ctxsw Free Buff Cach Inac Slab  Map 
10:33:08   84   4 46083   6964   5G 324M  61G  60G 563M  25G 
10:33:10   71   7 39933  25281   5G 324M  61G  60G 566M  24G 
10:33:12   89   4 48545  15724   5G 324M  61G  60G 566M  25G 
10:33:14   81   7 44566   8224   7G 324M  61G  60G 566M  23G 
10:33:16   81   4 44604   8815   8G 324M  62G  60G 566M  22G 
10:33:18   87   7 46906  20430   8G 324M  62G  60G 566M  22G 
10:33:20   79   6 43565  11260   6G 324M  62G  61G 565M  24G 
10:33:22   75   6 41113  13180   3G 325M  62G  61G 565M  26G 
10:33:24   64   5 36610   9745   2G 325M  62G  61G 565M  27G 
10:33:26   60   4 34439   7500   1G 325M  62G  61G 565M  28G 
10:33:28   74   5 40507   9870   1G 324M  61G  60G 564M  30G 
10:33:30   73   6 42778   7023   6G 324M  60G  59G 561M  25G 
10:33:32   86   5 46904  11836   5G 324M  61G  59G 561M  26G 
10:33:34   78   3 43803   9378   5G 324M  61G  59G 559M  25G 
10:33:36   83   4 44566  11408   6G 324M  61G  60G 560M  24G 
10:33:38   62   4 35228   7060   7G 324M  61G  60G 559M  23G 
10:33:40   75   7 42878  16457  10G 324M  61G  60G 559M  21G 
10:33:42   88   7 47898  13636   7G 324M  61G  60G 560M  23G 
10:33:44   83   6 45221  17253   5G 324M  61G  60G 560M  25G 
10:33:46   66   4 36586   6875   3G 324M  61G  60G 560M  26G 
10:33:48   66   4 37690   9938   2G 324M  61G  60G 559M  28G 
10:33:50   66   3 37199   6981   1G 324M  61G  60G 559M  28G 

# echo always > /sys/kernel/mm/redhat_transparent_hugepage/enabled
# collectl -scm -oT -i2
waiting for 2 second sample...
#         <----CPU[HYPER]----->
#Time     cpu sys inter  ctxsw Free Buff Cach Inac Slab  Map 
10:51:31   99  81 51547  14961  24G 326M  53G  51G 536M  15G 
10:51:33   92  81 49928  11377  24G 326M  52G  51G 536M  15G 
10:51:35   59  58 39357   2440  24G 326M  52G  51G 536M  15G 
10:51:37   54  53 36825   1639  24G 326M  52G  51G 536M  15G 
10:51:39   88  87 49293   2284  24G 326M  52G  51G 536M  15G 
10:51:41   95  94 50295   1638  24G 326M  52G  51G 536M  15G 
10:51:43   99  98 51780   1838  24G 326M  52G  51G 536M  15G 
10:51:45   97  95 50492   2412  24G 326M  52G  51G 536M  15G 
10:51:47  100  96 50902   2732  24G 326M  52G  51G 536M  15G 
10:51:49  100  89 51097   4748  24G 326M  52G  51G 536M  15G 
10:51:51  100  71 51198  36708  24G 326M  52G  51G 536M  15G 
10:51:53   99  56 51807  50767  24G 326M  52G  51G 536M  15G 
10:51:55  100  51 51363  66095  24G 326M  52G  51G 536M  15G 
10:51:57  100  48 51691  73226  24G 326M  52G  51G 536M  15G 
10:51:59   99  36 52350  87560  24G 326M  52G  51G 536M  15G 
10:52:01   99  51 51809  42327  24G 325M  52G  51G 536M  15G 
10:52:03  100  50 51582  62493  24G 325M  52G  51G 536M  15G 
10:52:05   99  44 52135  69813  24G 326M  52G  50G 536M  15G 
10:52:07   99  39 51505  65393  24G 326M  52G  50G 536M  16G 
10:52:09   98  39 52778  54844  24G 326M  52G  50G 536M  16G 
10:52:11   98  62 51456  30880  24G 326M  52G  50G 536M  16G 
10:52:13  100  83 51014  21095  24G 326M  52G  50G 536M  16G

Update: 2013-09-17
Oracle comments on disabling THP in Oracle Linux: Performance Issues with Transparent Huge Pages (THP)

Pascal matrix SQL puzzle solution

I’ve been impressed with the solutions to my little problem of generating a symmetric Pascal matrix using SQL. Charles Hooper in particular has provided some very nice commentary on the problem, complete with diagrams and 2 alternative solutions.

I thought I’d walk through my solution in order to explain my thought process and see if it resonates with anyone.

Usually when I think about generating rows with SQL I think about the Oracle “trick” of using the CONNECT BY clause to generate rows:

select level from dual connect by level <= k

You’ll see a lot of constructs like this in the solutions provided by commenters.

However, lately I’ve been tending more toward the ANSI SQL Recursive construct instead, which works in Oracle and many other SQL databases:

with f (n) as (
select 1 from dual
union all
select n+1 from f where n < k
)
select n from f;

I particularly like the way this statement works, even if it’s technically not recursive, as it defines rows in terms of prior rows, which leads to all kinds of unique possibilities of ways to construct new rows.

I think the symmetric Pascal matrix lends itself to this kind of technique especially because it involves factorials.
Charles (and others) have used the Wikipedia definition of the Pascal matrix for each cell entry which is Aij = (i+j-2)! / ((i-1)!(j-1)!). And most of the solutions have used a clever way to calculate the necessary factorials:

select exp(sum(ln(level))) from dual connect by level <=n

However, the neat thing about factorials is that they are easily defined in recursive terms:

f(0) = 1
f(n+1) = (n+1) * f(n)

And this definition maps really nicely to the ANSI SQL Recursive construct:

with f(n,nf) as (
select 0,1 from dual
union all
select n+1, n+1 * nf from f where n < k
)
select n,nf from from f;

Given this idea of using the Recursive construct, I set about seeing if I could use it to solve my challenge.

The first thing I did was to construct the row (i) and column (j) indices, doing all of the rows for each column — to do that I started with a simple row generator:

with m(i) as (
select 1 from dual
union all
select i+1 from m where i < s
)
select i from m;

With s = 4 this generates a simple list from 1 to 4:

1
2
3
4

Next, I wanted to generate the columns, repeating the rows for each column as I moved from column to column. I did this by “re-setting” the row counter and incrementing the column counter after finishing each column:

with m(s,i,j) as (
select 4,1,1 from dual
union all
select
s,
case when i < s then i+1 else 1 end,
case when i < s then j else j+1 end
from m where i < s or j < s
)
select i,j from m;

In this statement I included the size (s) in the initial query and “passed it down” each row in order to easily refer to it. This query produces:

1,1
2,1
3,1
4,1
1,2
2,2

4,4

It stops when both i and j reach 4.

Now that I’ve got the cell indicies I started to think about how to calculate the information necessary for the values. Based on the cell definition from Wikipedia, I need 3 values:

(i+j-2)!, (i-1)!, and (j-1)!

What’s interesting about the required values is that they look like they could be defined via information from the prior item since they refer to things like i-1 and factorial — both of which should be pretty easy to generate. Let’s try to do (i-1)! (which I’ll refer to as im1f or “i minus 1 factorial”)

with m(s,i,j,im1f) as (
select 4,1,1,1 from dual /* This is cell 1,1. (i-1)! is (1-1)! is 0! which equals 1 */
union all
select
s,
case when i < s then i+1 else 1 end,
case when i < s then j else j+1 end,
case when i < s then im1f*i else 1 end
from m where i < s or j < s
)
select i,j,im1f from m;

Basically, this just multiplies the prior (i-1)! times i to get the new (i-1)!, and “resets” to 0! whenever we move to the next column. This produces:

1,1,1
2,1,1
3,1,2
4,1,6
1,2,1
2,2,1
3,2,2
4,2,6

4,4,6

We can get (j-1)! in a similar fashion:

with m(s,i,j,im1f,jm1f) as (
select 4,1,1,1,1 from dual
union all
select
s,
case when i < s then i+1 else 1 end,
case when i < s then j else j+1 end,
case when i < s then im1f*i else 1 end,
case when i < s then jm1f else jm1f*j end
from m where i < s or j < s
)
select i,j,im1f,jm1f from m;

So far, so good — I’m liking this approach as each cell takes advantage of the prior cell’s information to simply get the necessary values. Now, how do I get (i+j-2)!

I started out seeing if I could simply get (i+j-2) or ipjm2:

with m(s,i,j,im1f,jm1f,ipjm2) as (
select 4,1,1,1,1,0 from dual
union all
select
s,
case when i < s then i+1 else 1 end,
case when i < s then j else j+1 end,
case when i < s then im1f*i else 1 end,
case when i < s then jm1f else jm1f*j end,
case when i < s then ipjm2+1 else j end
from m where i < s or j < s
)
select i,j,im1f,jm1f,ipjm2 from m;

What struck me about this was then when i=1 then i+j-2=j-1, and I’m already calculating (j-1)!, so it looks like I can use it when I “reset” back to i=1 when switching columns. Let’s see what the pattern looks like for the factorial as we go “down” the column row by row:

(j-1)! for the first row
previous row value * (i+j-1), for subsequent rows

Which is easy for us to write into our query now as ipjm2f:

with m(s,i,j,im1f,jm1f,ipjm2f) as (
select 4,1,1,1,1,1 from dual
union all
select
s,
case when i < s then i+1 else 1 end,
case when i < s then j else j+1 end,
case when i < s then im1f*i else 1 end,
case when i < s then jm1f else jm1f*j end,
case when i < s then ipjm2f*(i+j-1) else j*jm1f end
from m where i < s or j < s
)
select i,j,im1f,jm1f,ipjm2f from m;

Which now produces:

1,1,1,1,1
2,1,1,1,1
3,1,2,1,2
4,1,6,1,6
1,2,1,1,1
2,2,1,1,2
3,2,2,1,6
4,2,6,1,24
1,3,1,2,2
2,3,1,2,6
3,3,2,2,24
4,3,6,2,120
1,4,1,6,6
2,4,1,6,24
3,4,2,6,120
4,4,6,6,720

At this point, it’s simple to just put together the whole formula and display it as the value for each cell, noting that the initial value for every column (row 1) is just 1.

with m(s,i,j,im1f,jm1f,ipjm2f,v) as (
select 4,1,1,1,1,1,1 from dual
union all
select
s,
case when i

Which works in Oracle 11g without any special Oracle functions or syntax to produce:

1,1,1
2,1,1
3,1,1
4,1,1
1,2,1
2,2,2
3,2,3
4,2,4
1,3,1
2,3,3
3,3,6
4,3,10
1,4,1
2,4,4
3,4,10
4,4,20

And also works perfectly well in PostgreSQL 9.1 with the addition of the “recursive” keyword:

with recursive m(s,i,j,im1f,jm1f,ipjm2f,v) as (
select 4,1,1,1,1,1,1 from dual
union all
select
s,
case when i

And there you have it — an ANSI SQL version.

Now, while I think the code is pretty elegant, it does have a drawback — each cell value requires the prior cell value in order to be calculated. The cell calculations are NOT independent, which ends up making this a serial algorithm. Many of the other solutions in the comments compute the cell values independently of each other, which facilitates parallelizing the production if that’s necessary and should be a consideration when looking at the various techniques.

I hope you’ve enjoyed this rather long post describing my process for creating the query, and that such a process might be useful to you as you construct similar queries.

East Coast Oracle Users Group Conference...

I'll be speaking at the East Coast Oracle Users Group Conference held in North Carolina on October 16th-18th.  It is always nice to be able to stay in my own timezone for a change!

There are opportunities to not only attend the conference but also to speak - they are still accepting abstracts for presentations until June 21st.  If you have done anything interesting (you have), please consider speaking out about it.  Others will be interested.  You never know how it will go unless you try!

Hope to see you there!