INNOGAMES STORIES

Table Inheritance in Forge of Empires

In Forge of Empires we use the relational database system PostgreSQL to store our game data. Sometimes, a table doesn’t have an optimal design and needs code logic to ensure the data consistency.

In such cases, tables may be growing horizontally with optional fields and nullable foreign keys. We may even see ourselves relying on “type” columns rather than making proper use of foreign keys and relational tables.

The conventional one to one relationship is still a very good approach but there is an alternative based on the object-oriented concept that can provide better performance while having a very clean and familiar design: the Table Inheritance.

What is Table Inheritance

Table Inheritance is a concept that creates a parent-child relationship between multiple tables. As of 2021, it’s available only on PostgreSQL databases and version 9.6, released on September 2016, is the oldest supported version.

Using the Table Inheritance results in child tables that will not only have their dedicated fields, but also inherit all the parent table’s columns. This way, we don’t need Foreign Keys like in the conventional one to one relationship approach since every child is a partition from the parent table and can also inherit constraints and indexes.

It is also important to mention that, unlike the object-oriented programming, Table Inheritance deals only with data structure and disregards behaviours that could be passed to the children such as methods. For example, imagine that at code level your Vehicle class has an “openDoor(door)” method and you have a convertible car that doesn’t have doors and, therefore, couldn’t implement such method. While this object could cause problems at code level, this wouldn’t be a concern for the Table Inheritance as it is not a structural problem, but a behavioural one.

Diagram of the one to one database relationship compared to the Table Inheritance relationship

Query Examples with Table Inheritance

The queries needed to create the Table Inheritance and perform the regular database operations have a very simple syntax.

To create a table using the inheritance, simply add INHERITS (parent_table_name) after the column definitions when creating the child table. In the example below, the “car” table will have not only its dedicated columns but also inherit the “vehicle” definitions, including the serial column.

CREATE TABLE vehicle (
    id SERIAL PRIMARY KEY NOT NULL,
    manufacturer varchar NOT NULL,
    license_plate varchar NOT NULL,
    mileage int NOT NULL DEFAULT 0
);
CREATE TABLE car (
    LIKE vehicle INCLUDING INDEXES, -- optional, used to inherit parent's indexes
    max_speed int NOT NULL,
    number_of_seats int NOT NULL,
    main_color varchar NOT NULL
) INHERITS (vehicle); -- mandatory, this is what will generate the inheritance

In comparison to the one to one relationship where two inserts to save “vehicle” and “car” data are needed, the Table Inheritance allows us to perform one single INSERT query directly at the child table as there is no foreign key constraint to fulfil. Due to all definitions being inherited, the serial from the parent table will be used and incremented as well.

INSERT INTO car (
    manufacturer, license_plate, mileage, max_speed, number_of_seats, main_color
)
VALUES ('Audi', 'ABC1234', 0, 210, 5, 'black');

Selecting data is also simplified with Table Inheritance, especially when we want to load all data related to one of the children. In the example below, there is a comparison between the conventional approach and the inheritance approach on both general and dedicated data retrieval.

-- All data, one to one relationship
SELECT * FROM vehicle_1t1 v
LEFT JOIN car_1t1 c ON v.id = c.vehicle_id
LEFT JOIN truck_1t1 t ON v.id = t.vehicle_id;
 
-- All data, Table Inheritance
SELECT * FROM vehicle
NATURAL FULL JOIN car
NATURAL FULL JOIN truck;
 
-- Data from dedicated table, one to one relationship
SELECT * FROM car_1t1 c
JOIN vehicle_1t1 v ON c.vehicle_id = v.id;
 
-- Data from child table, Table Inheritance
SELECT * FROM car;

Drawbacks

The biggest limitations of the Table Inheritance are the unique and foreign key constraints. Such constraints are neither inherited nor shared across multiple children tables or with the parent table.

The unique constraint is applied to one single table and does not propagate to any child or parent table. This means that we can only ensure that values for a column or group of columns are unique when inserting them directly into the table that has such index. If a row is inserted into any of the other tables from that inheritance, regardless of being a parent or child table, the unique constraint is not taken into account.

In our previous example, if we add the constraint to “license_plate” in the “vehicle” table we do not allow rows inserted directly into the vehicle table to have repeated license plates although it would still be possible to add a car that has an existing license plate. The same works in a reverse fashion meaning that if I also add a unique constraint to the “license_plate” in the “car” table, I can still bypass when add a row into the parent vehicle table. The example below illustrates what happens in both situations.

