Friday, August 10, 2012

A Software Architect's View of the Design of Double Entry Paper Accounting Systems

Taking a brief break from the computer side for now, I figured it would be worth describing the basic design considerations of double entry.  This post is the result of my work studying history and anthropology far more than working on LedgerSMB but of course working on the software played a role too.  Most of what is presented here is my own original research.

Also I am sure that accounting students or those who have studied accounting in school will find some aspects of this challenging since I explore some areas that accountants are not taught about and because, as a history buff, I refuse to believe that certain designations are arbitrary.

I think that the apparent evolution of double entry accounting shows a number of potential approaches for dealing with the very difficult distributed transaction issues of today, not so much in what to do but where to look for answers.

The Tally Stick System and the Origins of Double Entry

In medieval Europe there were two basic economic constraints.  First most people could not read or write or perform arithmetic on paper, which limited the forms of exchange possible.  Secondly there was a perpetual shortage of currency which meant that official money was not really possible to use money as a simple medium of exchange.  These problems were resolved by the development of the split tally stick.  The split tally stick evolved through the Middle Ages into a very highly developed system and was still in active use in some places into the 19th century.  Ironically it was an effort to destroy these sticks held by the British Government in 1836 which burned down both houses of parliament.

At its fully fully developed form, a split tally stick consisted of a stick, usually of hazel, which had notches carved in it.  The stick would be split length wise and one side would be cut short.  The long side would be called the stock (trunk) and represented the debt.  It would be held by the creditor.  The short side, called the foil ('leaf') would follow the loan.

The creditor, at the allotted day, could show up and present his stock and demand payment.  If the creditor tried to pad the debt by adding more notches, this would be immediately apparent, and there was no way to erase notches on the other side.  Additionally it was immediately apparent if the sides were from different tally sticks.

As the Middle Ages progressed, literacy became somewhat more widespread.  From the days of the Merovingian king, Charles Martel,  through the "Carolingian Renaissance" in to the high Middle Ages, literacy began to become more open beginning with kings and eventually being available to the children of wealthy merchants.  With literacy came basic knowledge of arithmetic and eventually algebra, and the efforts to track tally sticks on paper may have given rise to double entry systems of bookkeeping.

The first step of course is a journal.  Here the tally sticks could be recorded.  The bigger stocks (like bigger numbers) would be reported on the left, while the smaller foils would be reported on the right.  One could then get a quick breakdown of one's position in terms of debt collectable vs debt owing.  Within a few hundred years, this develops into general ledgers and the full double entry accounting system that has not changed in its outlines since Luca Pacioli wrote about it in the 15th century.

However it is worth noting that split tally sticks are inherently double entry in the sense that every debit has a corresponding credit, and they are inherently accrual since income and formal payment could not be as well correlated as could invoice and income.  Moreover the rules for stock and foil appear to have tracked the rules for debit and credit today.

It is finally worth noting that even in Pacioli's day, and even a hundred years later, tally sticks were in common use in this way.  Therefore, it seems to me that Pacioli himself was probably familiar with these and so his use of Latin terms corresponds almost certainly to the tally stick approach.


Business as Owning Nothing for Itself

Many of the principles I have found while investigating the origins of double entry accounting are challenging to us today and force us to think about businesses differently.  Exploring the development of designs of older functional systems also better prepares us to think about design ourselves in areas of software where we are building complex functional systems today.

In a double entry accounting system, a business owns nothing for itself.  Everything it owns, it owes to its owners.  This is why the books always balance and why debits always equal credits.  Corporations are a legal fiction which post-date the development of double-entry accounting systems but even they don't own things for themselves.  Their equity is owned entirely by their owners.  A corporation owns things only on behalf of its shareholders.  Limited liability only means that the effective equity cannot drop below 0 and a corporation has no possessory interest distinct from those of its stockholders.

This understanding is also behind the fundamental accounting equation that assets - liabilities = equity.

As long as the books are guaranteed to balance, then it is possible to detect errors by balancing the books (using a trial balance, as Pacioli suggests).  This is only possible if the intrinsic net worth of the business is always 0 (when we talk about the net worth of the business, we are talking about the extrinsic net worth, namely the equity balance, see below, but this is actually the net balance of debt owed by the business to its owners--- while an individual may on balance be worth a million dollars, this means something very different than if a business is worth a million dollars because the business, unlike the individual, owes that money to someone).

While stock and foil tally sticks were originally used to track debt, Henry I of England required that they be used for receipts for taxes in the 11th century.  The process followed the pre-existing use, where the stock follows the person who has given money, while the foil was retained by the exchequer as a receipt of money retained.  The continued use of this sort suggests that the basic principles of double entry accounting were  already known to some extent.  If tax liability is a debt owed, then the payment is a debit and one receives a stock, while the foil follows the money given.

It is my belief that the basic principles of double entry accounting were explored first with tally sticks and later, as literacy became somewhat more widespread, on paper.

What Accounting Systems are Designed to Do

Accounting systems are designed to do one thing only, to track who owes what to whom.  Even tracking of current assets is a part of that since all assets of a business are effectively owed to the owners.

This may sound overly simplistic but the anthropological assessment on the origin of money is that money itself arises as a way to quantify debt.  Debt pre-exists money systems, and all economies are powered by debt, and this is particularly noticeable in gift economies where debt, in the form of honor, is the primary currency.    Everywhere debt precedes payment, and everywhere debt precedes money.  Therefore not only is accrual-basis accounting better in terms of reporting, but it better represents what actually is happening economically.

Debits and Credits

