Common Table Expressions – SQL Magic by another name

Common Table Expressions, or CTEs as they are often called, are an area of SQL which can by some be considered to be no different than magic. This is because few of us use them, and even fewer of us use them regularly enough to make them like the familiar of some powerful wizard in some book. And just like those familiars sometimes do in the books, they can give us great frustration or even turn upon us like some demon or Djinn who has escaped the bounds we thought would control them. But all the same, they can be quite useful, and indeed, necessary for us to have a performant application.

An introduction by example

And I myself have used them in a number of instances, including:

  • Building up access control lists, where permissions can be inherited through roles.
  • Generating menu hierarchies.
  • Generating organizational charts.
  • Analyzing data to generate reports.

In many of these cases, will see records in a database which point at other records of the same type. For example, here is one where we have an employee record, where there is a reference to the supervisor (their manager, boss, or whatever term is used at that level of the organization).

Now, when generating the org chart, moving downward from someone in the organization, such as an executive, we could do this in one of two ways, which basically boils down to:

  1. Have our program do the work.
  2. Have our database do the work.

In general, you are actually better off doing the latter, since:

  1. The database will tend to reside on a system with lots of resources (CPU, memory, disk), while your program may be running on a system with a much smaller set of resources, which can easily be replicated, etc.
  2. Each query sent to the database uses those resources, as well as network bandwidth, with there being costs being setup to validate and prepare each query, to run it, to prepare the results, as well as in the transmission and consumption of those results. And this does not even consider that a new database connection may need to be created.
  3. While we can certainly use things such as prepared statements in our program to reduce the overhead, and our queries may be simple, with a properly designed database, the database server can use its knowledge, as well as the expertise of its developers, to do things far better than we can.

Think about that employee database for a moment to see why. Suppose we are talking an employee database with 100,000 records (when I was at Lucent in what we termed the “Greater Bell Labs R&D”, we were over 150,000, so that is not an impossible figure), in which 90,000 of them are employees with nobody reporting to them, that could easily turn into 90,000 unnecessary queries sent to the server, or some similar nightmare, with all the associated execution time on both end, and all the requests going back and forth. So this is where a form of CTE called a recursive CTE helps us greatly.

Now, while referred to as a “recursive” CTE, it is really just a repeated iteration, where the records resulting from the prior pass are used to produce a new set of records, and it is repeated until no further records are returned to be placed into the temporary working table the server uses internally. Here is the CTE for the employees table.

WITH RECURSIVE report_tree ( employee_id, fname, lname, supervisor ) AS (
    SELECT
        employee_id,
        fname,
        lname,
        supervisor
    FROM employees
    WHERE supervisor IS NULL

UNION ALL

    SELECT
        e.employee_id,
        e.fname,
        e.lname,
        e.supervisor
    FROM employees AS e
    INNER JOIN report_tree AS emps ON (emps.employee_id = e.supervisor)
)

SELECT *
FROM report_tree;

When we look at this, we see the WITH block which defines the CTE as a prefix to the SELECT which uses it. That block consists of (in this case) an initial query (sometimes referred to as the “non-recursive” or “anchor” query), a UNION, and then the “recursive” portion, which references the containing CTE. In this case, we first get the batch of employees who have no supervisor, which may in fact be just a single record, or could be multiple records (such as the CEO, CTO, CFO, CLO, etc.). And in the next iteration, the bottom part will get those who report to the first set, with the following iteration getting those who report to the second set, and so on.

The one issue with the above CTE is that the output order, put bluntly, sucks like the vacuum of intergalactic space. There is no easy way of taking the output records and sorting them to even remotely resemble the organization. But there is a way in which we can address this, as we will see later.

My most recent encounter… (an in depth look)

Now, the most recent item where I came across a structure which could use a CTE is this… I have a page which is displayed on some of my machines when I connect to them via my browser. For example, if I connect to my main administrative server, or to the machine which handles all my virtual machines, I get the following page (sanitized):

