/usr/share/doc/routino/html/limits.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>

<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1">

<title>Routino : Numerical Limits</title>

<!--
 Routino documentation - ID limits

 Part of the Routino routing software.

 This file Copyright 2013-2015 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see http://www.gnu.org/licenses/.
-->

<link href="style.css" type="text/css" rel="stylesheet">
</head>

<body>

<!-- Header Start -->

<div class="header">

<h1>Routino : Numerical Limits</h1>

</div>

<!-- Header End -->

<!-- Content Start -->

<div class="content">

<h2 id="H_1_1">32/64-bit Data IDs</h2>

The
<a class="ext" title="OpenStreetMap" href="http://www.openstreetmap.org/">OpenStreetMap</a>
data uses a numerical identifier for each node, way and relation.  These
identifiers started at 1 and increase for every new item of each type that is
added.  When an object is deleted the identifier is not re-used so the highest
identifier will always be higher than the number of objects.

<p>
The identifier needs to be handled carefully to ensure that it does not overflow
the data type allocated for it.  Depending on the data type used to store the
identifier there are are a number of numerical limits as described below:

<ol>
  <li>If a signed 32-bit integer is used to store the identifier then the
    maximum value that can be handled is 2147483647 (2<sup>31</sup>-1) before
    overflow.
  <li>If an unsigned 32-bit integer is used to store the identifier then the
    maximum value that can be handled is 4294967295 (2<sup>32</sup>-1) before
    overflow.
  <li>If a signed 64-bit integer is used to store the identifier then the
    maximum value that can be handled is 9223372036854775807 (2<sup>63</sup>-1)
    before overflow.
</ol>

For the purposes of this document the possibility of overflow of a 64-bit
integer is ignored.

<p>
The part of Routino that handles the node, way and relation identifiers is the
<tt>planetsplitter</tt> program.


<h3 id="H_1_1_1">ID Above 31-bits</h3>

The first identifier exceeding 31-bits (for a node) is predicted to be created
in the OpenStreetMap database in February 2013.

<p>
All versions of Routino use unsigned 32-bit integers to store the identifier.
Therefore all versions of Routino will continue working correctly when node
number 2147483648 (2<sup>31</sup>) or higher is present.


<h3 id="H_1_1_2">ID Above 32-bits</h3>

The ability of Routino to handle identifiers larger than 32-bits does not depend
on having a 64-bit operating system.

<p>
Before version 2.0.1 of Routino there was no check that the identifier read from
the input data would fit within an unsigned 32-bit integer.  Earlier versions of
Routino will therefore fail to report an error and will process data incorrectly
when node number 4294967296 (2<sup>32</sup>) or higher is present.

<p>
From version 2.0.2 the code is written to allow the node, way and relation
identifier data type to be changed to 64-bits.  This means that a consistent
data type is used for handling identifiers and the format used for printing them
is consistent with the variable type.

<p>
From version 2.0.2 onwards it is possible to make a simple change to the code to
process data with node identifiers above 4294967296 (2<sup>32</sup>) without
error.  The binary format of the database will be unchanged by the use of 64-bit
identifiers (since the identifiers are not stored in the database).

<p>
To recompile with 64-bit node identifiers the file <tt>src/typesx.h</tt> should
be edited and the two lines below changed from:

<pre class="boxed">
typedef uint32_t node_t;

#define Pnode_t PRIu32
</pre>

to:

<pre class="boxed">
typedef uint64_t node_t;

#define Pnode_t PRIu64
</pre>

<p>
A similar change can also be made for way or relation identifiers although since
there are currently fewer of these the limit is not as close to being reached.

<p>
Between version 2.0.2 and version 2.4 a bug means that route relations will
ignore the way or relation identifier if it is equal to 4294967295
(2<sup>32</sup>-1).

<p>
From version 2.4 onwards when a numerical limit is reached the
<tt>planetsplitter</tt> program will exit with an error message that describes
which limit was reached and which data type needs to be changed.


<h2 id="H_1_2">Database Format</h2>

The other limitation in Routino is the number of objects stored in the database
that is generated by the <tt>planetsplitter</tt> data processing.  This number
may be significantly different from the highest identifier in the input data set
for two reasons.  Firstly any nodes, ways or relations that have been deleted
will not be present in the data.  Secondly when a partial planet database
(continent, country or smaller) is processed there will be only a fraction of
the total number of nodes, ways and relations.

<p>
The limiting factor is the largest of the following.
<ol>
  <li>The number of nodes in the input data files.
  <li>The number of segments in the input data files.
  <li>The number of highways in the input data files.
  <li>The number of relations in the input data files.
</ol>

Normally the number of nodes will be the limiting factor.


<h3 id="H_1_2_1">32-bit Indexes</h3>

Before version 1.2 the database could hold up to 4294967295 (2<sup>32</sup>-1)
items of each type (node, segment, way) since an unsigned 32-bit integer is
used.

<p>
Versions 1.3 to 1.4.1 have a limit of 2147483647 (2<sup>31</sup>-1) items since
half of the 32-bit integer range is reserved for fake nodes and segments that
are inserted if a waypoint is not close to a node.

<p>
From version 1.5 the limit is 4294901760 (2<sup>32</sup>-2<sup>16</sup>) for the
number of items of each type that can be stored.  The small remaining part of
the 32-bit unsigned integer range is reserved for fake nodes and segments.


<h3 id="H_1_2_2">64-bit Indexes</h3>

When using a 32-bit operating system it is not possible to create a database
that exceeds about 2GB in total.  This will be fewer than 2<sup>32</sup> objects
in the database in total.  The use of 64-bit indexes will require a 64-bit
operating system.

<p>
From version 2.0.2 onwards it is possible to make a simple change to the code to
index the database objects with 64-bit integers insted of 32-bit integers.

<p>
To recompile with 64-bit index integers the file <tt>src/types.h</tt> should be
edited and the two lines below changed from:

<pre class="boxed">
typedef uint32_t index_t;

#define Pindex_t PRIu32
</pre>

to:

<pre class="boxed">
typedef uint64_t index_t;

#define Pindex_t PRIu64
</pre>

This change will affect nodes, segments, ways and relations together.  The
database that is generated will no longer be compatible with Routino that has
been compiled with 32-bit indexes.  The size of the database will also grow by
about 50% when this change is made.


</div>

<!-- Content End -->

<!-- Footer Start -->

<div class="footer">

<address>
&copy; Andrew M. Bishop - <a href="http://www.routino.org/">http://www.routino.org/</a>
</address>

</div>

<!-- Footer End -->

</body>

</html>
routino 3.0-3 / usr / share / doc / routino / html / limits.html