In the 15th Century, Luca Pacioli wrote his now-famous book on arithmetic, including a section on double-entry accounting.  Pacioli did not invent the system.  Instead his description is that of the Venetian system which was already in use at the time.  In general, the design is indicative of accrual-based accounting however in part because assets include debts owed to the business.  This actually is clearer when looking at the Latin terms Pacioli uses in his descriptions and how these fit together,  Namely he uses the terms "debit" and "credit" to refer to financial units which are clearer in Latin than they are in English and much of our accounting terminology derives from his work.

Pacioli's use of debit and credit are specifically of distinct concepts, and when every accounting student is taught these are arbitrary, every accounting student is taught wrong.

In Latin, debit refers to something which is owed and indeed it leads to our modern English word debt (via Old French).  The word derives from early Latin roots meaning "to take away something you have" and so it denotes a loss of a possessory interest in something.

A credit is the opposite side of a debit.  A debit is something owed.  A credit (from credere, to believe or trust, related to "creed" in Modern English) is something entrusted to someone else or loaned to them.  This term denotes a continued possessory interest in something, even as it is entrusted to someone else.  So we can most simply translate debit and credit as debt and investment or loan, respectively.  Being opposites, a credit abates a debit and vice versa.

Also being opposite sides of the transaction every transaction inherently balances.  One person's debit must by nature correspond to someone else's credit.  By entering everything from the perspective of the counterparty, whether customer, vendor, or owner, the books will be guaranteed to balance, and this allows one to detect errors because the total intrinsic value of the business will remain 0.

For this reason both debits and credits have two distinct meanings.  One is to off-set the other (paying back a loan is a debit against the corresponding credit), and the other is to represent debts (debits) and assets entrusted to the business but possessed by others (credits).  Every type of account furthermore has a specific type of counter-party but these fall into two categories:  owners (equity, and change-in-equity accounts, namely accounts for tracking income and expenses) and non-owners (assets and liabilities).

From this point we can derive the normal balance of every account because we understand the basic structure and functions of the system:

  • Asset accounts track debt and debt payments by those who owe money to the business.  Therefore they use debits for positive balances.  Being debits, they can be used to pay off loans made to the business (credits) or investors (investments are credits).  The perspective is that of the debtor.
  • Liability accounts track loans and loan payments to those the business owes money to.  Therefore they use credits for positive balances.  The perspective is that of the lender.
  • Equity accounts track investments in a business which reflect the value of the business to the owners.  Therefore they use credits for positive balances.  The perspective is that of the owner.
  • Income accounts track positive changes in equity.  Therefore they use credits for positive balances.  The perspective is that of the owner.
  • Expense accounts track negative changes in equity.   Therefore they use debits for positive balances.  The perspective is that of the owner.

What Software Engineers can Learn from Accounting Systems

Most of the time, those of us who design and write software find that our approaches are relatively orderly but fragile.  Aspects of a system fail to support each other, and we basically add complexity to the system in order to hold it together.  Highly engineered systems are thus brittle, or to the extent that they are not, require layer upon layer of complexity in order to keep working.  These systems often cannot continue to be maintained properly once people have forgotten why certain design decisions were made in the first place.

In contrast, double entry accounting systems (particularly accrual-based systems), which probably arose organically during the Late Middle Ages until they became important enough for Pacioli to write about, is a highly evolved system.  The overall approach, while difficult to grasp at first, can be maintained without any understanding of the reasons behind the design decisions.  Accounting systems have further evolved from Pacioli's day, presumably through the same process they evolved before then.  People understand, in general terms, principles required to get meaningful information out of the system, are confronted by new problems, and respond by experimenting and sharing results, until new approaches take root.

One thing we as engineers can do is look to some of these highly evolved systems, and how they change over time, and recognize that they show us what may be a better way to create highly robust systems that tolerate and detect errors well.  In double entry accounting, we look to owners 'interest in the business vs the business's interest in everyone else's assets and make sure they are equal.  This adds redundancy in entering information but it also adds richness in reporting that is not possible otherwise.  Perhaps there are opportunities for things like this elsewhere.

Here, with double entry accounting, the perspective chosen, namely the value of a business to itself, is an easy one to check.  Such a business will inherently have no value to itself.  Choice of perspective makes some difficult problems (like catching data entry errors when tracking money) relatively simple to catch, locate, and correct.   Sometimes the most elegant solutions are not in what you do but how you look at things.  This is very clear when it comes to this specific sort of system.

The real challenge going forward in my view is how we look at distributed systems and what perspectives we can find which make these problems elegantly solvable.  As with double entry accounting, this will probably have to arise from looking at pre-computing methods, for example petty cash management as a basis for a guarantee of eventual consistency in a distributed transaction.  Current approaches like those adopted by the NoSQL community don't get us there.  Approaches that draw from our experiences doing non-distributed transactions well as well as paper forms of distributed transactions may, however provide something a lot more robust and usable.

Monday, August 6, 2012

Still pushing for 1.4 beta 1 by end of month

We are still pushing for LedgerSMB 1.4, beta 1 by the end of the month.  We have a lot of work to do to get there but are closing the gap fast.  I will put out a longer post at that time with a list of all of the improvements we have made, but for now I want to highlight only a few.
First, we have ditched tablefunc and gone to WITH RECURSIVE common table expressions, which means we now will require PostgreSQL 8.4 and higher.  Readers will recall a previous post discussing this in greater detail as well as the benefits we have seen.

One area I am particularly excited by is the new reporting framework.  This allows one to quickly and easily turn a stored procedure into a report using a common set of interface components.  Reports support subtotals on various criteria,  ordering of results by users clicking columns, and more.  Most code for specific reports is boilerplate code.  Our main modules do most of the work.  Some reports like the income statement will have to override this and supply their own interface components, but this is relatively rare.

Reports can be exported to CSV, ODS, and PDF files and contain identifying information so that one does not get confused as to where a report came from.  A future post will look inside our reporting engine.