In looking to redesign this, and ultimately put it into a new application which I am writing (which I am currently calling Heimdallr), I wanted to put this into a database and turn it into a dynamic page. And when you look at this, it quickly becomes apparent that it should be represented as a hierarchy. It is, after all, yet another hierarchical menu, with all but the top nodes being HTML list items, and each leaf item having an associated URL, a target window (hidden to the viewer). Indeed, here it is in its source form:

<html>
<head>
<title>Monitoring</title>
</head>
<body>
<h1>Server Info/Status</h1>
<ul>
    <li><a href="/server-info" target="server-info">Server Info</a></li>
    <li><a href="/server-status" target="server-status">Server Status</a></li>
</ul>

<h1>Builds</h1>
<ul>
<li>builds
    <ul>
        <li><a href="http://builds.example.com:8080" target="Jenkins">Jenkins</a></li>
    </ul>
</li>
<li>tuleap
    <ul>
        <li><a href="https://tuleap.example.com" target="tuleap">Tuleap</a></li>
    </ul>
</li>
<li>registry
    <ul>
        <li><a href="https://registry.example.com/v2/_catalog" target="registry">Local Docker registry</a></li>
    </ul>
</li>
<li>mirrors
    <ul>
        <li><a href="http://mirror.example.com/local/" target="mirror-local">Local Repository</a></li>
    </ul>
    <ul>
        <li><a href="http://mirror.example.com/local-secure/" target="mirror-local-secure">Local Secure</a></li>
    </ul>
</li>
</ul>
<h1>Management</h1>
<ul>
<li>firewall
    <ul>
        <li><a href="https://gateway.example.com" target="gateway" rel="noreferrer">Firewall</a></li>
    </ul>
</li>
<li>Host1
    <ul>
    <li><a href="https://host1-drac.example.com" target="host1-drac">host1 DRAC</a></li>
    <li><a href="https://host1.example.com:1311/OMSALogin?msgStatus=null" target="host1-om">Host1 OpenManage</a></li>
    </ul>
</li>
<li>nas
    <ul>
    <li><a href="https://nas.example.com/" target="nas">nas</a> (<a href="https://nas.example.com/api/docs/" target="nas-api">API Docs</a>)</li>
    </ul>
</li>
<li>Host2
    <ul>
    <li><a href="http://host2.example.com/cobbler_web/" target="cobbler">Cobbler</a></li>
    <li><a href="http://host2.example.com/phpldapadmin/" target="ldapadmin">phpldapadmin</a></li>
    </ul>
</li>
<li>Host3
    <ul>
    <li><a href="http://host3.example.com/phpipam/" target="phpiam">phpipam</a></li>
    <li><a href="http://host3.example.com/phpmyadmin/" target="phpMyAdmin">phpMyAdmin</a></li>
    <li><a href="http://host3.example.com/phpPgAdmin/" target="pgadmin">phpPgAdmin</a></li>
    </ul>
</li>
</ul>
<h1>Monitoring</h1>
<ul>
<li><a href="/cacti" target="cacti">Cacti</a></li>
<li>MRTG
<ul>
<li><a href="/mrtg/sw02.html" target="mrtg-sw02">SW02</a></li>
</ul>
</li>
<li><a href="/nagios" target="nagios">Nagios</a></li>
<li><a href="/smokeping/sm.cgi" target="smokeping">Smokeping</a></li>
</ul>

</body>
</html>

So, the first pass of this becomes the following database tables, shown in graphical format:

The index_groups table becomes something like this (intentionally shown as if “Management” was added after the fact):

IDOrderText
11Server Info/Status
22Builds
34Monitoring
43
Management

While index_links contains records like the following:

Link IDGroup IDParent Link IDURLTargetDescription
13firewall
21
https://gateway.example.com

gateway

Firewall
33Host1
43https://host1-drac…drachost1 DRAC
53https://host1:1311host1-omHost1 OpenManage
63Host2
66https://host2…host2-cobblerCobbler

Now, as I said above, we could do this with loops making queries, but remember those 90,000 employees? While this menu only has 31 records half of them have no children, so we would be making roughly 16 queries with no results.