INSERT INTO vehicle (manufacturer, license_plate) VALUES ('Audi', 'ABC1234');
✓
 
INSERT INTO vehicle (manufacturer, license_plate) VALUES ('Audi', 'ABC1234');
✗ [23505] ERROR: duplicate key value violates unique constraint
"vehicle_unique_license_plate"
Detail: Key (license_plate)=(ABC1234) already exists.
 
INSERT INTO car (
    manufacturer, license_plate, mileage, max_speed, number_of_seats, main_color
)
VALUES ('Audi', 'ABC1234', 0, 210, 5, 'black');
✓
 
SELECT * FROM vehicle;
 id | manufacturer | license_plate | mileage
----+--------------+---------------+---------
  1 | Audi         | ABC1234       |       0
  3 | Audi         | ABC1234       |       0
(2 rows)
 
INSERT INTO car (
    manufacturer, license_plate, mileage, max_speed, number_of_seats, main_color
)
VALUES ('Audi', 'XYZ9876', 0, 210, 5, 'black');
✓
 
INSERT INTO car (
    manufacturer, license_plate, mileage, max_speed, number_of_seats, main_color
)
VALUES ('Audi', 'XYZ9876', 0, 210, 5, 'black');
✗ [23505] ERROR: duplicate key value violates unique constraint
"car_unique_license_plate"
Detail: Key (license_plate)=(XYZ9876) already exists.
 
INSERT INTO vehicle (manufacturer, license_plate) VALUES ('Audi', 'XYZ9876');
✓
 
SELECT * FROM vehicle;
 id | manufacturer | license_plate | mileage
----+--------------+---------------+---------
  1 | Audi         | ABC1234       |       0
  2 | Audi         | ABC1234       |       0
  4 | Audi         | XYZ9876       |       0
  6 | Audi         | XYZ9876       |       0
(4 rows)

The same limitation happens in the foreign key constraint in two different ways: when having a column that references a table outside of the inheritance and when having a column from the parent table that is referenced by another table.

In the first scenario, if I now create a “manufacturer” table and change the vehicle column to reference the “id” from this new table, this constraint is not going to be applied automatically to the children tables. However, a workaround for this issue is to also apply the foreign key constraint to the child table.

-- After creating the 'manufacturer' table and having a 'manufacturer_id' field
-- with a FK constraint in the 'vehicle' table
 
SELECT * FROM manufacturer;
 id | name
----+------
  1 | Audi
(1 row)
 
INSERT INTO vehicle (manufacturer_id, license_plate) VALUES (2, 'QWE567');
✗ [23503] ERROR: insert or update on table "vehicle" violatesforeign key constraint
"vehicle_manufacturer"
Detail: Key (manufacturer_id)=(2) is not present in table "manufacturer".
 
INSERT INTO car (
    manufacturer_id, license_plate, mileage, max_speed, number_of_seats, main_color
)
VALUES (2, 'QWE567', 0, 210, 5, 'black');
✓
 
SELECT * FROM vehicle;
 id | manufacturer_id | license_plate | mileage
----+-----------------+---------------+---------
  1 |               2 | QWE567        |       0
(1 row)
 
-- After removing the car with the incorrect 'manufacturer_id'
-- and creating a FK constraint in the 'car' table
 
INSERT INTO car (
    manufacturer_id, license_plate, mileage, max_speed, number_of_seats, main_color
)
VALUES (2, 'QWE567', 0, 210, 5, 'black');
✗ [23503] ERROR: insert or update on table "car" violates foreign key constraint
"car_manufacturer"
Detail: Key (manufacturer_id)=(2) is not present in table "manufacturer".

The second situation is similar to the unique constraint caveat. In this case, if a new table now has a foreign key constraint referencing the “vehicle.id”, such constraint is applied only to the rows that have been inserted directly on such table and insertions containing an “id” from a “car” row would fail.

-- After creating a 'vehicle_owner' table that has a 'vehicle_id' field
-- with a FK constraint referencing 'vehicle.id'
 
INSERT INTO car (
    manufacturer, license_plate, mileage, max_speed, number_of_seats, main_color
)
VALUES ('Audi', 'ABC12345', 0, 210, 5, 'black') RETURNING id;
✓
 id
----
  1
(1 row)
 
INSERT INTO vehicle_owner (vehicle_id, driver_name) VALUES 1, 'John Doe');
✗ [23503] ERROR: insert or update on table "vehicle_owner" violates foreign key
constraint "vehicle_owner_vehicle_id"
Detail: Key (vehicle_id)=(1) is not present in table "vehicle".
 
