doc/html/limits.html

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

<HEAD>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

<title>Routino : Numerical Limits</title>

<!--
 Routino documentation - ID limits

 Part of the Routino routing software.

 This file Copyright 2013 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" align="center">

<h1>Routino : Numerical Limits</h1>

<hr>
</div>

<!-- Header End -->

<!-- Content Start -->

<div class="content">

<h2><a name="H_1_1"></a>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><a name="H_1_1_1"></a>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><a name="H_1_1_2"></a>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><a name="H_1_2"></a>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><a name="H_1_2_1"></a>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><a name="H_1_2_2"></a>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" align="center">
<hr>

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

</div>

<!-- Footer End -->

</BODY>

</HTML>
1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
2	<HTML>
3
4	<HEAD>
5	<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
6
7	<title>Routino : Numerical Limits</title>
8
9	<!--
10	Routino documentation - ID limits
11
12	Part of the Routino routing software.
13
14	This file Copyright 2013 Andrew M. Bishop
15
16	This program is free software: you can redistribute it and/or modify
17	it under the terms of the GNU Affero General Public License as published by
18	the Free Software Foundation, either version 3 of the License, or
19	(at your option) any later version.
20
21	This program is distributed in the hope that it will be useful,
22	but WITHOUT ANY WARRANTY; without even the implied warranty of
23	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24	GNU Affero General Public License for more details.
25
26	You should have received a copy of the GNU Affero General Public License
27	along with this program. If not, see http://www.gnu.org/licenses/.
28	-->
29
30	<link href="style.css" type="text/css" rel="stylesheet">
31	</HEAD>
32
33	<BODY>
34
35	<!-- Header Start -->
36
37	<div class="header" align="center">
38
39	<h1>Routino : Numerical Limits</h1>
40
41	<hr>
42	</div>
43
44	<!-- Header End -->
45
46	<!-- Content Start -->
47
48	<div class="content">
49
50	<h2><a name="H_1_1"></a>32/64-bit Data IDs</h2>
51
52	The
53	<a class="ext" title="OpenStreetMap" href="http://www.openstreetmap.org/">OpenStreetMap</a>
54	data uses a numerical identifier for each node, way and relation. These
55	identifiers started at 1 and increase for every new item of each type that is
56	added. When an object is deleted the identifier is not re-used so the highest
57	identifier will always be higher than the number of objects.
58
59	<p>
60	The identifier needs to be handled carefully to ensure that it does not overflow
61	the data type allocated for it. Depending on the data type used to store the
62	identifier there are are a number of numerical limits as described below:
63
64	<ol>
65	<li>If a signed 32-bit integer is used to store the identifier then the
66	maximum value that can be handled is 2147483647 (2<sup>31</sup>-1) before
67	overflow.
68	<li>If an unsigned 32-bit integer is used to store the identifier then the
69	maximum value that can be handled is 4294967295 (2<sup>32</sup>-1) before
70	overflow.
71	<li>If a signed 64-bit integer is used to store the identifier then the
72	maximum value that can be handled is 9223372036854775807 (2<sup>63</sup>-1)
73	before overflow.
74	</ol>
75
76	For the purposes of this document the possibility of overflow of a 64-bit
77	integer is ignored.
78
79	<p>
80	The part of Routino that handles the node, way and relation identifiers is the
81	<tt>planetsplitter</tt> program.
82
83
84	<h3><a name="H_1_1_1"></a>ID Above 31-bits</h3>
85
86	The first identifier exceeding 31-bits (for a node) is predicted to be created
87	in the OpenStreetMap database in February 2013.
88
89	<p>
90	All versions of Routino use unsigned 32-bit integers to store the identifier.
91	Therefore all versions of Routino will continue working correctly when node
92	number 2147483648 (2<sup>31</sup>) or higher is present.
93
94
95	<h3><a name="H_1_1_2"></a>ID Above 32-bits</h3>
96
97	The ability of Routino to handle identifiers larger than 32-bits does not depend
98	on having a 64-bit operating system.
99
100	<p>
101	Before version 2.0.1 of Routino there was no check that the identifier read from
102	the input data would fit within an unsigned 32-bit integer. Earlier versions of
103	Routino will therefore fail to report an error and will process data incorrectly
104	when node number 4294967296 (2<sup>32</sup>) or higher is present.
105
106	<p>
107	From version 2.0.2 the code is written to allow the node, way and relation
108	identifier data type to be changed to 64-bits. This means that a consistent
109	data type is used for handling identifiers and the format used for printing them
110	is consistent with the variable type.
111
112	<p>
113	From version 2.0.2 onwards it is possible to make a simple change to the code to
114	process data with node identifiers above 4294967296 (2<sup>32</sup>) without
115	error. The binary format of the database will be unchanged by the use of 64-bit
116	identifiers (since the identifiers are not stored in the database).
117
118	<p>
119	To recompile with 64-bit node identifiers the file <tt>src/typesx.h</tt> should
120	be edited and the two lines below changed from:
121
122	<pre class="boxed">
123	typedef uint32_t node_t;
124
125	#define Pnode_t PRIu32
126	</pre>
127
128	to:
129
130	<pre class="boxed">
131	typedef uint64_t node_t;
132
133	#define Pnode_t PRIu64
134	</pre>
135
136	<p>
137	A similar change can also be made for way or relation identifiers although since
138	there are currently fewer of these the limit is not as close to being reached.
139
140	<p>
141	Between version 2.0.2 and version 2.4 a bug means that route relations will
142	ignore the way or relation identifier if it is equal to 4294967295
143	(2<sup>32</sup>-1).
144
145	<p>
146	From version 2.4 onwards when a numerical limit is reached the
147	<tt>planetsplitter</tt> program will exit with an error message that describes
148	which limit was reached and which data type needs to be changed.
149
150
151	<h2><a name="H_1_2"></a>Database Format</h2>
152
153	The other limitation in Routino is the number of objects stored in the database
154	that is generated by the <tt>planetsplitter</tt> data processing. This number
155	may be significantly different from the highest identifier in the input data set
156	for two reasons. Firstly any nodes, ways or relations that have been deleted
157	will not be present in the data. Secondly when a partial planet database
158	(continent, country or smaller) is processed there will be only a fraction of
159	the total number of nodes, ways and relations.
160
161	<p>
162	The limiting factor is the largest of the following.
163	<ol>
164	<li>The number of nodes in the input data files.
165	<li>The number of segments in the input data files.
166	<li>The number of highways in the input data files.
167	<li>The number of relations in the input data files.
168	</ol>
169
170	Normally the number of nodes will be the limiting factor.
171
172
173	<h3><a name="H_1_2_1"></a>32-bit Indexes</h3>
174
175	Before version 1.2 the database could hold up to 4294967295 (2<sup>32</sup>-1)
176	items of each type (node, segment, way) since an unsigned 32-bit integer is
177	used.
178
179	<p>
180	Versions 1.3 to 1.4.1 have a limit of 2147483647 (2<sup>31</sup>-1) items since
181	half of the 32-bit integer range is reserved for fake nodes and segments that
182	are inserted if a waypoint is not close to a node.
183
184	<p>
185	From version 1.5 the limit is 4294901760 (2<sup>32</sup>-2<sup>16</sup>) for the
186	number of items of each type that can be stored. The small remaining part of
187	the 32-bit unsigned integer range is reserved for fake nodes and segments.
188
189
190	<h3><a name="H_1_2_2"></a>64-bit Indexes</h3>
191
192	When using a 32-bit operating system it is not possible to create a database
193	that exceeds about 2GB in total. This will be fewer than 2<sup>32</sup> objects
194	in the database in total. The use of 64-bit indexes will require a 64-bit
195	operating system.
196
197	<p>
198	From version 2.0.2 onwards it is possible to make a simple change to the code to
199	index the database objects with 64-bit integers insted of 32-bit integers.
200
201	<p>
202	To recompile with 64-bit index integers the file <tt>src/types.h</tt> should be
203	edited and the two lines below changed from:
204
205	<pre class="boxed">
206	typedef uint32_t index_t;
207
208	#define Pindex_t PRIu32
209	</pre>
210
211	to:
212
213	<pre class="boxed">
214	typedef uint64_t index_t;
215
216	#define Pindex_t PRIu64
217	</pre>
218
219	This change will affect nodes, segments, ways and relations together. The
220	database that is generated will no longer be compatible with Routino that has
221	been compiled with 32-bit indexes. The size of the database will also grow by
222	about 50% when this change is made.
223
224
225	</div>
226
227	<!-- Content End -->
228
229	<!-- Footer Start -->
230
231	<div class="footer" align="center">
232	<hr>
233
234	<address>
235	© Andrew M. Bishop - <a href="http://www.routino.org/">http://www.routino.org/</a>
236	</address>
237
238	</div>
239
240	<!-- Footer End -->
241
242	</BODY>
243
244	</HTML>