Additionally files can be attached to persons and companies, which means that this goes for customers, vendors, employees, leads, etc.  This brings full-fledged CRM a step closer.  The files are stored in the database as bytea types.

The final feature I want to mention here is that projects and departments are being replaced by a system of reporting dimensions.  These reporting dimensions can be nested, so projects can now contain other projects, and departments can contain other departments.  Funds etc can be added by configuring the application rather than by customization.

This feature makes heavy use of common table expressions.  We can now check for business reporting units and descendants within a report.  This allows us to do more flexible reporting than we would be able to do without many of the features found first in PostgreSQL 8.4.

Thursday, August 2, 2012

Patterns and Anti-Patterns in Code Comments

Code commenting is something which takes a lot of introspection and practice to get right.  As a heads-up when I am looking at hiring someone, I will be asking about commenting style and if you can't talk intelligently about the topic, you won't get hired.  I wouldn't want you to just agree with me.  I would expect you to demonstrate you have thought about the issue enough to have your own opinions and reasons for thinking the way you do.

We started LedgerSMB as a fork of SQL-Ledger and one of the immediate challenges we had was that the only comments in SQL-Ledger were brief descriptions of what files did, copyright notices, and strings for translation or other meta-information actively used by the software.  Debugging uncommented code is not fun, and it took us a long time to get an acceptable number of comments and/or POD in place.   Over time, working in a collaborative environment, I have come to have very strong opinions on code commenting.

In this post I will pull examples from PostgreSQL's source files (using 9.1.2 because I have the source handy for that) as well as from LedgerSMB.

Comments are extremely important as they represent an important collaborative tool, but like all powerful tools, it can be misused.

Commenting Pitfalls and Anti-patterns

In general, when debugging an application we have to read the code, not the comments.  Sparse, helpful comments are very helpful and will be read.  Copious comments that appear to describe the inner workings of the code get ignored by necessity.  Being ignored, they are not updated with the code, and consequently  become out of date.  Three or four people work on a code section and eventually the comments and the code don't match.  This is a real problem and it is one reason why over-commenting needs to be avoided.

A second problem with this approach is that people put faith in comments, rather than code, to explain what the program is doing to other developers.  This can lead to unclear code.  In general if you have to describe how it works, and you can't find a better way to write it, at least do everyone a favor by flagging the section of code as FIXME so that the comment and the code will be read together and the explanation deleted as clarity emerges.

A third problem is the anti-pattern of magic comments which I have seen crop up in more than one place.  Comments are designed to be ignored by the program as a way to annotate code.  When you start turning them into code, individuals may not be able to maintain the files properly and may delete a magic comment by accident.  Similarly using database-level COMMENT ON statements to add info for programs throws off documentation tools and the like.  Don't do it.  Keep code and comments separate.  If you really must use magic comments, at least do us a favor and note clearly that they are important and must not be deleted.

Finally if there are too many comments in code, the comments will not get read and so helpful comments will get missed.

Alternatives to Comments (Use Them!)

Comments are not the only way to make code readable, and often they are not even the best.  It's important also to pay attention to things like whitespace, use blank lines to separate blocks that logically belong together, and otherwise organize the code well.  Additionally enforcing design patterns which include things like declaring all variable for a function or code block at the earliest possible opportunity are helpful.

Similarly care in variable names goes a long way to rendering code readable.  In an SQL query for example, table aliases should be abbreviations of the table name, not arbitrary letters.

Finally to the extent you can structure your code you can make it easier to read.  Design patterns and coding patterns help organize code and make it easier to read.  To the extent that the code is easy to read, comments are less necessary.  Again, comments shouldn't ever be necessary to explain how code works, but sometimes they are.  In general it's good to keep these minimal in frequency and flagged with a note that one recognizes that this section of the code is unclear.

The above three boil down to the mentality of writing code with two distinct intended audiences:  the computer and other coders.

The Documentation Comment Pattern

Functions should be documented.  This helps programmers understand what a function is supposed to do but it has a number of more important functions as well.  By documenting a function call, you establish an API.  The code is expected to conform to the API, not the other way around.  These code comments are important but the code implements what is described, not the other way around.  It's hard to think of these as comments because they do not annotate the code per se, but rather describe the interfaces for interacting with it.

In most languages, we place the documentation at the front of the file.  In PostgreSQL with stored procedures, however, we have to put the comments after if we want to use COMMENT ON and therefore allow documentation tools to work properly.  We use POD for Perl, and COMMENT ON for SQL, and so these are distinguished from the other types of comments listed below in accordance with the literate programming pattern.

These comments may be extensive or not but should be seen as specifications rather than comments.


The Section Heading Comment Pattern

In a function or other code block of significant length, debugging requires being able to find a relevant section of code quickly.  Comments can help organize code  and make it easy to find a given section.

For example, in the PostgreSQL code, it is common to see a comment stating:

/* local functions */

This is very helpful.  If you know the header is there and you want a list of local functions that are declared for function re-use purposes, you find that definition quickly.  if you need to add a function name, it is easy to add it where it will be noticed not only by the compiler but also by fellow programmers.  The whole goal of these comments is just to help enforce organization of code and help the next programmer find the appropriate section of code quickly.

In general, my experience is that, like section headers in a blog post, these should be short, concise, and descriptive.


The Footnote Comment Pattern

A footnote comment is one which  annotates the code, by providing descriptions of why a given approach was taken, references to other works or algorithms used, or the like.  In general, my experience is that these comments should be short but provide information that cannot be deduced from the code.  For example one might  state why a given approach was taken or allude to an external document or standard for more information.

I prefer to inline my footnote comments because then it is clear exactly what the comment refers to, but other people may disagree.  For example the following comment from analyzejoins.c is a good footnote comment and not inlined (it explains the use of a goto statement):

