1. A method, comprising: performing, by one or more computers: storing columnar data of a database table in a plurality of physical data blocks in a distributed data storage system on behalf of one or more clients, wherein the distributed data storage system comprises a cluster of one or more nodes, each of which comprises one or more disks on which physical data blocks are stored, wherein each of the plurality of physical data blocks is associated with a respective unique identifier, and wherein said storing columnar data comprises storing two or more copies of each portion of the columnar data in different physical data blocks in the distributed data storage system; storing a backup copy of each of the plurality of physical data blocks in a remote key-value durable backup storage system, wherein for each of the plurality of physical data blocks, the respective unique identifier serves as a key to access the data block in the remote key-value durable backup storage system; receiving, from a client, a query directed to a portion of the columnar data stored in the distributed data storage system; in response to said receiving: accessing one of the plurality of physical data blocks in the distributed data storage system in which a copy of the portion of the columnar data is stored; applying a consistency check to the one of the plurality of physical data blocks; determining, based, at least in part, on said applying, that data on the one of the plurality of physical data blocks is corrupted or inconsistent with other ones of the plurality of physical data blocks; automatically retrieving the backup copy of the one of the plurality of physical data blocks stored in the remote key-value durable backup storage system, wherein said retrieving comprises using the unique identifier for the one of the one or more blocks as a key to access the backup copy of the one of the plurality of physical data blocks in the remote key-value durable backup storage system; and satisfying the query, wherein said satisfying the query comprises returning at least a portion of the data in the retrieved backup copy of the one of the plurality of physical data blocks to the client.