NOTE: Yes, we could group them and use queries containing code like WITH index_link_parent_id IN [ 1,2,3,4 ], but that quickly becomes complex, and could run into some limit. So again… why not let the SQL server do what it has been designed, and indeed is optimized to do.

So, how can we get those records out, and have them in an nice order, unlike the employee list? The first part is to have each record contain what is often referred to as an XPATH… a string which indicates how we arrived at the record in question. In this example, we are not going to use the /node1/node2/... syntax, but something similar… we will take the unique ID of each record in index_links, and add it onto a string, and each child will add theirs onto the end, using a ‘>’ character as a separator. It could be just about anything consistent, such as a colon, a dash, a period or a comma… just something which does not show up in our IDs, so we know where one ID ends and the next child’s begins. Were we to add an order to those records, we would just use it instead (or perhaps the order and ID, if we allowed for duplicate order values). And, as an added bonus, we will also use a trick to make the records of index_groups look like the records of index_links, so that we have rows for those records included in their spots in the hierarchy. And so, we have this CTE to get the data:

WITH RECURSIVE menutree (group_id, link_url, link_target, description, link_id, link_parent_id, xpath) AS (
    SELECT                                      -- Non-recursive
        index_group_id,
        CAST(NULL AS CHARACTER VARYING) AS link_url,
        CAST(NULL AS CHARACTER VARYING) AS link_target,
        CAST(index_group_name AS CHARACTER VARYING(64)),
        CAST(NULL AS INTEGER) AS link_id,
        CAST(NULL AS INTEGER) AS parent_id,
        CONCAT('', index_group_order)
    FROM index_groups

    UNION

    SELECT                                      -- Recursive
        CAST(NULL AS INTEGER),
        l.index_link_url,
        l.index_link_target,
        CAST(l.description AS CHARACTER VARYING),
        l.index_link_id,
        l.index_link_parent_id,
        CONCAT(mtree.xpath, '>', l.index_link_id)
    FROM index_links l
    INNER JOIN menutree mtree ON (
        (l.index_link_parent_id IS NULL AND l.index_group_id = mtree.group_id) 
        OR
        (l.index_link_parent_id IS NOT NULL AND l.index_link_parent_id = mtree.link_id)
    )
)
SELECT * FROM menutree
ORDER BY xpath;

The non-recursive part starts by getting the records out of index_groups, and adding in columns with NULL values to make those look like the other records, and then in the “recursive” block, we have our query to add on the next set of records. The things to note here are:

  1. We are using column names on the CTE itself to save ourselves some typing.
  2. For our INNER JOINON, we have two conditions or’ed together.
    1. A condition to join our group and link records for the first round of joining, and
    2. A condition to join child links to their parent links.
  3. We are having to use CAST() to have our column types match up, which is one reason why a CTE such as this can be particularly tricky.
  4. The order is not exactly identical. In particular, the fact that the MRTG record was added last and the SW02 record placed under it, as if by an afterthought, means that the MRTG entry and its children will come last, rather than following the entry for Cacti.

But with that said… here is the output.

It should be noted that:

  1. A simple JOIN between the two tables and a sort on the group ID and description takes well over half that amount of time.
  2. We are in fact doing three JOINs, not two.
  3. Each query on item_links is taking about 4.5ms, meaning that even if we group things as we produce each query level, we would be talking roughly 18ms (3 levels, and an empty 4th level), and were we to not group them, but to do a simple one by one query, we would spend over 60ms just querying for children for rows which have none. And that would still require our taking the results and interleaving them with their parent records, while here, we need only look at the length of the xpath column, see we need to add another layer or close one, and continue from there… and we could even have computed a depth in the results, had we desired to do so.

For Further Reading

So, with this, here are a few handy links for you if you wish to learn more about them, as they are available in many of the current SQL server implementations out there today.

FreeNAS woes involving certificates and HTTPS Everywhere