/*
 * Restart the scan.  This is necessary to ensure we find all
 * removable joins independently of ordering of the join_info_list 
 * (note that removal of attr_needed bits may make a join appear
 * removable that did not before).      Also, since we just deleted the
 * current list cell, we'd have to have some kluge to continue the
 * list scan anyway.
 */

The comment clearly and concisely describes why a given statement is there.  It explains what it does to but only as necessary to get into why it is necessary.

The Warning Comment Pattern

Sometimes comments can and should be used to warn programmers about a certain segment of code.  For example in LedgerSMB we have the following comment near the top of the admin.sql which defines functions for user management.  Because user management functions are not parameterized we have to build them through string interpolation and run them with elevated privileges, which leads to dangers of in-stored-proc SQL injection as a database superuser.

-- README:  This module is unlike most others in that it requires most functions
-- to run as superuser.  For this reason it is CRITICAL that the following
-- practices are adhered to:
-- 1:  When using EXECUTE, all user-supplied information MUST be passed through
--     quote_literal.
-- 2:  This file MUST be frequently audited to ensure the above rule is followed
--
-- -CT

Similarly inside the admin__save_user function we include the comment:

-- WARNING TO PROGRAMMERS:  This function runs as the definer and runs 
-- utility statements via EXECUTE. 
-- PLEASE BE VERY CAREFUL ABOUT SQL-INJECTION INSIDE THIS FUNCTION.

Of course this is only required because the utility statements in question (like CREATE ROLE) are not parameterized and so parameterized queries are not an option.

The function of these comments is to call attention to pitfalls specific to certain blocks of code.  In this case we are warning about security implications.  In others we are warning about potential other problems. 

TODO, XXX, and FIXME comments are all very helpful and part of this pattern.  Typically I find it useful to include sections that need to be in caps in caps where a warning is critical, but otherwise leave it lower case.

Signed Comments

One thing we have found helpful in a collaborative environment is to sign comments.   This is not something we have seen people do elsewhere but we have found we get a lot of benefit from it.  In a typical woven code approach (below), the idea is that you get an autonomous discourse which is the code, documentation,and comments all together, but as things change, the discourse becomes less autonomous, as it should.  People may see a TODO or a FIXME and have different ideas as to what should be done.  Therefore signing a comment fills a number of rolls.

First it provides a clear record as to who one should talk to about a possible code change, and helps give people credit for their work.  However beyond this it sets up individuals as people who are publicly thinking about problems in the code and this provides some additional conversation points.  Finally a signed comment comes across as less authoritative than an unsigned one and so it allows for dialog in the comments between individuals.  So consider this:

# we need to add checks here for .... --CT

# As we move this to Moose, the problem may go away. -- YT

The above dialog of course is fictional but there are examples in the LedgerSMB code where you can see this sort of dialog develop.  It becomes helpful to a programmer because they can see what different programmers are thinking about an issue and what sorts of solutions may be available.  Also each programmer can speak for him/herself and doesn't have to amend the master, autonomous discourse in order to do so.

The Woven Code Pattern

Borrowed in part from Donald Knuth's concept of literate programming, this pattern involves writing the documentation and code as a single work intended to be read by other people.  Typically when I employ this I write my Perl POD first, then annotate the POD with code, and then add non-POD comments as needed to draw other programmers' attention to some things.   In this pattern four things are the case:
  1. Documentation is Authoritative and Done First
  2. Code Implements and Explains Documentation
  3. Footnote/Warning Comments Annotate Code, but only as needed.
  4. The above three components are woven together to create a text for the next programmer.  All components of that text evolve together.
Conclusions

Comments are essential to long-term maintainability and  collaboration in software development.  In general, I have found that they are more helpful when used to annotate, rather than describe, the source code.  The source code should be able to speak for itself but is necessarily an incomplete glimpse into the mind of the programmers involved.  Comments bridge this gap, but poorly used comments get in the way more than they help.

Any others?

What patterns do you like to push for when commenting in an environment where others will read your code and comments?

Saturday, July 28, 2012

One advantage of Logic in the DB: PHP classes for LedgerSMB coming soon!

The perpetual argument over logic in the db will continue forever, but here's one advantage that is often overlooked:  stored procedures provide a powerful way to integrate programs written in different environments.

Case in point:  Yesterday when I got tired of staring at Perl code, I wrote some basic PHP classes to provide integration logic for LedgerSMB.  The basic interface which performs query mapping functions, took me a couple of hours including debugging, despite the fact that I haven't programmed in PHP since 4.2 was current, and includes an additional class for retrieving/saving company records as well.  Not everything works yet but this will probably be finished up today.

These classes will make writing integration logic with portions of the software which have been moved over to stored procedures quite easy, and such code that calls stored procedures will be provably free of SQL injection and privilege escalation.

I haven't decided where to put this, whether in the main LedgerSMB project or in another Sourceforge project but it is coming soon.  Once these are working I intend to teach myself enough Java to write the same in that language,

Long-run there is a lot of boilerplate code that will probably be able to be generated by code generators in all these languages.  The code generators will eventually have to query system catalogs, and some custom application catalogs.  This will minimize the amount of code that will have to be written by hand.

Friday, July 20, 2012

On Long Queries/Stored Procedures

In general, in most languages, programmers try to keep their subroutines down to a couple screens in size.  This helps, among other things, with readability and ease at debugging.  Many SQL queries are significantly longer than that.  I have queries which are over 100 lines long in LedgerSMB, and worked on debugging queries that are more than 200 lines long.  In general, though, the maximum length of a query is not a problem if certain practices are followed.  This post describes why I think SQL allows for longer procedures and what is required to maintain readibility.

