Optimise Your Own Fuckin' Tail Calls

I've heard a few people moaning that Java 8 still doesn't optimise tail calls. Not having programmed in a functional language since Moscow ML at University, I didn't really give a shit, but thought I should find out what the deal is.

A tail call method is a method where the final action is to call another method. And a tail-recursive method is when a method's final action is to call itself.

Now, we all know recursion is mathematically beautiful and elegant for people who write programs that don't do anything. For the rest of us, using recursion for anything non-trivial means you're going to run out of stack at some point.

For example NASA's JPL C Coding Standard disallows the use of recursion because:-

"The presence of statically verifiable loop bounds and the absence of recursion prevent runaway code, and help to secure predictable performance for all tasks. The absence of recursion also simplifies the task of deriving reliable bounds on stack use. The two rules combined secure a strictly acyclic function call graph and control-flow structure, which in turn enhances the capabilities for static checking tools to catch a broad range of coding defects."

Languages which support tail call optimisation replace tail call recursion with a loop so you don't have to worry about runaway stack usage. Think about that - the compiler tries to get rid of recursion for you, because it's inefficient and prone to causing defects. How elegant is your recursive algorithm really?

Also, in what other situation would you expect the compiler to so drastically change your code for you? Yeah I know you can expect the Java JIT compiler to perform optimisations, but tail call elimination is a step too far for me. While you're optimising my recursive calls, why don't you just go ahead and write the rest of my algorithms for me? - GET OFF MY LAWN!

A good example of converting a recursive algorithm to a while loop is available here: http://c2.com/cgi/wiki?TailCallOptimization and I've converted it to Java below.

I've used BigInteger in the code to avoid integer overflow, because I want to demonstrate stack overflow with the default JVM settings.

First, a recursive method which is NOT tail call recursive. The method is not tail call recursive because the final action in the method is not a call to itself but a multiplication:

    private static BigInteger notTailRecursionFactorial(final BigInteger n) {

        if (n.compareTo(TWO) < 0) {
            return ONE;
        } else {
            return n.multiply(notTailRecursionFactorial(n.subtract(ONE)));
        }
    }

Modifying the method to use an accumulator variable makes the method tail call recursive, and a candidate for tail call optimisation:

    private static BigInteger tailRecursionFactorial(final BigInteger n, final BigInteger accumulator) {

        if (n.compareTo(TWO) < 0) {
            return accumulator;
        } else {
            return tailRecursionFactorial(n.subtract(ONE), n.multiply(accumulator));
        }
    }

The recursive method converted to a while loop:

    private static BigInteger tailRecursionEliminationFactorial(BigInteger n, BigInteger accumulator) {

        while (n.compareTo(TWO) >= 0) {
            accumulator = accumulator.multiply(n);
            n = n.subtract(ONE);
        }

        return accumulator;
    }

Further optimisation to the tail call eliminated method:

    private static BigInteger tailRecursionEliminationFactorialOptimised(BigInteger n) {

        BigInteger accumulator = ONE;

        while (n.compareTo(TWO) >= 0) {
            accumulator = accumulator.multiply(n);
            n = n.subtract(ONE);
        }

        return accumulator;
    }

The full class looks like this:

TailCallOptimisation.java

package org.adrianwalker;

import java.math.BigInteger;

public class TailCallOptimisation {

  private static final BigInteger ONE = new BigInteger("1");
  private static final BigInteger TWO = new BigInteger("2");
  private static final BigInteger ONE_HUNDRED_THOUSAND = new BigInteger("100000");

  public static void main(final String[] args) {

    System.out.println("\nnotTailRecursionFactorial:");

    try {
      System.out.println(notTailRecursionFactorial(ONE_HUNDRED_THOUSAND));
    } catch (final Throwable t) {
      System.out.println("Stack Overflow Error");
    }

    System.out.println("\ntailRecursionFactorial:");

    try {
      System.out.println(tailRecursionFactorial(ONE_HUNDRED_THOUSAND, ONE));
    } catch (final Throwable t) {
      System.out.println("Stack Overflow Error");
    }

    System.out.println("\ntailRecursionEliminationFactorial:");

    System.out.println(tailRecursionEliminationFactorial(ONE_HUNDRED_THOUSAND, ONE));

    System.out.println("\ntailRecursionEliminationFactorialOptimised:");

    System.out.println(tailRecursionEliminationFactorialOptimised(ONE_HUNDRED_THOUSAND));
  }