INSERT INTO vehicle (manufacturer, license_plate) VALUES ('Audi', 'ASDF146')
RETURNING id;
✓
 id
----
  2
(1 row)
 
INSERT INTO vehicle_owner (vehicle_id, driver_name) VALUES (2, 'John Doe');
✓

Table Inheritance Performance

One of the greatest advantages that the Table Inheritance provides is the performance improvement when fetching dedicated data. In order to compare the performance of the Table Inheritance with the One to One relationship, I have created a scenario with two sets of tables: one with 20.000 Vehicle rows (10.000 Cars and 10.000 Trucks) using the inherited definition and one with the same amount of rows, but using the conventional approach. Then, I have benchmarked the duration to get all data and dedicated data for both designs by running the EXPLAIN ANALYSE on the following SELECT queries, which also provided the following times listed in the “EXPLAIN ANALYSE result” column:

QueryTable DesignIntentEXPLAIN ANALYSE
result
SELECT * FROM car;Table InheritanceSpecific data (all cars)≈ 112 ms
SELECT * FROM car_1t1 c
JOIN vehicle_1t1 v ON c.vehicle_id = v.id;
One to OneSpecific data (all cars)≈ 353,5 ms
SELECT * FROM vehicle_1t1 v
LEFT JOIN car_1t1 c ON v.id = c.vehicle_id
LEFT JOIN truck_1t1 t ON v.id = t.vehicle_id;
One to OneAll data≈ 675 ms
SELECT * FROM vehicle
NATURAL FULL JOIN car
NATURAL FULL JOIN truck;
Table InheritanceAll data≈ 832,5 ms
Time results of the EXPLAIN ANALYSE SELECTs for the scenarios with 10.000 Car rows and 10.000 Truck rows with different table designs and intents

The results show that the Table Inheritance is not faster than the one to one relationship when we need to get all columns from the group of tables. However, it was more than 3x faster when retrieving all the data from one of the child tables, being a very interesting solution for the use cases where such SELECT queries are needed.

In addition, some basic queries for INSERT, UPDATE and DELETE with the Table Inheritance had similar or slightly better performance results than the correspondent queries when using the one to one relationship. Due to the nature of the conventional one to one structure, sometimes two queries were needed to achieve the end result as shown in the table below.

QueryTable DesignEXPLAIN ANALYSE
result
INSERT INTO vehicle_1t1 (manufacturer, license_plate, mileage)
VALUES (‘Audi’, ‘ABC1234’, 0);
INSERT INTO car_1t1 (vehicle_id, max_speed, number_of_seats, main_color) VALUES (1, 210, 5, ‘black’);
One to One≈ 0,9 ms
(0,5 ms + 0,4ms)
INSERT INTO car (manufacturer, license_plate, mileage, max_speed, number_of_seats, main_color)
VALUES (‘Audi’, ‘ABC1234’, 0, 210, 5, ‘black’);
Table Inheritance≈ 0,9 ms
UPDATE car_1t1 SET main_color = ‘red’ WHERE vehicle_id = 1;
UPDATE vehicle_1t1 SET manufacturer = ‘Ferrari’ WHERE id = 1;
One to One≈ 0,5 ms
(0,25 ms + 0,25 ms)
UPDATE car SET manufacturer = ‘Ferrari’, main_color = ‘red’ WHERE id = 1;Table Inheritance≈ 0,2 ms
DELETE FROM vehicle_1t1 WHERE id = 1;One to One≈ 0,4 ms
(CASCADE deletion)
DELETE FROM car WHERE id = 1;Table Inheritance≈ 0,2 ms
Time results of the EXPLAIN ANALYSE INSERTs, UPDATEs and DELETEs for the vehicle-car scenario with the different table designs

Implementation in Forge of Empires

After checking out how to get the best from the Table Inheritance, it was decided to add the concept to the Forge of Empires game project. The main goal was to profit from its benefits and add the inheritance where it is going to be meaningful rather than just change some existing design for the sake of having inherited tables.

To find out the best use cases, we have searched throughout our database for tables that did not have an ideal design and could benefit from the performance improvements, namely selecting data from what would become children tables for most of its usage. In addition, one common point is that such tables would often use complex queries to fulfil the possible scenarios required by the business logic, either by combining many JOINS or having some different WHERE/AND conditions to narrow down the SELECT.

