A talk given by Ann Harrison at the Open Source Database Conference in Tokyo, Japan, February 2002
The goal of the open source database community is - or should be - to demonstrate that our products are a reliable alternative to commercial databases, not just a cost-effective solution. We don't compete with each other; we compete with Oracle and Microsoft SQL Server, Informix, Sybase, SQLBase, DB2, Solid, Ingres and the dozens of other commercial databases. Organizations that use SQLBase and those that use Oracle have different needs and expectations from their databases. As they begin to look at open source alternatives, they will look for different features there too.
In an ideal world, there would be one open source database that was simple, fast, transaction oriented, easy to use, included a complete implementation of SQL-99 plus all the extra features of all the major commercial systems. In fact, we can't even agree on which features are desirable, let alone organize such a massive project with volunteer developers. What we can do is learn from each other, borrow technology, and improve our products quickly. At the same time, we can insure that our market is aware of the depth and breadth of the open source database offerings.
To that end, I would like to introduce Firebird and attempt to describe some of its distinctive features. Firebird is a fork of InterBase® Open Edition [1]. InterBase is a commercial relational database that has been in use for over 15 years at millions of companies, large and small. The major features of InterBase are its portability, small footprint, ease of administration, rich implementation of standard SQL, non-blocking concurrency control, and its "active database" features. InterBase is distributed both as a stand-alone data manager and as a part of the Delphi® developers kit.
In December of 1999, Borland Software Corporation, owners of the copyright to InterBase, decided to release the database as an open source product. At that time, everyone assumed that all subsequent versions of InterBase would be open source. During the confusion around the time that the sources were released, a group of open source developers created a fork, with the intention of reuniting with InterBase when that project stabilized. Unfortunately, Borland shortly made it clear that InterBase would be open source, but not an open project, and that their major focus would be on future commercially licensed versions.
In December of 2001, Borland released a new version of InterBase, available only under commercial license. The new features in that release have not been added to the public source tree. As an open source project, InterBase has died, leaving Firebird to explore, enhance, and explain the architecture of the product.
The Firebird project is now eighteen months old. We started with raw sources, without any source-level documentation, without a test system or user documentation, and without a working build system. Thanks to the tireless efforts of developers like Mark O'Donohue and the assistance of former InterBase developers, we soon had build scripts that worked on Linux and on Windows. We began fixing some of the more egregious bugs, especially those bugs that were interfering with our own development work. At the same time we discussed the future direction for the product and determined that the most necessary change was a better implementation of threads. To make that possible, we decided to convert the code base to C++. Thus, for most of the past year, the Firebird project has been working in two parallel directions: one group migrating to the new C++ version while another produced a very reliable V1.0.
What are the features of Firebird that make it an interesting addition to the open source community?
One is portability. This may not seem to be a serious issue to those who understand that there is one true operating system - Linux. For those who are developing applications that must run in other environments, portability is a major issue. Firebird is portable in part because the code is entirely C, now C++. The code is written to the requirements of gcc and several proprietary compilers. Generally speaking, operating specific code like the I/O routines, memory mapping, and inter-process communication is isolated to separate modules. That convention has broken down slightly and I hope to see it revived in Version 2. So far, we have ports for Windows, Linux, Solaris (two kinds), HP/UX, AIX, MacOSX, and SCO. Databases can be moved between platforms easily. Windows clients can take advantage of the performance and cost advantages of a Linux server.
Another Firebird feature is its small footprint. The server is about 1Mb before it starts allocating dynamic memory and it does not allocate much. That's a far cry from the 64Kb databases I knew on DEC PDP-11 computers, but it also does a great deal more. Part of the reason for its size is that it was designed to run on the machines that were current 15 years ago, as were most of the commercial databases. Part of the reason is that the engine is tightly integrated - in the words of the Mythical Man Month [2] , InterBase was a "surgical team" project. By their nature, most open source projects use the "hog butcher" approach, breaking the whole into components with well-defined interfaces that can be worked on separately.
A related feature is ease of administration. Designing and write a database management system is fun, at least for those of us with that sort of personality. Making it easy to use is a nuisance, and generally and after thought. Since InterBase was designed as a commercial product and sold with three months of free support, making it easy to install and manage was important to the bottom line. Firebird continues that tradition, having simple install procedures, an on-line backup, no required off-line maintenance, and, more controversially, very few tuning parameters.
Everyone knows that databases need tuning. Nearly every benchmark reflects a two- or three-fold improvement from the database as installed to the database as tuned by the company that wrote it. That is a great way to sell consulting services, but it seriously interferes with distributing applications based on a database if the customer has to buy a support contract not only from the application developer, but also from the database developer. Ideally, the customer buying an accounting package should not need to know that the database exists.
Most databases require tuning to insure that memory is allocated appropriately between the various functions. Firebird allows you to set the maximum memory used and the number of database pages that should be held in cache. The software manages other memory issues. The maximum amount of memory is a relic from the days when a machine with 10Mb of RAM was normal. The size of the page cache depends on the type of processing being done and is the one tuning parameter that must be set by experimentation.
Another area of tuning is data placement, both the placement of tables and the placement of records within a database. Placement control allows the database administrator to be at fault when there is bad locality of reference or head contention. Firebird handles placement differently. All data is stored in a single file, or a sequence of files. Even multi-file databases have no table placement control; they are simply a mechanism for spreading the database across disks.
Data is located through a three-level lookup tree, consisting of pointer pages, data pages, and records on page. A record identifier is the pointer page sequence number, the offset on the pointer page of the data page number, and the offset on the data page of the pointer to the record. When the database is restored from a backup, all pages for a table will be clustered. Otherwise they are allocated throughout the database file(s), using pages that have been allocated and released first and then allocating new pages at the end of the file(s).
Nor does Firebird have any record placement within a table. Other databases cluster records based on an indexed value, so that records likely to be read together are stored together. Access on any other index is significantly slower. Firebird's indexed access is structured differently. When a where clause can be resolved with an index, Firebird first finds the identifiers of all the matching records and stores them in a sparse bitmap [3]. Because the bitmap is ordered by record identifier and the record identifier reflects the storage location of the record, all records on any particular page will be read at once. The result is even lookup times on all indexes.
Firebird's indexes are very dense because they compress both the prefix and the suffix of each key. Suffix compression is simply the elimination of trailing blanks or zeros, depending on the data type. Suffix compression is performed on each segment of a segmented key. Prefix compression removes the leading bytes that match the previous key. Thus a duplicate value has no key stored at all. Dense storage in indexes minimizes the depth of the btrees, eliminating the advantage of other index types for most data. Geographic data is another issue, but that is not one of Firebird's areas of focus. Other open source databases would be a better choice for largely geographic data.
Another area where Firebird reduces the difficult of administering a database is in its handling of metadata. Most metadata operations can be performed on a live database. Columns can be added, modified, dropped, and reordered without unloading or reloading their data. If you add a column to a table, you may want it to appear in the middle of the record. When you add the column, you can specify its position within the record and, if necessary, alter the positions of other columns to make room for the new column.
The column name, data type, length, default value, and constraints can all be altered.
From its commercial heritage, Firebird also has good support for standard SQL. Firebird implements most of the first two levels of SQL-89 and SQL-92, some features from SQL-99. In particular, Firebird supports inner join, left, right, and full outer joins, and unions including unions in views. It supports the group by and having clauses of the select statement. It supports direct updates of updateable views and triggered updates of other views. The select list can contain subqueries. Subqueries can also appear in where clauses and in the IN expression. Firebird does not support the use of subqueries in the FROM clauses, but does accept procedures in that clause, which provides an exact emulation.
Even though many of the variants of a SQL statement are redundant and a good argument can be made that a simple language is easier to use and easier to optimize, the available of familiar syntax reduces the cost of conversion from commercial systems to Firebird.
Non-blocking concurrency control was the foundation on which InterBase was built and remains a central element of Firebird. The creator of InterBase, Jim Starkey, created the first multi-version concurrency control system in 1982. It eliminated the cost of record locking while increasing throughput and maintaining an equivalent level of consistency. Multi-version concurrency control also reduces the difficulty of database administration by eliminating the need for a before image (rollback) journal.
Multi-version concurrency control uses back versions of modified and deleted records to maintain a consistent view of data for read transactions. Each record version is tagged with the identifier of the transaction that created it. When a record is modified, the old version of the record is reduced to a "delta record" - a set of differences from the new version - and written to a new location, ordinarily on the same page where it was originally stored. Then the new record overwrites the old. The new record points to the old record. Unless the values of indexed fields are changed, there's no need to update the index. Even if the values have changed, the old values remain in the index to keep the record available to older transactions.
The transaction identifier also permits update transactions to recognize updates by concurrent transactions and allows Firebird to dispense with write locks on records. When a transaction encounters a record updated by a concurrent transaction, it waits for the other transaction to complete. If the competing transaction commits, the waiting transaction gets an error. If the competing transaction rolls back, the waiting transaction succeeds. If the competing transaction attempts to update a record that the waiting transaction has modified, a deadlock exists and one or the other will receive an error.
Multi-version concurrency replaces a before-image (rollback) log with versions stored in the database. When a transaction fails, its changes remain in the database. The next transaction that reads that record recognizes that the record version is invalid. Depending on the version of Firebird and architecture, that transaction either replaces the invalid record version with its back version or invokes a garbage collect thread.
Before describing the active database features of Firebird, I will digress slightly and explain the "two architecture" situation.
Originally, InterBase was a shared library that an application program invoked. This is now called the "Classic" architecture. A remote request communicates with an inet-server, which is just another client. The instances of the shared library communicate through a lock manager and the database on disk. Each instance has its own page and metadata caches. Fairly quickly and for obvious reasons, the inet-server changed from a process-per-connection model to a thread-per-process model.
With the complete death of timesharing and the universal movement to client-server architectures, the advantages of a procedure-based architecture diminished and the cost of maintaining separate page and metadata caches became more significant. A new architecture called "SuperServer" - because it was a superior version of the old inet-server - was created. As time went on, the differences between the Classic and SuperServer grew, even though both are in the same code base. The amount of conditional code is distressing, but more distressing is the fact that some potential benefits of the "SuperServer" architecture can not be realized because the would be difficult or impossible to implement in the Classic architecture.
The Classic architecture persists for several reasons. The most compelling is that, for historical reasons, the threading in the SuperServer is very coarse. As a result, the SuperServer cannot take advantage of the parallelism offered by a multi-processor. The Classic architecture works well on multi-processors. It also isolates clients from each other, so that even if one crashes the database engine, it does not take concurrent clients with it. A third benefit is that a runaway client is easy to recognize and kill. All three of those issues can and will be addressed in the SuperServer architecture, but until they are, we will continue to work in the constraints of two architectures in one product.
The final set of features makes Firebird an "active database". They are computed fields , user defined functions and blob filters, constraints, triggers, triggers on views, stored procedures, and localization. What they have in common is that they all move processing from the client to the database. The advantages are obvious. First, the more processing that happens on server, the less data needs to be transferred between the client and server. Second, common routines can be implemented in the "active database" features, rather than relying on each client-side programmer to code the correctly. The complexity of client-side code is reduced and with it the probability of introducing bugs.
Computed fields are fields that include a formula in their definition. The computation can be as simple as a literal value, or it can require access to several tables, procedures, functions, etc. As their name suggests, they are computed at runtime and no value is stored. For example, if you want to provide a monetary value in several currencies, you could define computed fields that referenced the primary value and a table of exchange rates. When the Firebird query compiler encounters a computed field, it expands the formula and integrates it into the larger query.
"User defined functions (UDFs)" are functions written in a programming language, usually C, C++, or Delphi. They are normally compiled into a standalone shared library, though they can be linked directly with the engine (and were when there were still operating systems worth using that didn't support dynamic loading). A user defined function accepts an arbitrary number of input parameters and returns a single value. It does not maintain state between invocations, so it cannot be used for aggregate functions. It does not have "state" - it is not involved in the client transaction or connection. Although a user defined function can connect to the database and perform database operations, that usage is not recommended, particularly for updates, because of the risk of deadlock between the client transaction and the UDF. User defined functions are frequently used for string and date manipulation, and math functions.
The interface definition for user defined functions is stored in a system table. The fields in that table describe how to find the function, its name on the database side, its name in the library. Its parameters and return value and their passing modes, are stored in another table. When Firebird encounters an unknown function, it looks in the system tables and converts the parameters to the desired type and reference mode. Parameters are referenced by value, reference, and descriptor. The descriptor mode is somewhat more complex, but useful when the function must return a distinctive null value. It also allows a procedure to accept and return several types of values - creating, for example, a function that returns the absolute value of any number, regardless of type.
User defined functions can also manipulate blobs, but generally a specialized form of UDF called a blob filter is preferred. In Firebird, blobs are not just divided into blobs (binary) and clobs (character) but are give a subtype. Subtype 0 is undefined, 1 is text, 2 is text in other than ASCII representation, 3 is blr, etc. The range of negative values is reserved for user defined types and might include PDF, GIF, JPG, WordDoc, or any other large object.
A blob filter is a UDF that translates a blob from one format to another. You could, for example, create a filter that invoked Word and Acrobat to change a Word document stored in a blob of that type to a PDF. You could also use a filter to change a compressed document back into text and another to do the reverse. When Firebird receives a request for a blob, it checks the requested type and the type of the stored blob and if they are different, looks for a filter that converts one to the other. If no such filter exists, it looks for a filter that converts the input type to an intermediate type that can be converted to the requested type.
Like UDFs, blob filters are written in programming languages, compiled and linked into shared libraries, and described in a system table. They are, of course, not limited to obvious blob manipulation and can do anything that can be coded into a blob and chosen by specifying the transformation.
Firebird implements constraints on columns and tables, including foreign key constraints. Like triggers, constraints prevent incorrect data from being entered into the database. In addition, foreign key constraints can determine the action to be taken an attempt is made to change a record in the parent table that has dependent records in the child table. You can specify that the child records be deleted, that their foreign keys be set to null, that their foreign keys be set to match the new key value for the parent record, or that the operation return an error.
Most database programmers have discovered triggers at some point in their careers. Most systems have some type of trigger. Typically, triggers are specific to a table and fire before or after a database action. Firebird triggers are written in an extended subset of SQL that is also used for stored procedures. The SQL-99 standard specifies that there can be at most one trigger before and one trigger after an action. Firebird allows an arbitrary number of triggers in either location. If the order of firing affects the application logic or performance, each trigger can be given a position so it will fire after the trigger in the next lower position and before the trigger in the next higher position.
Triggers that cause updates of other tables will fire triggers on those tables. Those triggers can cause updates of other tables, including the original table, and the triggers on those tables will fire. Recursion is stopped before it causes a stack overflow, but aside from that case, they can be nested arbitrarily deep. If any part of the trigger fails, it undoes all actions back to the insert/update/delete that caused the first trigger to fire.
Triggers can also invoke stored procedures and UDFs so their capabilities are virtually unlimited. When they encounter errors, they can return a status associated with a user defined message.
View triggers are a Firebird extension to the normal capabilities of triggers. Firebird allows direct update of simple views: non-reflexive views of a single table that include the primary key and any columns or combinations of columns that are declared as unique. On those views, triggers work they same way they do on base tables. For other views, the triggers replace the action. Thus a view that includes a join or a union can be updated following the rules the database designer lays out in triggers.
The inspiration for view triggers is that views are often used to hide database changes from client programs. A table may be split or two tables combined for efficiency. Until all client applications are modified to use the new format, they continue to run against views that have the same name and the same content as the old tables. When reconstructing a table requires creating a view that cannot be updated normally, the database designer describes the update behavior of the view in triggers.
View triggers are not limited to emulating update operations on views that cannot be updated naturally. They can also emulate stored procedures, and did for a number of years until the customer base finally convinced the architects that stored procedures were not just a workaround for databases that were slow or otherwise unwieldy. An insert into a view could cause a series of database actions governed by the values of the view fields - used like procedure parameters.
The language used for stored procedures and triggers is an adaptation of standard SQL with several additions and some significant deletions. Metadata objects cannot be changed in a stored procedure. No DDL commands are allowed. Part of the reason for that is a strong prejudice on the part of the developers that on-line metadata updates are a good idea but can be taken too far. The execution of a DDL command occurs in two parts. When the command executes, it updates the system tables and creates a description of the physical changes that must be made. That description is associated with the transaction. When the transaction commits, the DDL changes are instantiated. This is very different from some commercial databases where DDL changes are always made through stored procedures.
Stored procedures cannot change the state of the client transaction. Transaction control is part of the application and "black box" operations in the database cannot affect it. Unless the stored procedure includes explicit error handling, any error it encounter will undo it, procedures it invoked, and any triggered actions it caused.
The additions to SQL are a conditional statement (IF … THEN …ELSE), BEGIN…END to delimit code blocks, the ability to declare variables, EXIT, error handling, and for stored procedures only, a loop (WHILE … DO…), SUSPEND, and a FOR SELECT loop.
The stored procedure and trigger language is compiled on first reference into an internal request format and optimized. In the Classic architecture, this must be done once for each connection. In the SuperServer architecture, the compiled form of the procedure is released only at the close of the last connection to the database.
Neither triggers nor stored procedures can build queries on the fly. Input and output values can be parameterized, but the actions, table names, and field names are fixed at the time the procedure or trigger is created.
Stored procedures are also common to many systems. Firebird stored procedures differ from most in their language - the extended subset of SQL described above - and in the fact that they can be used like tables.
The FOR SELECT loop works very much like a declare cursor, prepare, open, a loop of fetching records, and a test that will cause the loop to exit when the data stream is exhausted. The SUSPEND operation stops the stored procedure and returns the output variables to the client or whatever caused the procedure to be invoked.
The FOR SELECT and SUSPEND allow stored procedures to be used for retrieval like tables or views. Stored procedures can provide input streams for any type of join, subquery, union, or view. A stored procedure without a SUSPEND is executed like a normal procedure. A stored procedure with a SUSPEND is invoked as part of a select statement or select expression.
Either an "execute" stored procedure or a "select" stored procedure can also insert, update, and delete records. If any of those operations have triggers, the triggers fire normally. The procedure can also call other procedures and call itself recursively - directly or indirectly. As with triggers, the recursion level is checked to prevent stack overflow.
Many, if not most, Firebird application developers put significant parts of their applications into stored procedures, creating insert procedures for each table that guarantee that all values are legitimate. The combination of constraints, triggers and stored procedures may begin to seem like belt, braces, and pantywaist buttons, but different applications have different requirements and each of the methods has its advocates.
The final item in the list of "active database" features is localization. Firebird has an open interface that allows customers to define character sets and collating sequences on those character sets. The database understands one, two, three, and varying byte length characters. A library shipped with the product provides most common character sets and collations. A default character set and collation can be defined for a database, a connection, or a column. The localization specified affects the representation of the data - the number of bytes allocated, and sorting, comparisons, and indexes.
In conclusion, Firebird has a number of features that make converting from a commercial system to it easier than converting to some other open source databases. If we are to seduce customers from commercial systems, these are features we need to offer. Firebird might not be the first choice as a backend for some web applications - though it is used successfully in that environment - but it offers features that more transaction oriented applications require.
This paper was written by Ann Harrison in March 2002, and is copyright Ms. Harrison and IBPhoenix Inc. You may republish it verbatim, including this notation. You may update, correct, or expand the material, provided that you include a notation that the original work was produced by Ms. Harrison and IBPhoenix Inc.
- [1] InterBase, InterBase Open Edition, Delphi, and Borland are trademarks of Borland Software Corporation.
- [2] Mythical Man-Month, The: Essays on Software Engineering, Frederick P. Brooks, Jr., Boston, Addison Wesley, 1975,1995 ISBN: 0-201-83595-9
- [3] A sparse bitmap is a bitmap that stores both isolated values and dense values in a compressed format. A series of identical bits is represented by the offset of the first and the offset of the last.