  private static BigInteger notTailRecursionFactorial(final BigInteger n) {

    if (n.compareTo(TWO) < 0) {
      return ONE;
    } else {
      return n.multiply(notTailRecursionFactorial(n.subtract(ONE)));
    }
  }

  private static BigInteger tailRecursionFactorial(final BigInteger n, final BigInteger accumulator) {

    if (n.compareTo(TWO) < 0) {
      return accumulator;
    } else {
      return tailRecursionFactorial(n.subtract(ONE), n.multiply(accumulator));
    }
  }

  private static BigInteger tailRecursionEliminationFactorial(BigInteger n, BigInteger accumulator) {

    while (n.compareTo(TWO) >= 0) {
      accumulator = accumulator.multiply(n);
      n = n.subtract(ONE);
    }

    return accumulator;
  }

  private static BigInteger tailRecursionEliminationFactorialOptimised(BigInteger n) {

    BigInteger accumulator = ONE;

    while (n.compareTo(TWO) >= 0) {
      accumulator = accumulator.multiply(n);
      n = n.subtract(ONE);
    }

    return accumulator;
  }
}

And the output on my machine is:

notTailRecursionFactorial:
Stack Overflow Error

tailRecursionFactorial:
Stack Overflow Error

tailRecursionEliminationFactorial:
282422940796034787429342157802453551847749492609... (loads more)

tailRecursionEliminationFactorialOptimised:
282422940796034787429342157802453551847749492609... (loads more)

The recursive methods run out of stack way before getting anywhere near an answer for 100,000!.

Bottom line - optimise your own fuckin' tail calls.

Update - 24/08/14

A clever chap called Dr Rowan Davies got in touch about this post. Here's some food for thought:-

Just a small comment that your page "Optimise Your Own Fuckin' Tail Calls" is missing the point.

Basically, you've only considered the very simplest situation, a single recursive function that corresponds to a loop. Functional compilers like Scala do exactly the transformation to loops you've shown, so no one is complaining about that kind of tail call on the JVM.

It is the much more powerful uses of tail calls for things that don't correspond to loops. E.g., in F# on .NET (which supports tail calls) there is really nice support for asynchronous programming that depends on tail calls to avoid the stack increasing when you swap between different asynchronous handlers and lightweight software threads. The correspond code in Scala can't do that, the JVM just doesn't support it - and I challenge you to convert such asynchronous code using tail calls to Java code that doesn't chew up stack as it goes.

And, optimized tail-calls are not rewriting your code - they are exactly doing the tail call, just in a way that doesn't keep crap on your stack that clearly can never be needed in the future. Basically rejecting tail call optimization is demanding that the JVM keep this unneeded crap on the stack. Why do you insist that the JVM keep crap around? It's equivalent to insisting that for loops chew up stack space as they go through iterations - it really makes no sense at all to require that.

And this one as well:-

Your view is actually pretty common. But, it really is unnatural to make the implementation of tail calls consume stack when they don't have to. It's not so much about mathematical elegance, it's about whether certain powerful and natural ways of programming explode the stack or not. You're expecting a function call to always be implemented in a certain way that is really non-optimal sometimes. It's not really an optimization, it's about not doing something stupid that keeps potentially huge amounts of unnecessary data on the stack. gcc has done this basically forever. Indeed, many years ago I checked the machine code output and the C compiler cc in UNIX System V and it clearly supported efficient tail calls back in 1989.

The JVM doesn't include efficient tail calls largely because the JVM security model isn't so compatible with them, and changing the model would change the assumptions existing code could depend on. This is a basically a bureaucratic reason, the requirement to support earlier JVM programs that depend on the lack of efficient tail calls. But, many hackers and language implementers will celebrate if it is allowed sometime, otherwise those hackers and languages will eventually move on to VMs that do support what they need.

Cheers for the comments doc.

Database Backed Map

I wanted an RDBMS backed Map, with it's keys and values immediately persisted to a relational database for use with a properties design pattern for prototype based programming.

I'm not sure if it'll be useful to anybody else, or even me for that matter, but I thought I'd put it out there anyway. The implementation, RdbmsMap, implements the java.util.Map interface and reads from, and writes to, a PostgreSQL database. The implementation supports key and values types of: null, Boolean, Integer, Double, String and RdbmsMap(the persistent Map class itself).

