How is tile ordering determined for COGs?

[scottyhq]

(modified from a GDAL mailing list post at @rouault's suggestion: https://lists.osgeo.org/pipermail/gdal-dev/2025-January/060017.html)

I’m accustomed to GeoTiff files having row-wise sequential layout of image tiles (GDAL COG driver sorts tiles top-to-bottom,
left-to-right) But I recently was very surprised by a lot of GET requests working with SRTM data that passes COG validation scripts:

https://opentopography.s3.sdsc.edu/raster/SRTM_GL1/SRTM_GL1_srtm/N59W102.tif

I have no idea how this file came about, but the tiles are clearly non-sequential (for example here is excerpt from tiffdump: TileOffsets (324) LONG (4) 64<2269213 2409502 3485315 2716342 …)

This non-contiguous layout prevents merging consecutive GET range-requests:

CPL_DEBUG=ON gdal_translate -srcwin 0 0 1024 512 /vsicurl/https://opentopography.s3.sdsc.edu/raster/SRTM_GL1/SRTM_GL1_srtm/N59W102.tif test.tif

Since a key aspect of COGs is efficient network access, shouldn’t this file not be considered a COG? Or perhaps in the spec, there should be a place to declare the tile ordering so that readers may optimize for the smallest number of range requests?

I see a mention of different ordering schemes like Hilbert curves in this comment
#2 (comment) but not in the spec text.

[joanma747]

That is a good question. I has to go back to the TIFF 6.0 to understand what could happen.
It says:
"TileOffsets
For each tile, the byte offset of that tile, as compressed and stored on disk. The
offset is specified with respect to the beginning of the TIFF file. Note that this
implies that each tile has a location independent of the locations of other tiles.
Offsets are ordered left-to-right and top-to-bottom. "

Please note that ir says:
Offsets are ordered left-to-right and top-to-bottom
(it DOES NOT say "tiles are orderred...)

So it is clear that you cannot assume tiles are in the same order than the offsets (even if this is provably the case in many files). So the spec is giving freedom to any particular time order including Hilbert or other more convenient case (or less optimal).

Since a key aspect of COGs is efficient network access, shouldn’t this file not be considered a COG?

In my personal opinion, what makes COG fast is that you read a reduced number of bytes by selecting the right overview and reasonably small number of tiles. It is true that consecutive tiles con be requested at once and begin even more optimal but then the caching should also be more "intelligent" to take advantage of this. I wonder if some benchmarking is needed to find out. Testbed 21?

Thanks for make us realize that.

[jjimenezshaw]

My question is if COG should fix the tiles order (or not)

[rouault]

My question is if COG should fix the tiles order (or not)

That would probably be a too strong restriction, if someone would want to use any other sensible layout, such as Hilbert curves.
The spec could potentially have a recommendation/suggestion hinting that tiles should be ordered in the file in a spatial friendly way (such as row major order as used by the GDAL COG driver, Hilbert curves, etc.)

One evolution of this would be to have a "field" where one could indicate the tile ordering logic used, and that validators could use to check if a file is compliant with its advertised tile ordering. The main difficulty is where to put such a field, given we cannot in practice reserve new TIFF tags. GDAL uses a hacky "ghost" area (that is an area of the file, just after the 8-byte TIFF header, that isn't used by IFD or tiles) to sure such indication. I'm not sure we'd want to standardize such mechanism though, as it is clearly a hack, and by itself it is moderately useful. GDAL only advertizes that to also mean that there's no hole between consecutive tiles, to save reading the TileByteCount array, and just read the TileOffsets one, which may save a GET request on very large (BigTIFF) COG files where those arrays can be multi megabyte large.

[joanma747]

We could also use a new GeoTIFF Key to indicate the tile ordering.

[rouault]

We could also use a new GeoTIFF Key to indicate the tile ordering.

One can argue if the tile layout is really a geo thing... Folks in the medical imagery field could potentially use a COG