In my previous post, I unloaded on Chrome’s crappy handling of expired SSL certificates. I had to work around the fact that when trying to connect using HTTP with its FQDN (e.g. http://host.subdomain.ka8zrt.com), the browser would itself switch to HTTPS, and then refuse to let me connect due to the SSL certificate having expired. And so, I instead had to connect using the IP address. Using that route, I thankfully can get around the expired certificate, since the application in question (FreeNAS) happened to also be set to allow connections via HTTP, and did not either rely on name based virtual hosts, or use URLs which used the FQDN. Indeed, using the IP address in the URL (e.g. https://192.168.1.1), I got the following screen:

Notice… this has the “Proceed to…” link at the bottom, which the other screen I got when using the FQDN  did not. But going this route, I was able to both re-enable the ability to use HTTP as well as HTTPS, turn off forced redirection by the app, and thanks to some digging, find out how to change these two settings from the CLI.  And so, in case browsers across the board decide to do away with the “Proceed to” link in all cases, I am putting the info about changing the settings here for general consumption.

Being able to connect to the box using SSH and get to the shell (or login via the console), I was able to disable redirecting HTTP to HTTPS and  enable HTTP as well as HTTPS with the following command. The configuration is stored in a SQLite3 database, and as of this writing, the disabling of the redirection is done with the following command:

sqlite3 /data/freenas-v1.db 'update system_settings set stg_guihttpsredirect=0;'

and to enable the use of HTTP as well as HTTPS, the command is:sqlite3 /data/freenas-v1.db 'update system_settings set stg_guiprotocol="httphttps";'

If you want to check the settings, then you can do something like the following, which shows both the command and the response.root@nas:~ # sqlite3 /data/freenas-v1.db 'select * from system_settings;'
1|httphttps|en|America/New_York|192.168.1.4|0.0.0.0|80||::|443|0|1|1|+b5ou/urLTPPL7FsrRz5YvYetWIDEPaUooZypKSEZUo=|f_info

After making the change, a reboot using the CLI command on the appliance, a curl/wget command from another host (ignoring certificate issues), or other means will result in the config files being regenerated from the database, and your being able to at least use a browser which allows you to proceed even though there are issues with the certificate.

Note: Switching to include HTTP or just use HTTP instead of HTTPS, while still having the redirection turned on creates an interesting condition, where you will still get sent to the HTTPS URL, but will either be faced with the expired certificate behaviour or just fail to get a connection. Thankfully, the commands I just gave will save your bacon in that instance as well.

I will also add that I have never been a fan of storing critical configuration information which affects connectivity in a database on that host/appliance and regenerating flat files from the database, since I first encountered it in AIX on the RS/6000 boxes back around 1990 or so. Corrupt the database, or edit a file without realizing that it is one of those files which gets regenerated at reboot, or is ignored for the most part by the OS, and it will drive you to trying to put your own head through the walls of a spillway of a dam, sometimes months after you made the change. I understand why it is so very tempting, but when it is suggested, learn to say a very important word: NO! An XML file is fine, as is YAML, JSON, or some other text based format…but not a database… even a SQLite database. Think worst case scenario where you are limited to text.

Google Chrome Frustrations

As a developer, it is not often that a developer or developer team makes me go WTF, and has me envisioning conducting a test of both electromagnetic repulsion and the Pauling Exclusion Principle using their head and an available desk or wall, but today, the Google Chrome team has done it twice. Congratulations to them for setting several new records (minimum interval between occurrences, and the more than once in a day).

The first item is a common occurrence for me, and can sometimes happen with just a handful of tabs, or it can happen when I am having a tab-crazy day going to sites, opening new tabs to read various pages of documentation, etc. And every other day or so, I pull up the menu, open the task manager, and find one of the browser tasks playing Jabba the Hut, just sitting there big and bloated, slowly laughing at me as it consumes a GB or more of RAM (IIRC, I have seen over 2.1GB, and I only have 4GB of RAM on the machine). Sometimes, it is a task which is handling a site such as Facebook or even gmail, and at other times, it is the main browser task. Indeed, right now, my main browser task is reporting a memory footprint of just over 675MB, and a tab handling Facebook is around 570MB… which is mild. If it is a task other than the main browser task, I will often kill that task, and then reload the tab, but if it is the browser task, I have no option but to enter chrome://restart in the URL bar and restart the entire browser. And while I can open up the developer tools and grab a memory snapshot for the former (if it has not grown too big), there is no such option in the case of the main task.  But the thing is, there really should be no reason for a task to grow beyond around the 500MB point, and even then, it should only happen on a site which has lots of media on a very long page (e.g. Facebook). And even then, that is what disk caching is for, and generally indicates some stupid programming error like a memory leak, or just trying to do too damned much in RAM. And, in most cases, one puts in place an adjustable resource limit which says “Nope… free some stuff up first!” when you try to allocate too much. Why Chrome does not have such a process in place, given its nature, is beyond me.

The second item, I hit while working on a script which would allow me to automatically renew the SSL certificates on a NAS appliance I have setup. I had been using CAcert for signing my certificates given they are not charging, much less charging a mint for signing, but there are a few issues with it.  One issue is that the folks at Mozilla refusing to add their signing certificates to the trusted list which is used by pretty much everybody. Every time the CAcert folks seem to have addressed issues raised the last time they tried to get added to the list, there always seems to have been a new issue, so that using certificates signed by them require importing their root certificates. While for an internal site, that is no biggie, for an external site, that would mean you having to import those certificates to read this page… big NOPE. The second is that while renewing a certificate is just a matter of going to the website and clicking a button or three, I then have to copy/paste the new certificate and put it where it needs to go. And having to do that every six months for multiple sites/services… Yea… But more about that at the end… in the meantime, what had me once again thinking of taking some developer, PM or suit on the Chrome team, and repeating the test over and over while saying “What… the frell…were you…thinking?  Or did…you even…stop to… think about…this possibility??” Google, through their Chrome team, has been driving a HTTPS everywhere initiative, and now, regardless of how a site/program/appliance is configured, Chrome insists on switching over to HTTPS, and provides no way to use the hostname to access it via HTTP. No “Let me do this.  Yes, I am sure!” type dialog of any variety, no site setting… nada… just this…

So, after taking a bit of a break today, when I came back to this to try to debug the program which uses a halfway documented REST API, I could not use Chrome to access the WUI (Web UI), because the certificate had expired, and I use internal subdomains of my domain. Now mind you, I think that the HTTPS Everywhere initiative is the best thing since a meatloaf sandwich, and the work done by the ISRG, EFF, Google and others is great on the whole, but that is like saying someone did a great job at clearing a minefield to turn it into a school playground, when they missed at least one landmine. Worse… this application uses its own internal database to store its configuration, and all configuration is done through that same WUI Chrome is not allowing me to access to update the expired certificate.

Now, at this point, there are a couple of options…

  1. Use the numeric IP address.  Thankfully, the application for this appliance does not redirect to or rely upon the hostname, like some do.
  2. Setup and use an address in one of the gTLDs (e.g. the .com, .org, .net, .test, etc. part of the name) which is not forced to HTTPS.  I think .test is the one they talk about… but if the app relied on the hostname, how to get in and configure that alternate name??
  3. Use a different browser. HTTPS everywhere has not made full penetration into the browsers yet… but what happens if this happens a few years down the line?

All in all, it shows a critically major gap when decisions like what Chrome has done do not account for situations like this, and why when applications do not have the means to update configurations from a CLI, that too is a major design flaw.

Now… one last bit, about the certificate issue. To help handle the HTTPS Everywhere effort, folks like the EFF, Mozilla, Chrome and so many others got together to address the issues such as the cost of signed certificates, etc. They have put up the Let’s Encrypt certificate authority, which has the ACME protocol, to make things happen automagically… but not everyone has managed to integrate things yet, and who knows how many appliance applications are either dragging their feet (such as arguing that a given appliance should not be accessible from the public Internet), or have not managed to figure out how to make things work. And until everyone thinks things through 100%, I expect this sort of frustration to become more and more common, unless the browser folks give you the means to say “Yes, I really want to use HTTP and not HTTPS, as risky as that may be” for at least a given session/tab.