The ER diagram looks like this:

(Click To Enlarge)

The PostgreSQL code to create this schema is:

rdbms-map.sql

CREATE TABLE map
(
  id serial NOT NULL,
  CONSTRAINT map_pkey PRIMARY KEY (id)
);

CREATE TABLE entry
(
  id serial NOT NULL,
  map_id integer NOT NULL,
  key_type character(1) NOT NULL,
  value_type character(1) NOT NULL,
  CONSTRAINT entry_pkey PRIMARY KEY (id),
  CONSTRAINT entry_map_id_fkey FOREIGN KEY (map_id) REFERENCES map (id) ON DELETE CASCADE
);

CREATE INDEX entry_key_type_idx ON entry (key_type);
CREATE INDEX entry_value_type_idx ON entry (value_type);

CREATE TABLE object_integer
(
  id serial NOT NULL,
  entry_id integer NOT NULL,
  map_id integer NOT NULL,
  type character(1) NOT NULL,
  value integer NOT NULL,
  CONSTRAINT object_integer_pkey PRIMARY KEY (id),
  CONSTRAINT object_integer_entry_id_fkey FOREIGN KEY (entry_id) REFERENCES entry (id) ON DELETE CASCADE,
  CONSTRAINT object_integer_map_id_fkey FOREIGN KEY (map_id) REFERENCES map (id) ON DELETE CASCADE
);

CREATE INDEX object_integer_type_idx ON object_integer (type);
CREATE INDEX object_integer_value_idx ON object_integer (value);


CREATE TABLE object_boolean
(
  id serial NOT NULL,
  entry_id integer NOT NULL,
  map_id integer NOT NULL,
  type character(1) NOT NULL,
  value boolean NOT NULL,
  CONSTRAINT object_boolean_pkey PRIMARY KEY (id),
  CONSTRAINT object_boolean_entry_id_fkey FOREIGN KEY (entry_id) REFERENCES entry (id) ON DELETE CASCADE,
  CONSTRAINT object_boolean_map_id_fkey FOREIGN KEY (map_id) REFERENCES map (id) ON DELETE CASCADE
);

CREATE INDEX object_boolean_type_idx ON object_boolean (type);
CREATE INDEX object_boolean_value_idx ON object_boolean (value);

CREATE TABLE object_numeric
(
  id serial NOT NULL,
  entry_id integer NOT NULL,
  map_id integer NOT NULL,
  type character(1) NOT NULL,
  value numeric NOT NULL,
  CONSTRAINT object_numeric_pkey PRIMARY KEY (id),
  CONSTRAINT object_numeric_entry_id_fkey FOREIGN KEY (entry_id) REFERENCES entry (id) ON DELETE CASCADE,
  CONSTRAINT object_numeric_map_id_fkey FOREIGN KEY (map_id) REFERENCES map (id) ON DELETE CASCADE
);

CREATE INDEX object_numeric_type_idx ON object_numeric (type);
CREATE INDEX object_numeric_value_idx ON object_numeric (value);

CREATE TABLE object_text
(
  id serial NOT NULL,
  entry_id integer NOT NULL,
  map_id integer NOT NULL,
  type character(1) NOT NULL,
  value text NOT NULL,
  CONSTRAINT object_text_pkey PRIMARY KEY (id),
  CONSTRAINT object_text_entry_id_fkey FOREIGN KEY (entry_id) REFERENCES entry (id) ON DELETE CASCADE,
  CONSTRAINT object_text_map_id_fkey FOREIGN KEY (map_id) REFERENCES map (id) ON DELETE CASCADE
);

CREATE INDEX object_text_type_idx ON object_text (type);
CREATE INDEX object_text_value_idx ON object_text (value);

CREATE TABLE object_null
(
  id serial NOT NULL,
  entry_id integer NOT NULL,
  map_id integer NOT NULL,
  type character(1) NOT NULL,
  CONSTRAINT object_null_pkey PRIMARY KEY (id),
  CONSTRAINT object_null_entry_id_fkey FOREIGN KEY (entry_id) REFERENCES entry (id) ON DELETE CASCADE,
  CONSTRAINT object_null_map_id_fkey FOREIGN KEY (map_id) REFERENCES map (id) ON DELETE CASCADE
);

CREATE INDEX object_null_type_idx ON object_null (type);

