Changes between Initial Version and Version 1 of rfc63_sparse_datasets_improvements

Timestamp:

Jul 8, 2016, 7:17:11 AM (8 years ago)

Author:

Even Rouault

Comment:

Create RFC 63

rfc63_sparse_datasets_improvements

@@ +1 @@
+= RFC 63 : Sparse datasets improvements =
+
+Author: Even Rouault[[BR]]
+
+Contact: even.rouault at spatialys.com[[BR]]
+
+Status: Development[[BR]]
+
+Target version: 2.2
+
+== Summary ==
+
+This RFC covers an improvement to manage sparse datasets, that is to say datasets that contain substantial empty regions.
+
+== Approach ==
+
+There are use cases where one needs to read or generate a dataset that covers a large spatial extent, but in which significant parts are not covered by data. There is no way in the GDAL API to quickly know which areas are covered or not by data, hence requiring to process all pixels, which is rather inefficient. Whereas some formats like GeoTIFF, VRT or GeoPackage can potentially give such an information without processing pixels.
+
+It is thus proposed to add a new method GetDataCoverageStatus() in the GDALRasterBand class, that takes as input a window of interest and returns whether it is made of data, empty blocks or a mix of them.
+
+This method will be used by the GDALDatasetCopyWholeRaster() method (used by CreateCopy() / gdal_translate) to avoid processing sparse regions when the output driver instructs it to do so.
+
+== C++ API ==
+
+In GDALRasterBand class, a new virtual method is added :
+{{{
+ virtual int IGetDataCoverageStatus( int nXOff, int nYOff,
+                                     int nXSize, int nYSize,
+                                     int nMaskFlagStop,
+                                     double* pdfDataPct);
+
+/**
+ * \brief Get the coverage status of a sub-window of the raster.
+ *
+ * Returns whether a sub-window of the raster contains only data, only empty
+ * blocks or a mix of both.
+ *
+ * Empty blocks are blocks that contain only pixels whose value is the nodata value when it
+ * is set, or whose value is 0 when the nodata value is not set.
+ *
+ * The query is done in an efficient way without reading the actual pixel
+ * values. If not possible, GDAL_DATA_COVERAGE_STATUS_UNIMPLEMENTED will be
+ * returned.
+ *
+ * @see GDALGetDataCoverageStatus()
+ *
+ * @param nXOff The pixel offset to the top left corner of the region
+ * of the band to be queried. This would be zero to start from the left side.
+ *
+ * @param nYOff The line offset to the top left corner of the region
+ * of the band to be queried. This would be zero to start from the top.
+ *
+ * @param nXSize The width of the region of the band to be queried in pixels.
+ *
+ * @param nYSize The height of the region of the band to be queried in lines.
+ *
+ * @param nMaskFlagStop 0, or a binary-or'ed mask of possible values
+ * GDAL_DATA_COVERAGE_STATUS_UNIMPLEMENTED,
+ * GDAL_DATA_COVERAGE_STATUS_DATA and GDAL_DATA_COVERAGE_STATUS_EMPTY. As soon as
+ * the computation of the coverage matches the mask, the computation will be
+ * stopped. pdfDataPct will not be valid in that case.
+ *
+ * @param pdfDataPct Optional output parameter whose pointed value will be set
+ * to the (approximate) percentage in [0,100] of pixels in the queried sub-window that have
+ * valid values. The implementation might not always be able to compute it, in
+ * which case it will be set to a negative value.
+ *
+ * @return a binary-or'ed combination of possible values
+ * GDAL_DATA_COVERAGE_STATUS_UNIMPLEMENTED,
+ * GDAL_DATA_COVERAGE_STATUS_DATA and GDAL_DATA_COVERAGE_STATUS_EMPTY
+ *
+ * @note Added in GDAL 2.2
+ */
+}}}
+
+This method has a dumb default implementation that returns GDAL_DATA_COVERAGE_STATUS_UNIMPLEMENTED.
+
+The public API is made of :
+
+{{{
+C++ :
+
+int  GDALRasterBand::GetDataCoverageStatus( int nXOff,
+                                            int nYOff,
+                                            int nXSize,
+                                            int nYSize,
+                                            int nMaskFlagStop,
+                                            double* pdfDataPct)
+
+C :
+int GDALGetDataCoverageStatus( GDALRasterBandH hBand,
+                               int nXOff, int nYOff,
+                               int nXSize,
+                               int nYSize,
+                               int nMaskFlagStop,
+                               double* pdfDataPct);
+}}}
+
+GDALRasterBand::GetDataCoverageStatus() does basic checks on the validity of the window before calling IGetDataCoverageStatus()
+
+== Changes ==
+
+GDALDatasetCopyWholeRaster() accepts a SKIP_HOLES option that can be set to YES by the output driver to cause GetDataCoverageStatus() to be called on each chunk of the source dataset to determine if contains only holes or not.
+
+== Drivers ==
+
+This RFC upgrades the GeoTIFF and VRT drivers to implement the IGetDataCoverageStatus() method.
+
+The GeoTIFF driver has also receive a number of prior enhancements, related to that topic, for example to accept the SPARSE_OK=YES creation option in CreateCopy() mode (or the SPARSE_OK open option in update mode).
+
+Extract of the documentation of the driver:
+
+{{{
+GDAL makes a special interpretation of a TIFF tile or strip whose offset
+and byte count are set to 0, that is to say a tile or strip that has no corresponding
+allocated physical storage. On reading, such tiles or strips are considered to
+be implictly set to 0 or to the nodata value when it is defined. On writing, it
+is possible to enable generating such files through the Create() interface by setting
+the SPARSE_OK creation option to YES. Then, blocks that are never written
+through the IWriteBlock()/IRasterIO() interfaces will have their offset and
+byte count set to 0. This is particularly useful to save disk space and time when
+the file must be initialized empty before being passed to a further processing
+stage that will fill it.
+To avoid ambiguities with anoter sparse mechanism discussed in the next paragraphs,
+we will call such files with implicit tiles/strips "TIFF sparse files". They will
+be likely '''not''' interoperable with TIFF readers that are not GDAL based and
+would consider such files with implicit tiles/strips as defective.
+
+Starting with GDAL 2.2, this mechanism is extended to the CreateCopy() and
+Open() interfaces (for update mode) as well. If the SPARSE_OK creation option
+(or the SPARSE_OK open option for Open()) is set to YES, even an attempt to
+write a all 0/nodata block will be detected so that the tile/strip is not
+allocated (if it was already allocated, then its content will be replaced by
+the 0/nodata content).
+
+Starting with GDAL 2.2, in the case where SPARSE_OK is '''not''' defined (or set
+to its default value FALSE), for uncompressed files whose nodata value is not
+set, or set to 0, in Create() and CreateCopy() mode, the driver will delay the
+allocation of 0-blocks until file closing, so as to be able to write them at
+the very end of the file, and in a way compatible of the filesystem sparse file
+mechanisms (to be distinguished from the TIFF sparse file extension discussed
+earlier). That is that all the empty blocks will be seen as properly allocated
+from the TIFF point of view (corresponding strips/tiles will have valid offsets
+and byte counts), but will have no corresponding physical storage. Provided that
+the filesystem supports such sparse files, which is the case for most Linux
+popular filesystems (ext2/3/4, xfs, btfs, ...) or NTFS on Windows. If the file
+system does not support sparse files, physical storage will be
+allocated and filled with zeros.
+}}}
+
+== Bindings ==
+
+The Python bindings has a mapping of GDALGetDataCoverageStatus(). Other bindings could be updated (need to figure out how to return both a status flag and a percentage)
+
+== Utilities ==
+
+No direct changes in utilities.
+
+== Results ==
+
+With this new capability, a VRT of size 200 000 x 200 000 pixels that contains 2 regions of 20x20 pixels each can be gdal_translated as a sparse tiled GeoTIFF in 2 seconds. The resulting GeoTIFF can be itself translated into another sparse tiled GeoTIFF in the same time.
+
+== Future work ==
+
+Future work using the new capability could be done in overview building or warping. Other drivers could also benefit from that new capability: GeoPackage, ERDAS Imagine, ...
+
+== Documentation ==
+
+The new method is documented.
+
+== Test Suite ==
+
+Tests of the VRT and GeoTIFF drivers are enhanced to test their IGetDataCoverageStatus() implementation.
+
+== Compatibility Issues ==
+
+C++ ABI change. No functional incompatibility foreseen.
+
+== Implementation ==
+
+The implementation will be done by Even Rouault.
+
+The proposed implementation is in https://github.com/rouault/gdal2/tree/sparse_datasets
+
+== Voting history
+
+TBD
+