Why Long Queries Aren't a Problem Per Se

In a typical programming language, there isn't an enforced structure to any subroutines.  What this means is as a subroutine becomes longer, maintaining internal patterns and an understanding of state becomes more difficult.  SQL queries themselves, however, are defined by their structure.  For example, a standard select statement (excluding common table expressions) includes the following parts in order:

  1. Returned column list
  2. Starting relation
  3. Join operations
  4. Filters
  5. Aggregation criteria
  6. Aggregation filters
  7. Postprocessing (Ordering, limits, and off-set)
The order of these elements are not interchangeable.  I can't put my returned column list at the end, or my join operations at the front.  Therefore in a 100 line query, chances are you know initially what is being returned first, and can work onward to see why the value is what it is.  Generally also you will have an idea of likely causes before you get started.  Does this look like a join projection problem?  Like a misbehaving filter?  Bad aggregation?  Ok, we know where to look for logic.  Ok, now we have a block, and an idea of what to look for.  It's pretty quick to figure out which lines are likely at issue.

Because of the structure, it is pretty easy to dive into even a very long query and figure out exactly where the problems are quickly.  Maintainability is not dependent on length or overall complexity.

Moreover if you have common table expressions, it is easy to jump back to the beginning, where these are defined, and reference these as needed.

A second difference is that SQL statements work with state which is typically assumed to be unchanging for purposes of the operation.  With rare exceptions, the order of execution doesn't matter (order of operations however does).  Consequently you don't have to read line-by-line to track state.

In essence debugging an SQL statement is very much like searching a b-tree, while debugging Perl, Python, or C is very much like traversing a singly linked list.

What Can Be a Problem

Once I spent several days helping a customer troubleshoot a long, complex query.  The problem turned out to be a bad filter parameter, but we couldn't tell that right away.  The reason was that the structure of the query had decayed a bit and this made maintenance difficult.

The query was not only long, but it was also difficult to understand, because it didn't conform to the above structure.  The problem in that case was the use of many inline views to create a cross-tab-type report.

If you can't understand a long query, or if you don't know immediately where to look, it is hard to troubleshoot these.

Best Practices

The following recommendations are about keeping long queries well-structured.   Certain features of the SQL language are generally to be avoided more as queries become longer, and other features should be used carefully.
  • Avoid inline views.  Ok, sometimes I use inline views too on longer queries, but usually these are well-tested units in their own right, and re-used elsewhere.  These should probably be moved into defined views, or CTE's if applicable.
  • Avoid union and union all in long queries.  These complicate query maintenance in a number of ways.  It's better to move these to small testable units, like a defined view based on a shorter query or a common table expression.
  • In long stored procedures, keep your queries front and center, and move as much logic as is reasonable into them.
  • Avoid implicit joins, which work by doing cross-joins and then placing the filter condition in the result.  Join logic should be separate from filter logic.
What do you think?  What practices do you find helpful?

Tuesday, July 17, 2012

Why LedgerSMB uses Moose. An intro for PostgreSQL folks.

In LedgerSMB 1.4 we are moving to using a Perl object system called Moose for new code.  This post will discuss why we are doing so, what we get out of it, etc.  For those new to Moose this may serve as a starting point to decide whether to look further into this object framework.

To start with, however, we will need to address our overall strategy regarding data consistency and accuracy.  

Why we Use Database Constraints Aggressively

Before getting into Moose specifically it's important to re-iterate why we use database constraints aggressively in LedgerSMB.

In general you can divide virtually all application bugs into a few categories which fall within two major classifications:

  • State Errors
  • Execution Errors
State errors involve not only transient state problems but also stored information.  In other words if the application processes meaningless information, the results will be similarly meaningless.  Summarized: garbage in, garbage out.  Detecting garbage, and preventing garbage from being persistently stored is thus important.  Typically a specific misbehavior can be a cascading failure from an undetected bug regarding storage of information.  This is particularly important to avoid in an accounting application.

Database constraints allow us to declare mathematically the constraints of meaningful data and thus drastically reduce the chance of state errors occurring in the application.  Foreign keys protect against orphaned records, type constraints protect against invalid data, and check constraints can be used to ensure data falls within meaningful parameters.  NOT NULL constraints can protect against necessary but missing information.

The other type of error is an execution error.  These can be divided into two further categories:  misdirected execution (confused deputy problems and the like) and bad execution (cases where the application takes the right information and does the wrong things with it).

Any reduction in state errors has a significant number of benefits to the application.  Troubleshooting is simplified, because the chances of a cascade from previous data is reduced.  This leads to faster bugfixes and a more robust and secure application generally.  Not only are the problems simplified but the problems that remain are reduced.  We see this as a very good thing.  While it is not necessarily a question of alternatives, testing cannot compare to proof.

One really nice thing about PostgreSQL is the very rich type system and the ability to add very rich constraints against those types.  The two of those together makes it an ideal database for this sort of work.


Enter Moose

Recently, Perl programmers have been adopting a system of object-oriented programming based on metaclasses and other concepts borrowed from the LISP world.  The leading object class that has resulted is called Moose, and bills itself as a post-modern object system for a post-modern language (Perl).  Moose offers a large number of important features here including the following, which we consider to be the most important:
  • A rich type system for declaring object properties and constraints
  • Transparent internal structures
  • Automatic creation of constructors and accessors
  • Method modifiers.
These four benefits bring to the Perl level the ability to add the same sort of proof of state that the database level has traditionally had.  We can be sure that a given attribute falls within meaningful range of values and we can be sure everything else just works.

Brief Overview of Useful Type Features

In plain old Perl 5 we would normally build accessors and constructors to check specific types for sanity.  This is the imperative approach to programming.  With Moose we do so declaratively and everything just works.