CREATE TABLE object_map
(
  id serial NOT NULL,
  entry_id integer NOT NULL,
  map_id integer NOT NULL,
  type character(1) NOT NULL,
  value integer NOT NULL,
  CONSTRAINT object_map_pkey PRIMARY KEY (id),
  CONSTRAINT object_map_entry_id_fkey FOREIGN KEY (entry_id) REFERENCES entry (id) ON DELETE CASCADE,
  CONSTRAINT object_map_map_id_fkey FOREIGN KEY (map_id) REFERENCES map (id) ON DELETE CASCADE,
  CONSTRAINT object_map_value_fkey FOREIGN KEY (value) REFERENCES map (id) ON DELETE CASCADE
);

CREATE INDEX object_map_type_idx ON object_map (type);

The Map implementation is:

RdbmsMap.java

package org.adrianwalker.rdbmsmap;

import java.sql.Connection;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public final class RdbmsMap<K, V> implements Map<K, V> {

  // object types
  private static final String OBJECT_NULL_TYPE = "0";
  private static final String OBJECT_INTEGER_TYPE = "I";
  private static final String OBJECT_BOOLEAN_TYPE = "B";
  private static final String OBJECT_NUMERIC_TYPE = "N";
  private static final String OBJECT_TEXT_TYPE = "T";
  private static final String OBJECT_MAP_TYPE = "M";
  // entry types
  private static final String ENTRY_KEY_TYPE = "K";
  private static final String ENTRY_VALUE_TYPE = "V";
  // object types
  private static final String OBJECT_TABLE = "object_table";
  private static final String OBJECT_NULL_TABLE = "object_null";
  private static final String OBJECT_INTEGER_TABLE = "object_integer";
  private static final String OBJECT_BOOLEAN_TABLE = "object_boolean";
  private static final String OBJECT_NUMERIC_TABLE = "object_numeric";
  private static final String OBJECT_TEXT_TABLE = "object_text";
  private static final String OBJECT_MAP_TABLE = "object_map";
  // inserts
  private static final String INSERT_MAP = "insert into map(id) values(nextval('map_id_seq')) returning id";
  private static final String INSERT_ENTRY = "insert into entry(id, map_id, key_type, value_type) values(nextval('entry_id_seq'), ?, ?, ?) returning id";
  private static final String INSERT_OBJECT = "insert into " + OBJECT_TABLE + "(id, entry_id, map_id, type, value) values(nextval('" + OBJECT_TABLE + "_id_seq'), ?, ?, ?, ?) returning id";
  // counts
  private static final String COUNT_ENTRIES = "select count(*) from entry where map_id = ?";
  private static final String COUNT_OBJECT = "select count(*) from " + OBJECT_TABLE + " where map_id = ? and type = ? and value = ?";
  // selects
  private static final String SELECT_ENTRIES = "select id, key_type, value_type from entry where map_id = ?";
  private static final String SELECT_ENTRY_BY_OBJECT = "select value_type, id from entry where id = (select entry_id from " + OBJECT_TABLE + " where map_id = ? and type = ? and value = ?)";
  private static final String SELECT_OBJECT_BY_ENTRY = "select value from " + OBJECT_TABLE + " where map_id = ? and type = ? and entry_id = ?";
  private static final String SELECT_OBJECT = "select value from " + OBJECT_TABLE + " where map_id = ? and type = ?";
  // deletes
  private static final String DELETE_ENTRIES = "delete from entry where map_id = ?";
  private static final String DELETE_ENTRY_BY_OBJECT = "delete from entry where id = (select entry_id from " + OBJECT_TABLE + " where map_id = ? and type = ? and value = ?)";
  // specific cases for nulls
  private static final String INSERT_OBJECT_NULL = "insert into " + OBJECT_NULL_TABLE + "(id, entry_id, map_id, type) values(nextval('" + OBJECT_NULL_TABLE + "_id_seq'), ?, ?, ?) returning id";
  private static final String COUNT_OBJECT_NULL = "select count(*) from " + OBJECT_NULL_TABLE + " where map_id = ? and type = ?";
  private static final String SELECT_ENTRY_BY_OBJECT_NULL = "select value_type, id from entry where id = (select entry_id from " + OBJECT_NULL_TABLE + " where map_id = ? and type = ?)";
  private static final String SELECT_OBJECT_NULL_BY_ENTRY = "select null from " + OBJECT_NULL_TABLE + " where map_id = ? and type = ? and entry_id = ?";
  private static final String SELECT_OBJECT_NULL = "select null from " + OBJECT_NULL_TABLE + " where map_id = ? and type = ?";
  private static final String DELETE_ENTRY_BY_OBJECT_NULL = "delete from entry where id = (select entry_id from " + OBJECT_NULL_TABLE + " where map_id = ? and type = ?)";

  private final Connection connection;
  private final int mapId;

  public RdbmsMap(final Connection connection) {

    this.connection = connection;

    try {
      this.mapId = inserMap();

    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  private RdbmsMap(final Connection connection, final int mapId) {

    this.connection = connection;
    this.mapId = mapId;
  }

  public int getMapId() {
    return mapId;
  }

  @Override
  public void clear() {

    try {
      delete();
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  @Override
  public boolean containsKey(final Object key) {

    try {
      return countObjects(key, ENTRY_KEY_TYPE) > 0;
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  @Override
  public boolean containsValue(final Object value) {

    try {
      return countObjects(value, ENTRY_VALUE_TYPE) > 0;
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  @Override
  public Set<Entry<K, V>> entrySet() {

    try {
      return selectEntries();
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  @Override
  public V get(final Object key) {

    try {
      return select(key);
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  @Override
  public Set<K> keySet() {

    try {
      return (Set<K>) selectObjects(ENTRY_KEY_TYPE);
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  @Override
  public V put(final K key, final V value) {

    Object previousValue = remove(key);

    try {
      insert(key, value);
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }

    return (V) previousValue;
  }

  @Override
  public void putAll(final Map<? extends K, ? extends V> m) {

    for (Entry<? extends K, ? extends V> entry : m.entrySet()) {
      put(entry.getKey(), entry.getValue());
    }
  }

  @Override
  public V remove(final Object key) {

    try {
      if (countObjects(key, ENTRY_KEY_TYPE) > 0) {
        V value = select(key);
        delete(key, ENTRY_KEY_TYPE);

        return value;
      }
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }

    return null;
  }

  @Override
  public int size() {

    try {
      return countEntries();
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  @Override
  public boolean isEmpty() {

    return size() == 0;
  }

  @Override
  public Collection<V> values() {

    try {
      return selectObjects(ENTRY_VALUE_TYPE);
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  private PreparedStatement prepareStatement(final String sql) throws SQLException {

    return connection.prepareStatement(sql);
  }

  private int inserMap() throws SQLException {

    PreparedStatement insertMap = prepareStatement(INSERT_MAP);

    ResultSet result = insertMap.executeQuery();
    if (!result.next()) {
      throw new RuntimeException();
    }

    return result.getInt(1);
  }

  private int countEntries() throws SQLException {

    PreparedStatement countEntries = prepareStatement(COUNT_ENTRIES);
    countEntries.setInt(1, mapId);

    ResultSet result = countEntries.executeQuery();
    if (!result.next()) {
      return 0;
    }

    return result.getInt(1);
  }

  private int countObjects(final Object obj, final String entryType) throws SQLException {

    String objectType = getType(obj);

    PreparedStatement countObject;

    if (objectType.equals(OBJECT_NULL_TYPE)) {
      countObject = prepareStatement(COUNT_OBJECT_NULL);
    } else if (objectType.equals(OBJECT_INTEGER_TYPE)) {
      countObject = prepareStatement(COUNT_OBJECT.replace(OBJECT_TABLE, OBJECT_INTEGER_TABLE));
      countObject.setInt(3, (Integer) obj);
    } else if (objectType.equals(OBJECT_BOOLEAN_TYPE)) {
      countObject = prepareStatement(COUNT_OBJECT.replace(OBJECT_TABLE, OBJECT_BOOLEAN_TABLE));
      countObject.setBoolean(3, (Boolean) obj);
    } else if (objectType.equals(OBJECT_NUMERIC_TYPE)) {
      countObject = prepareStatement(COUNT_OBJECT.replace(OBJECT_TABLE, OBJECT_NUMERIC_TABLE));
      countObject.setDouble(3, (Double) obj);
    } else if (objectType.equals(OBJECT_TEXT_TYPE)) {
      countObject = prepareStatement(COUNT_OBJECT.replace(OBJECT_TABLE, OBJECT_TEXT_TABLE));
      countObject.setString(3, (String) obj);
    } else if (objectType.equals(OBJECT_MAP_TYPE)) {
      countObject = prepareStatement(COUNT_OBJECT.replace(OBJECT_TABLE, OBJECT_MAP_TABLE));
      countObject.setString(3, (String) obj);
    } else {
      return 0;
    }

    countObject.setInt(1, mapId);
    countObject.setString(2, entryType);
    countObject.executeQuery();

    ResultSet result = countObject.executeQuery();
    if (!result.next()) {
      return 0;
    }

    return result.getInt(1);
  }

  private V select(final Object key) throws SQLException {

    String keyType = getType(key);

    PreparedStatement selectEntry;

    if (keyType.equals(OBJECT_NULL_TYPE)) {
      selectEntry = prepareStatement(SELECT_ENTRY_BY_OBJECT_NULL);
    } else if (keyType.equals(OBJECT_INTEGER_TYPE)) {
      selectEntry = prepareStatement(SELECT_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_INTEGER_TABLE));
      selectEntry.setInt(3, (Integer) key);
    } else if (keyType.equals(OBJECT_BOOLEAN_TYPE)) {
      selectEntry = prepareStatement(SELECT_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_BOOLEAN_TABLE));
      selectEntry.setBoolean(3, (Boolean) key);
    } else if (keyType.equals(OBJECT_NUMERIC_TYPE)) {
      selectEntry = prepareStatement(SELECT_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_NUMERIC_TABLE));
      selectEntry.setDouble(3, (Double) key);
    } else if (keyType.equals(OBJECT_TEXT_TYPE)) {
      selectEntry = prepareStatement(SELECT_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_TEXT_TABLE));
      selectEntry.setString(3, (String) key);
    } else if (keyType.equals(OBJECT_MAP_TYPE)) {
      selectEntry = prepareStatement(SELECT_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_MAP_TABLE));
      selectEntry.setString(3, (String) key);
    } else {
      return null;
    }

    selectEntry.setInt(1, mapId);
    selectEntry.setString(2, ENTRY_KEY_TYPE);

    ResultSet result = selectEntry.executeQuery();
    if (!result.next()) {
      return null;
    }

    String objectType = result.getString(1);
    int entryId = result.getInt(2);

    Object value = selectObject(objectType, ENTRY_VALUE_TYPE, entryId);

    return (V) value;
  }

  private Collection selectObjects(final String entryType, final String objectType) throws SQLException {

    Collection objs;

    if (entryType.equals(ENTRY_KEY_TYPE)) {
      objs = new HashSet();
    } else if (entryType.equals(ENTRY_VALUE_TYPE)) {
      objs = new ArrayList();
    } else {
      return null;
    }

    PreparedStatement selectObject;

    if (objectType.equals(OBJECT_NULL_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT_NULL);
    } else if (objectType.equals(OBJECT_INTEGER_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT.replace(OBJECT_TABLE, OBJECT_INTEGER_TABLE));
    } else if (objectType.equals(OBJECT_BOOLEAN_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT.replace(OBJECT_TABLE, OBJECT_BOOLEAN_TABLE));
    } else if (objectType.equals(OBJECT_NUMERIC_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT.replace(OBJECT_TABLE, OBJECT_NUMERIC_TABLE));
    } else if (objectType.equals(OBJECT_TEXT_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT.replace(OBJECT_TABLE, OBJECT_TEXT_TABLE));
    } else if (objectType.equals(OBJECT_MAP_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT.replace(OBJECT_TABLE, OBJECT_MAP_TABLE));
    } else {
      return objs;
    }

    selectObject.setInt(1, mapId);
    selectObject.setString(2, entryType);

    ResultSet result = selectObject.executeQuery();

    while (result.next()) {
      if (objectType.equals(OBJECT_NULL_TYPE)) {
        objs.add(null);
      } else if (objectType.equals(OBJECT_INTEGER_TYPE)) {
        objs.add(result.getInt(1));
      } else if (objectType.equals(OBJECT_BOOLEAN_TYPE)) {
        objs.add(result.getBoolean(1));
      } else if (objectType.equals(OBJECT_NUMERIC_TYPE)) {
        objs.add(result.getDouble(1));
      } else if (objectType.equals(OBJECT_TEXT_TYPE)) {
        objs.add(result.getString(1));
      } else if (objectType.equals(OBJECT_MAP_TYPE)) {
        objs.add(new RdbmsMap<K, V>(connection, result.getInt(1)));
      }
    }

    return objs;
  }

  private Collection selectObjects(final String entryType) throws SQLException {

    Collection objs = selectObjects(entryType, OBJECT_NULL_TYPE);
    objs.addAll(selectObjects(entryType, OBJECT_INTEGER_TYPE));
    objs.addAll(selectObjects(entryType, OBJECT_BOOLEAN_TYPE));
    objs.addAll(selectObjects(entryType, OBJECT_NUMERIC_TYPE));
    objs.addAll(selectObjects(entryType, OBJECT_TEXT_TYPE));
    objs.addAll(selectObjects(entryType, OBJECT_MAP_TYPE));

    return objs;
  }

  private String getType(final Object obj) {

    String keyType;

    if (null == obj) {
      keyType = OBJECT_NULL_TYPE;
    } else if (obj instanceof Integer) {
      keyType = OBJECT_INTEGER_TYPE;
    } else if (obj instanceof Boolean) {
      keyType = OBJECT_BOOLEAN_TYPE;
    } else if (obj instanceof Number) {
      keyType = OBJECT_NUMERIC_TYPE;
    } else if (obj instanceof String) {
      keyType = OBJECT_TEXT_TYPE;
    } else if (obj instanceof RdbmsMap) {
      keyType = OBJECT_MAP_TYPE;
    } else {
      return null;
    }

    return keyType;
  }

  private int insertEntry(final K key, final V value) throws SQLException {

    String keyType = getType(key);
    String valueType = getType(value);

    PreparedStatement insertEntry = prepareStatement(INSERT_ENTRY);
    insertEntry.setInt(1, mapId);
    insertEntry.setString(2, keyType);
    insertEntry.setString(3, valueType);

    ResultSet result = insertEntry.executeQuery();
    if (!result.next()) {
      return 0;
    }

    return result.getInt(1);
  }

  private void insertObject(final int entryId, final Object obj, final String entryType) throws SQLException {

    String objectType = getType(obj);

    PreparedStatement insertObject;

    if (objectType.equals(OBJECT_NULL_TYPE)) {
      insertObject = prepareStatement(INSERT_OBJECT_NULL);
    } else if (objectType.equals(OBJECT_INTEGER_TYPE)) {
      insertObject = prepareStatement(INSERT_OBJECT.replace(OBJECT_TABLE, OBJECT_INTEGER_TABLE));
      insertObject.setInt(4, (Integer) obj);
    } else if (objectType.equals(OBJECT_BOOLEAN_TYPE)) {
      insertObject = prepareStatement(INSERT_OBJECT.replace(OBJECT_TABLE, OBJECT_BOOLEAN_TABLE));
      insertObject.setBoolean(4, (Boolean) obj);
    } else if (objectType.equals(OBJECT_NUMERIC_TYPE)) {
      insertObject = prepareStatement(INSERT_OBJECT.replace(OBJECT_TABLE, OBJECT_NUMERIC_TABLE));
      insertObject.setDouble(4, (Double) obj);
    } else if (objectType.equals(OBJECT_TEXT_TYPE)) {
      insertObject = prepareStatement(INSERT_OBJECT.replace(OBJECT_TABLE, OBJECT_TEXT_TABLE));
      insertObject.setString(4, (String) obj);
    } else if (objectType.equals(OBJECT_MAP_TYPE)) {
      insertObject = prepareStatement(INSERT_OBJECT.replace(OBJECT_TABLE, OBJECT_MAP_TABLE));
      insertObject.setInt(4, ((RdbmsMap) obj).mapId);
    } else {
      return;
    }

    insertObject.setInt(1, entryId);
    insertObject.setInt(2, mapId);
    insertObject.setString(3, entryType);
    insertObject.executeQuery();
  }

  private void insert(final K key, final V value) throws SQLException {

    int entryId = insertEntry(key, value);
    insertObject(entryId, key, ENTRY_KEY_TYPE);
    insertObject(entryId, value, ENTRY_VALUE_TYPE);
  }

  private void delete(final Object obj, final String entryType) throws SQLException {

    String objectType = getType(obj);

    PreparedStatement deleteEntry;
    if (objectType.equals(OBJECT_NULL_TYPE)) {
      deleteEntry = prepareStatement(DELETE_ENTRY_BY_OBJECT_NULL);
    } else if (objectType.equals(OBJECT_INTEGER_TYPE)) {
      deleteEntry = prepareStatement(DELETE_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_INTEGER_TABLE));
      deleteEntry.setInt(3, (Integer) obj);
    } else if (objectType.equals(OBJECT_BOOLEAN_TYPE)) {
      deleteEntry = prepareStatement(DELETE_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_BOOLEAN_TABLE));
      deleteEntry.setBoolean(3, (Boolean) obj);
    } else if (objectType.equals(OBJECT_NUMERIC_TYPE)) {
      deleteEntry = prepareStatement(DELETE_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_NUMERIC_TABLE));
      deleteEntry.setDouble(3, (Double) obj);
    } else if (objectType.equals(OBJECT_TEXT_TYPE)) {
      deleteEntry = prepareStatement(DELETE_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_TEXT_TABLE));
      deleteEntry.setString(3, (String) obj);
    } else if (objectType.equals(OBJECT_MAP_TYPE)) {
      deleteEntry = prepareStatement(DELETE_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_MAP_TABLE));
      deleteEntry.setInt(3, ((RdbmsMap) obj).mapId);
    } else {
      return;
    }

    deleteEntry.setInt(1, mapId);
    deleteEntry.setString(2, entryType);
    deleteEntry.executeUpdate();
  }

  private void delete() throws SQLException {

    PreparedStatement deleteEntries = prepareStatement(DELETE_ENTRIES);
    deleteEntries.setInt(1, mapId);
    deleteEntries.executeUpdate();
  }

  private Object selectObject(final String objectType, final String entryType, final int entryId) throws SQLException {

    PreparedStatement selectObject;
    if (objectType.equals(OBJECT_NULL_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT_NULL_BY_ENTRY);
    } else if (objectType.equals(OBJECT_INTEGER_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT_BY_ENTRY.replace(OBJECT_TABLE, OBJECT_INTEGER_TABLE));
    } else if (objectType.equals(OBJECT_BOOLEAN_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT_BY_ENTRY.replace(OBJECT_TABLE, OBJECT_BOOLEAN_TABLE));
    } else if (objectType.equals(OBJECT_NUMERIC_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT_BY_ENTRY.replace(OBJECT_TABLE, OBJECT_NUMERIC_TABLE));
    } else if (objectType.equals(OBJECT_TEXT_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT_BY_ENTRY.replace(OBJECT_TABLE, OBJECT_TEXT_TABLE));
    } else if (objectType.equals(OBJECT_MAP_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT_BY_ENTRY.replace(OBJECT_TABLE, OBJECT_MAP_TABLE));
    } else {
      return null;
    }

    selectObject.setInt(1, mapId);
    selectObject.setString(2, entryType);
    selectObject.setInt(3, entryId);

    ResultSet result = selectObject.executeQuery();

    if (!result.next()) {
      return null;
    }

    Object value;
    if (objectType.equals(OBJECT_NULL_TYPE)) {
      value = null;
    } else if (objectType.equals(OBJECT_INTEGER_TYPE)) {
      value = result.getInt(1);
    } else if (objectType.equals(OBJECT_BOOLEAN_TYPE)) {
      value = result.getBoolean(1);
    } else if (objectType.equals(OBJECT_NUMERIC_TYPE)) {
      value = result.getDouble(1);
    } else if (objectType.equals(OBJECT_TEXT_TYPE)) {
      value = result.getString(1);
    } else if (objectType.equals(OBJECT_MAP_TYPE)) {
      value = new RdbmsMap<K, V>(connection, result.getInt(1));
    } else {
      return null;
    }

    return value;
  }

  private Set<Entry<K, V>> selectEntries() throws SQLException {

    Set<Entry<K, V>> entries = new HashSet<Entry<K, V>>();

    PreparedStatement selectEntries = prepareStatement(SELECT_ENTRIES);
    selectEntries.setInt(1, mapId);

    ResultSet result = selectEntries.executeQuery();

    while (result.next()) {
      int entryId = result.getInt(1);
      String keyType = result.getString(2);
      String valueType = result.getString(3);

      Entry<K, V> entry = new AbstractMap.SimpleEntry<K, V>(
              (K) selectObject(keyType, ENTRY_KEY_TYPE, entryId),
              (V) selectObject(valueType, ENTRY_VALUE_TYPE, entryId));

      entries.add(entry);
    }

    return entries;
  }
}

For examples and tests check out the source code.

Source Code

• Code available in GitHub - rdbms-map