Policy-based, cell-level access control is provided in association with a sorted, distributed key-value data store. As data representing a hierarchical document is ingested into the data store, the data is interpreted to identify fields and any sub-fields in the document, each identified field and its associated protection level as identified are translated into a set of one or more fieldname and visibility label pairs. Each fieldname and visibility label pair has a fieldname identifying a field and its zero or more sub-fields, together with a visibility label that is a function of the associated protection levels of the field and any sub-fields therein. At query time, and in response to receipt of a query including an authorization label, the fieldname and visibility labels are applied against the authorization label in the query to control which fields in the document are retrieved and used to generate the response to the query.