For example we can do something like this, if we want to make sure the value is an integer:

has location_class => (is => 'rw', isa => 'Int');

This would be similar to having a part of a table definition in SQL being:

 location_class int,

 This tells Moose to create a constructor that's read/write, and check to make sure the value is a valid Int.

We can also specify that this is a positive integer:

subtype 'PosInt',  as 'Int', where { $_ > 0 };

has location_class => (is => 'rw', isa => 'PosInt');

This would be similar to using a domain:

CREATE DOMAIN posint AS int check(VALUE > 0)

Then the table definition fragment might be:

location_class posint,

But there is a huge difference.  In the SQL example, the domain check constraint (at least in PostgreSQL) is only checked at data storage.  If I do:

select -1::posint;

I will get -1 returned, not an error.  Thus domains are useful only when defining data storage rules.  The Moose subtype however, is checked on every instantiation.  It defines the runtime allowed values, so any time a negative number is instantiated as a posint, it will generate an error.  This then closes a major hole in the use of SQL domains and allows us to tighten up constraints even further.

So here we can simply specify the rules which define the data and the rest works.  Typical object oriented systems in most languages do not include such a rich declarative system for dealing with state constraints.

The type definition system is much richer than the above examples allow and we can require that attributes belong to specific classes, specify default values, when the default is created and many other things.  Moose is a rich system in this regard.

Transparent Internal Structures