With that set, we looked for the following the key points on the database tables:

  • horizontal growth with optional fields, sometimes even nullable foreign keys;
  • relying on “type” enum columns instead of using proper foreign keys;
  • duplicated fields related to the same core feature;

The first candidate was the Notice Indicator feature, which informs the players whether they have unlocked new buildings via research, received new items to their inventory or have progressed on their quests. Inside the game logic, the Notice Indicator not only references other features of the game but is also loaded on the game start, directly affecting the game loading time for every single session. In the old structure of the database table, the following problems have been spotted:

  • one single database table growing horizontally;
  • using a “type” enum column as reference;
  • nullable optional fields used based on the scope, including foreign keys;

The picture below shows how the table used to look with the aforementioned problems marked in red and how is it designed after refactoring them with the Table Inheritance design. The new approach removed the red flags, generated tables that would only contain their relevant data and enforced the business logic on the database level, also generating the unique constraints for each of the child tables. In the end, we have dropped the “type” column as such reference was no longer needed and kept the columns used on every situation in “NoticeIndicator” parent table.

After the changes in the database design, it was time to make our project compliant with the Table Inheritance both in query and code. Upon refactoring the code, we were able to make good use the Service Locator pattern:

  • first, by adding an abstract NoticeIndicator gateway containing the abstract base methods for the general database operations such as INSERT, DELETE and SELECT all the data from one of the tables;
  • then, creating a gateway class for each of the child tables extending the abstract gateway and implementing the methods with queries based on such tables;
  • finally, a service class to locate the proper gateway based on the parameter sent in the request;

By using the approach above, this part of the project now has simple and performant queries, cleaner code and also better reusability: to add a new child table we now only need to create it in the database, implement the dedicated gateway and everything would be working right away without adjustments or new dependencies injected. It is worth mentioning that there is a small loss of performance when needing to retrieve all the data from all the tables altogether when comparing to the previous solution where the data was stored in one single table. However, that was accepted in favour of a better design.

The first implementation of the Table Inheritance was considered a success by the team, which encouraged us to take the next step and apply the new concepts to a more complex game feature: the Boosts.

Boost overview in Forge of Empires. Each background colour represents a different origin type for that boost

The picture above is an example of how extensive the boosts can be with different types and origins varying from items, buildings, core mechanics and even other game features. The boosts are used everywhere in the game from the smallest actions such as collecting a production to every single unit in every battle.

Performance is a key factor when loading the Boosts, with a database table that contains millions of rows. However, we spotted some red flags in the older design:

  • one single database table growing horizontally;
  • nullable optional fields used based on the scope, including foreign keys;
  • non-nullable optional fields filled with arbitrary values when not need by a certain scope;

In the end, the same approach from the Notice Indicator feature was used both on database and code level to improve its performance, design and reusability. How the table looked before and the design with the Table Inheritance can be seen in the diagram below.

Conclusion

After the experience I had when implementing the Table Inheritance, I have created two comparison tables: one between the key points between Table Inheritance and the one to one relationship and another with some pros and cons of the concept.

Key PointsTable InheritanceOne to One relationship
Parent columns are not duplicated
Easy to add/remove columns
Easy to scale and add new dedicated tables
Easy to get specific data Requires JOIN with FK for main table data
Easy to get all data altogether Might require
NATURAL FULL JOIN
Requires JOIN with FK for related table data
Implementation and maintenance effort Higher effort than one to one relationship Maintain PK and FK for every related table
PROSCONS
Performance to retrieve specific data Performance when loading data from parent and all children in a single query 
Clean design familiar to the OOP Constraints and indexes either need to be explicitly inherited or cannot be inherited at all
Easy to implement and scale Maintenance requires more effort: REINDEX and VACUUM do not support recursing over inherited hierarchies
Simple queries Non-trivial manual work for database triggers
Good integration with the Service Locator pattern Exclusive to PostgreSQL

Overall, I recommend the Table Inheritance as it is a very useful solution that provides better performance than the one to one relationship in some use cases with a clean database design. Along with its benefits, the Table Inheritance also changed my way of thinking about the design of the database as I now think ahead on how I intend to use and retrieve data to consider if its worth using the Table Inheritance.

Keep in mind that the conventional one on one relationship still provides a very good solution and the inheritance might not be the most recommended solution for every table design. Be sure to analyse if you will profit from the benefits and use it wisely, otherwise you might end up disliking the concept if it is misused.

InnoGames is hiring! Check out open positions and join our awesome international team in Hamburg at the certified Great Place to Work®.