Moose treats objects as blessed references to hash tables (in Perl we'd call this a hashref), where every attribute is simply listed by name.  This ensures that when we copy and sanitize data for display, for example, the output is exactly expected.  Consequently if I have a class like:

package location;

has location_class => (is => 'rw', isa => 'Int');
has line_one =>  (is => 'rw', isa => 'Str');
has line_two => (is => 'rw', isa => 'Maybe[Str]');
has line_three =>  (is => 'rw', isa => 'Maybe[Str]');
has city =>  (is => 'rw', isa => 'Str');
has state =>  (is => 'rw', isa => 'Str');
has zip =>  (is => 'rw', isa => 'Maybe[Str]');
has country_name =>  (is => 'rw', isa => 'Maybe[Str]');
has country_id =>  (is => 'rw', isa => 'Int');

In that case, when we go to look at the hash, we could print values from the hash in our templates.  Our templating engines can copy value for value the resulting hash, escape it (in the new hash) for the format as needed, and then pass that on to the templating engine.  This provides cross-format safety that accessor-based reading of attributes would not provide.

In other words we copy these as hashrefs, pass them to the templates and these just work.

Accessors, Constructors, and Methods

Most of the important features here follow from the above quite directly.  The declarative approach is used to create constructors and accessors, and this provides a very different way to think about your code.

Now Moose also has some interesting features regarding methods which are useful in integrating LedgerSMB with other programs.  These include method modifiers which allow you to specify code to run before, instead of, or after functions.  These can take the place of database triggers on the Perl level.

Pitfalls

There are two or three reasons folks may choose not to use Moose, aside from the fact that it does have some overhead.

The first is complexity.  Moose has a lot of features and learning how to program effectively in Moose takes some time, though this is reduced by approaching it from a database perspective.

The second is that sometimes it is tempting to look into the raw data structure directly and fiddle with it, and if you do this then the proofs of accuracy are invalid.  This is mitigated by the use of correct controls on the database level.

Features we are Still Getting Used To

This isn't to say we are Moose experts already.  Moose has a number of concepts we haven't started using yet, like roles, which add cross-class functionality orthogonal to inheritance and which are highly recommended by other Moose programmers.

There are probably many other features too that will eventually come to be indispensable but that we aren't yet excited about.

Future Steps

On the LedgerSMB side, long-run, I would like to move to creating our classes directly using code generators from database classes.  We could query system catalogs for methods as well.  This is an advanced area we probably won't see much of for a while.

It's also likely that roles will start to be used, and perhaps DBObject will become a role instead of an inheritance base.

Update:

Matt Trout has pointed out that setting required => 0 is far preferable to Maybe[] and helped me figure out why that wasn't working before.  I agree.  Removing the Maybe[] from the type definitions would be a great thing.  Thanks Matt!

Wednesday, July 11, 2012

PostgreSQL CTEs and LedgerSMB

LedgerSMB trunk (which will become 1.4) has moved from connectby() to WITH RECURSIVE common table expressions (CTE's).    This post describes our experience, and why we have found that CTE's are an extremely useful way to write queries and why we are moving more and more towards these.  We have started using CTE's more frequently in place of inline views when appropriate as well.

CTEs are first supported in PostgreSQL 8.4.  They represent a way to write a subquery whose results remain stable for the duration of the query.  CTE's can be simple or recursive (for generating tree-like structures via self-joins).  the stability of CTEs both adds opportunities for better tuning a query and performance gotchas, and it is important to remember that the optimizer cannot correlate expected results from a CTE with the rest of the query to optimize the CTE (but presumably can go the other way).

The First Example

The simplest example would be our view, "menu_friendly" which shows the structure and layout of the menu.  The menu is generated using a self-join and this view returns the whole menu.

CREATE VIEW menu_friendly AS
WITH RECURSIVE tree (path, id, parent, level, positions) 

AS (select id::text as path, id, parent, 0 as level, position::text
      FROM menu_node where parent is null
     UNION
    select path || ',' || n.id::text, n.id, n.parent, t.level + 1,
           t.positions || ',' || n.position
      FROM menu_node n
      JOIN tree t ON t.id = n.parent)
SELECT t."level", t.path,
       (repeat(' '::text, (2 * t."level")) || (n.label)::text) AS label,
        n.id, n."position"
   FROM tree t
   JOIN menu_node n USING (id)
  ORDER BY string_to_array(t.positions, ',')::int[];


This replaced an older view using connectby() from the tablefunc module in contrib:

CREATE VIEW menu_friendly AS
SELECT t."level", t.path, t.list_order,
       (repeat(' '::text, (2 * t."level")) || (n.label)::text) AS label,
        n.id, n."position"
  FROM (connectby('menu_node'::text, 'id'::text, 'parent'::text,
                  'position'::text, '0'::text, 0, ','::text
        ) t(id integer, parent integer, "level" integer, path text,
        list_order integer)
   JOIN menu_node n USING (id));


The replacement query is longer, it is true,  However it has a number of advantages.  The biggest is that we no longer have to depend on a contrib module which may or may not come with PostgreSQL (most Linux distributions package these in a separate package) and where installation methodology may change (as it did in PostgreSQL 9.1).

I also think there is some value in having the syntax for the self-join a bit more obvious rather than having to run to the tablefunc documentation every time one wants to check.   The code is clearer and this adds value too.

I haven't checked performance between these two examples, because this isn't very performance-sensitive.  After all it is only there for troubleshooting menu structure, and it is only a set of read operations.  Given other tests however I would not expect a performance cost.


Better Performance

LedgerSMB generates the menu for the tree-view in a stored procedure called menu_generate() which takes no arguments.  The 1.3 version is:

CREATE OR REPLACE FUNCTION menu_generate() RETURNS SETOF menu_item AS
$$
DECLARE
        item menu_item;
        arg menu_attribute%ROWTYPE;
BEGIN
        FOR item IN
                SELECT n.position, n.id, c.level, n.label, c.path,
                       to_args(array[ma.attribute, ma.value])
                FROM connectby('menu_node', 'id', 'parent', 'position', '0',
                                0, ',')
                        c(id integer, parent integer, "level" integer,
                                path text, list_order integer)
                JOIN menu_node n USING(id)
                JOIN menu_attribute ma ON (n.id = ma.node_id)
               WHERE n.id IN (select node_id
                                FROM menu_acl
                                JOIN (select rolname FROM pg_roles
                                      UNION
                                     select 'public') pgr
                                     ON pgr.rolname = role_name
                               WHERE pg_has_role(CASE WHEN coalesce(pgr.rolname,
                                                                    'public')
                                                                    = 'public'
                                                      THEN current_user
                                                      ELSE pgr.rolname
                                                   END, 'USAGE')
                            GROUP BY node_id
                              HAVING bool_and(CASE WHEN acl_type ilike 'DENY'
                                                   THEN FALSE
                                                   WHEN acl_type ilike 'ALLOW'
                                                   THEN TRUE
                                                END))
                    or exists (select cn.id, cc.path
                                 FROM connectby('menu_node', 'id', 'parent',
                                                'position', '0', 0, ',')
                                      cc(id integer, parent integer,
                                         "level" integer, path text,
                                         list_order integer)
                                 JOIN menu_node cn USING(id)
                                WHERE cn.id IN
                                      (select node_id FROM menu_acl
                                        JOIN (select rolname FROM pg_roles
                                              UNION
                                              select 'public') pgr
                                              ON pgr.rolname = role_name
                                        WHERE pg_has_role(CASE WHEN 

                                                          coalesce(pgr.rolname,
                                                                    'public')
                                                                    = 'public'
                                                      THEN current_user
                                                      ELSE pgr.rolname
                                                   END, 'USAGE')
                                     GROUP BY node_id
                                       HAVING bool_and(CASE WHEN acl_type
                                                                 ilike 'DENY'
                                                            THEN false
                                                            WHEN acl_type
                                                                 ilike 'ALLOW'
                                                            THEN TRUE
                                                         END))
                                       and cc.path like c.path || ',%')
            GROUP BY n.position, n.id, c.level, n.label, c.path, c.list_order
            ORDER BY c.list_order

        LOOP
                RETURN NEXT item;
        END LOOP;
END;
$$ language plpgsql;


This query performs adequately for users with lots of permissions but it doesn't do so well when a user has few permissions.  Even on decent hardware the query may take several seconds to run if the user only has access to items within one menu section.  In many cases this isn't acceptable performance but on PostgreSQL 8.3 we don't have a real alternative outside of trigger-maintained materialized views.  For PostgreSQL 8.4, however, we can do this:

CREATE OR REPLACE FUNCTION menu_generate() RETURNS SETOF menu_item AS
$$
DECLARE
        item menu_item;
        arg menu_attribute%ROWTYPE;
BEGIN
        FOR item IN
               WITH RECURSIVE tree (path, id, parent, level, positions)
                               AS (select id::text as path, id, parent,
                                           0 as level, position::text
                                      FROM menu_node where parent is null
                                     UNION
                                    select path || ',' || n.id::text, n.id,
                                           n.parent,
                                           t.level + 1,
                                           t.positions || ',' || n.position
                                      FROM menu_node n
                                      JOIN tree t ON t.id = n.parent)
                SELECT n.position, n.id, c.level, n.label, c.path, n.parent,
                       to_args(array[ma.attribute, ma.value])
                FROM tree c
                JOIN menu_node n USING(id)
                JOIN menu_attribute ma ON (n.id = ma.node_id)
               WHERE n.id IN (select node_id
                                FROM menu_acl acl
                          LEFT JOIN pg_roles pr on pr.rolname = acl.role_name
                               WHERE CASE WHEN role_name
                                                           ilike 'public'
                                                      THEN true
                                                      WHEN rolname IS NULL
                                                      THEN FALSE
                                                      ELSE pg_has_role(rolname,
                                                                       'USAGE')
                                      END
                            GROUP BY node_id
                              HAVING bool_and(CASE WHEN acl_type ilike 'DENY'
                                                   THEN FALSE
                                                   WHEN acl_type ilike 'ALLOW'
                                                   THEN TRUE
                                                END))
                    or exists (select cn.id, cc.path
                                 FROM tree cc
                                 JOIN menu_node cn USING(id)
                                WHERE cn.id IN
                                      (select node_id
                                         FROM menu_acl acl
                                    LEFT JOIN pg_roles pr
                                              on pr.rolname = acl.role_name
                                        WHERE CASE WHEN rolname
                                                           ilike 'public'
                                                      THEN true
                                                      WHEN rolname IS NULL
                                                      THEN FALSE
                                                      ELSE pg_has_role(rolname,
                                                                       'USAGE')
                                                END
                                     GROUP BY node_id
                                       HAVING bool_and(CASE WHEN acl_type
                                                                 ilike 'DENY'
                                                            THEN false
                                                            WHEN acl_type
                                                                 ilike 'ALLOW'
                                                            THEN TRUE
                                                         END))
                                       and cc.path::text
                                           like c.path::text || ',%')
            GROUP BY n.position, n.id, c.level, n.label, c.path, c.positions,
                     n.parent
            ORDER BY string_to_array(c.positions, ',')::int[]
        LOOP
                RETURN NEXT item;
        END LOOP;
END;
$$ language plpgsql;


This function is not significantly longer, it is quite a bit clearer, and it performs a lot better.  For users with full permissions it runs twice as fast as the 1.3 version, but for users with few permissions, this runs about 70x faster.  The big improvement comes from the fact that we are only instantiating the menu node tree once.

So not only do we have fewer external dependencies now but there are significant performance improvements.


A Complex Example

CTE's can be used to "materialize" a subquery for a given query.  They can also be nested.  The ordering can be important because this can give you a great deal of control as to what exactly you are joining.

I won't post the full source code for the new trial balance function here.  However, the main query, which contains a nested CTE.

Here we are using the CTE's in order to achieve some stability across joins and avoid join projection issues, as well as creating a tree of projects, departments, etc (business_unit is the table that stores this).

The relevant part of the stored procedure is:

     RETURN QUERY
       WITH ac (transdate, amount, chart_id) AS (
           WITH RECURSIVE bu_tree (id, path) AS (
            SELECT id, id::text AS path
              FROM business_unit
             WHERE parent_id = any(in_business_units)
                   OR (parent_id = IS NULL
                       AND (in_business_units = '{}'
                             OR in_business_units IS NULL))
            UNION
            SELECT bu.id, bu_tree.path || ',' || bu.id
              FROM business_unit bu
              JOIN bu_tree ON bu_tree.id = bu.parent_id
            )
       SELECT ac.transdate, ac.amount, ac.chart_id
         FROM acc_trans ac
         JOIN (SELECT id, approved, department_id FROM ar UNION ALL
               SELECT id, approved, department_id FROM ap UNION ALL
               SELECT id, approved, department_id FROM gl) gl
                   ON ac.approved and gl.approved and ac.trans_id = gl.id
    LEFT JOIN business_unit_ac buac ON ac.entry_id = buac.entry_id
    LEFT JOIN bu_tree ON buac.bu_id = bu_tree.id
        WHERE ac.transdate BETWEEN t_roll_forward + '1 day'::interval
                                    AND t_end_date
              AND ac.trans_id <> ALL(ignore_trans)
              AND (in_department is null
                 or gl.department_id = in_department)
              ((in_business_units = '{}' OR in_business_units IS NULL)
                OR bu_tree.id IS NOT NULL)
       )
       SELECT a.id, a.accno, a.description, a.gifi_accno,
         case when in_date_from is null then 0 else
              CASE WHEN a.category IN ('A', 'E') THEN -1 ELSE 1 END
              * (coalesce(cp.amount, 0)
              + sum(CASE WHEN ac.transdate <= coalesce(in_date_from,
                                                      t_roll_forward)
                         THEN ac.amount ELSE 0 END)) end,
              sum(CASE WHEN ac.transdate BETWEEN coalesce(in_date_from,
                                                         t_roll_forward)
                                                 AND coalesce(in_date_to,
                                                         ac.transdate)
                             AND ac.amount < 0 THEN ac.amount * -1 ELSE 0 END) -
              case when in_date_from is null then coalesce(cp.debits, 0) else 0 end,
              sum(CASE WHEN ac.transdate BETWEEN coalesce(in_date_from,
                                                         t_roll_forward)
                                                 AND coalesce(in_date_to,
                                                         ac.transdate)
                             AND ac.amount > 0 THEN ac.amount ELSE 0 END) +
              case when in_date_from is null then coalesce(cp.credits, 0) else 0 end,
              CASE WHEN a.category IN ('A', 'E') THEN -1 ELSE 1 END
              * (coalesce(cp.amount, 0) + sum(coalesce(ac.amount, 0)))
         FROM account a
    LEFT JOIN ac ON ac.chart_id = a.id
    LEFT JOIN account_checkpoint cp ON cp.account_id = a.id
              AND end_date = t_roll_forward
        WHERE (in_accounts IS NULL OR in_accounts = '{}'
               OR a.id = ANY(in_accounts))
              AND (in_heading IS NULL OR in_heading = a.heading)
     GROUP BY a.id, a.accno, a.description, a.category, a.gifi_accno,
              cp.end_date, cp.account_id, cp.amount, cp.debits, cp.credits
     ORDER BY a.accno;


This query does a lot including rolling balances froward from checkpoints (which also effectively close the books), pulling only transactions which match specific departments or projects, and more.


Conclusion

We have found the CTE to be a tool which is hard to underrate in importance and usefulness.  They have given us maintainability and performance advantages, and they are very flexible.  We will probably move towards using more of them in the future as appropriate.