packages feed

rocksdb-query 0.6.1 → 0.7.0

raw patch · 6 files changed

+495/−77 lines, 6 filesdep ~rocksdb-haskell-jpruppsetup-changedPVP ok

version bump matches the API change (PVP)

Dependency ranges changed: rocksdb-haskell-jprupp

API changes (from Hackage documentation)

Files

CHANGELOG.md view
@@ -4,6 +4,32 @@ The format is based on [Keep a Changelog](http://keepachangelog.com/en/1.0.0/) and this project adheres to [Semantic Versioning](http://semver.org/spec/v2.0.0.html). +## 0.7.0 - 2026-11-15+### Changed+- Prefix queries read the database in chunks, through `iterChunk` of+  rocksdb-haskell-jprupp 2.8.0, which is now required. They made a call into+  RocksDB for every entry, and each such call costs a Haskell thread its+  capability, which it has to wait for under load. Lists now read up to 256+  entries or a megabyte per call. Conduits read 16 entries, then 64, then+  256 at a time, so that a consumer who stops early has made the database+  read little more than it took.+- The list functions no longer use stack for every entry. Their loop left a+  frame there for each one, and the run-time system walks the stack at every+  call that may block, so each entry cost more the longer the list was.+- Together, `matchingAsList` on four cores: 2,000 entries in 1 ms where they+  took 5, and from sixteen threads at once in 6 ms where they took 48;+  200,000 entries in 0.12 s where they took 0.54, and from sixteen threads+  in 0.92 s where they took 4.8.+- `firstMatching` and its variants read the one entry and nothing after it,+  without a conduit.+- A failure of RocksDB to read, such as a corrupt block, is thrown as an+  `IOError`. It used to look like the end of the data, and the result was+  only shorter.+- After a consumer of `matching` or `matchingSkip` stops, the iterator is+  past the entries read ahead, and no longer on the last one yielded.+- The module has an export list. It exports everything that it did before;+  the helpers that are new stay internal.+ ## 0.6.1 ### Changed - Documentation: the README explains the purpose and design of the library,
README.md view
@@ -118,8 +118,8 @@  ```yaml extra-deps:-  - rocksdb-query-0.6.1-  - rocksdb-haskell-jprupp-2.6.1+  - rocksdb-query-0.7.0+  - rocksdb-haskell-jprupp-2.8.0 ```  ## Quick start@@ -308,10 +308,11 @@ | Function            | Returns                                      | | ------------------- | -------------------------------------------- | | `matchingAsList`    | every match, as a list                       |-| `firstMatching`     | the first match                              |+| `firstMatching`     | the first match, reading that entry only     | | `matching`          | every match, as a conduit, on your iterator  | -The conduit version reads lazily, so it suits prefixes with many matches:+The conduit version reads as its consumer asks, so it suits prefixes with+many matches, and consumers that stop early:  ```haskell import Conduit@@ -321,6 +322,38 @@   runConduit $ matching it (OrderKeyS 1) .| mapC (qty . snd) .| sumC ``` +### How a prefix is read++Moving a RocksDB iterator is a foreign call that may wait for the disk, and+Haskell pays for each such call: the thread gives up its capability and has+to get one back, which under load means waiting for one. So a prefix is not+read one entry per call, but in chunks, with `iterChunk` of+rocksdb-haskell-jprupp:++- **Lists** read up to 256 entries, or a megabyte of them, per call. More+  per call gains nothing that can be measured; the megabyte keeps large+  values from being held 256 at a time.+- **Conduits** read 16 entries first, then four times as many with each+  chunk, up to the same 256. A consumer that takes three entries makes the+  database read 16; one that takes thousands is soon at full size. When the+  consumer stops, the iterator is past what was read ahead, not on the last+  entry yielded.+- **`firstMatching`** and its variants read one entry and move nowhere.++The lists are also built without using stack for each entry. Seconds to read+a list with `matchingAsList`, on four cores, before and after both changes:++| Entries | Threads | 0.6.1 | 0.7.0 |+| ------- | ------- | ----- | ----- |+| 2,000   | 1       | 0.005 | 0.001 |+| 2,000   | 16      | 0.048 | 0.006 |+| 200,000 | 1       | 0.54  | 0.12  |+| 200,000 | 16      | 4.8   | 0.92  |++If RocksDB fails to read, with a corrupt block for instance, the queries+throw an `IOError`. They do not return what they had as if the data ended+there.+ ### Pagination  The `Skip` variants start inside the prefix at a given key, or the next one@@ -388,6 +421,9 @@ `rocksdb-query.cabal`, which [hpack](https://github.com/sol/hpack) generates.  The tests are in `test/Spec.hs` and use [hspec](https://hspec.github.io/).+They run with a stack of at most 1 MiB, so that a query whose stack grows+with its result fails on the lists of a hundred thousand records instead of+only being slow.  ### Contributing 
Setup.hs view
@@ -1,2 +1,3 @@ import Distribution.Simple+ main = defaultMain
rocksdb-query.cabal view
@@ -5,7 +5,7 @@ -- see: https://github.com/sol/hpack  name:           rocksdb-query-version:        0.6.1+version:        0.7.0 synopsis:       RocksDB database querying library for Haskell description:    Please see the README on GitHub at <https://github.com/jprupp/rocksdb-query#readme> category:       Database@@ -36,7 +36,8 @@     , bytestring     , cereal     , conduit-    , rocksdb-haskell-jprupp >=2.3.0+    , data-default+    , rocksdb-haskell-jprupp >=2.8.0   default-language: Haskell2010  test-suite rocksdb-query-test@@ -46,13 +47,15 @@       Paths_rocksdb_query   hs-source-dirs:       test-  ghc-options: -threaded -rtsopts -with-rtsopts=-N+  ghc-options: -threaded -rtsopts "-with-rtsopts=-N -K1m"   build-depends:       base >=4.7 && <5+    , bytestring     , cereal+    , conduit     , data-default     , hspec-    , rocksdb-haskell-jprupp >=2.3.0+    , rocksdb-haskell-jprupp >=2.8.0     , rocksdb-query     , temporary   default-language: Haskell2010
src/Database/RocksDB/Query.hs view
@@ -70,6 +70,17 @@ -- full keys, and returns every entry whose key starts with that prefix. See -- 'matching' for an example. --+-- = How a prefix is read+--+-- A prefix query reads the database in chunks: up to 256 entries, or a+-- megabyte of them, from one call into RocksDB. Moving an iterator is a+-- foreign call that may wait for the disk, and Haskell pays for each such+-- call, so one call per entry made long lists slow, and slower still when+-- many threads read at once. The list functions read whole chunks from the+-- start. The conduits start with 16 entries and grow, so that a consumer who+-- stops early has not made the database read much more than it took. The+-- functions that return the first match read one entry and no more.+-- -- = Decoding errors -- -- If a stored key or value cannot be decoded, these functions call 'error'.@@ -80,11 +91,50 @@ -- -- Functions ending in @CF@ act on a given column family. The others act on the -- default column family.-module Database.RocksDB.Query where+module Database.RocksDB.Query+  ( -- * Schema+    Key,+    KeyValue, +    -- * Reading and writing+    retrieve,+    retrieveCF,+    insert,+    insertCF,+    remove,+    removeCF,++    -- * Batches+    insertOp,+    insertOpCF,+    deleteOp,+    deleteOpCF,+    writeBatch,++    -- * Prefix queries+    matchingAsList,+    matchingAsListCF,+    matchingSkipAsList,+    matchingSkipAsListCF,+    firstMatching,+    firstMatchingCF,+    firstMatchingSkip,+    firstMatchingSkipCF,+    matching,+    matchingSkip,++    -- * Internal+    retrieveCommon,+    matchRecursiveList,+    matchRecursive,+  )+where+ import Conduit import Control.Monad import Data.ByteString qualified as B+import Data.ByteString.Char8 qualified as C+import Data.Default (def) import Data.Serialize as S import Database.RocksDB as R @@ -143,31 +193,91 @@       Just cf -> R.getCF db cf (encode key)       Nothing -> R.get db (encode key) +-- | The most entries that a prefix query reads from the database in one+-- call.+--+-- An iterator moves in a foreign call that may wait for the disk, and such a+-- call has a cost of its own in Haskell: the thread gives up its capability+-- and has to get one back. Reading one entry per call, a long list paid that+-- once for every entry. At 256 entries per call the cost is spread so thin+-- that a larger number gains nothing that the benchmark of+-- @rocksdb-haskell-jprupp@ can measure, while it would make a consumer that+-- stops early read more entries that it does not want.+chunkMost :: Int+chunkMost = 256++-- | The entries that a conduit reads in its first call. Each call after it+-- reads four times as many, up to 'chunkMost'.+--+-- A conduit does not know how much its consumer will take. Starting small+-- means that one who takes a few entries makes the database read 16 and not+-- 256; growing fast means that one who takes thousands is at full size+-- from the third call on.+chunkFirst :: Int+chunkFirst = 16++-- | The most bytes of keys and values that a prefix query reads in one call,+-- 1 MiB. One entry is always read, whatever its size.+--+-- It bounds the memory that a query holds beyond its result. A chunk is in+-- memory twice for a moment, as the bytes read and as the values decoded+-- from them, and 256 values can be of any size: without this limit, 256+-- values of a megabyte would be read at once to yield the first.+chunkBytesMost :: Int+chunkBytesMost = 1024 * 1024++-- | The chunk of so many entries, at most, whose keys start with the given+-- bytes.+chunkOf :: B.ByteString -> Int -> ChunkConfig+chunkOf prefix n =+  def+    { chunkPrefix = prefix,+      chunkEntries = n,+      chunkBytes = chunkBytesMost+    }++-- | Decode an entry read from the database. Calls 'error' if the key or the+-- value cannot be decoded, when the action runs and not when its result is+-- looked at.+decodeEntry ::+  (Serialize key, Serialize value) =>+  (B.ByteString, B.ByteString) ->+  IO (key, value)+decodeEntry (key_bytes, value_bytes) = do+  key <- either error return (decode key_bytes)+  value <- either error return (decode value_bytes)+  return (key, value)+ -- | Internal function to collect, from the current position of the iterator, -- every entry whose key starts with the encoding of the given key. Stops at the -- first entry that does not match.+--+-- It reads 256 entries at a time, and keeps what it has read in an argument+-- of its loop, so that the stack does not grow with the list.+-- That matters for more than memory: the run-time system walks the stack of+-- a thread at every foreign call that may block, so a loop that left a frame+-- there for each entry got slower with every entry it read. matchRecursiveList ::   (KeyValue key value, Serialize key, Serialize value) =>   key ->   Iterator ->   IO [(key, value)]-matchRecursiveList base it = go+matchRecursiveList base it = go []   where-    go =-      iterEntry it >>= \case-        Nothing -> return []-        Just (key_bytes, value_bytes) ->-          if base_bytes `B.isPrefixOf` key_bytes-            then do-              key <- either error return (decode key_bytes)-              value <- either error return (decode value_bytes)-              iterNext it-              ((key, value) :) <$> go-            else return []-    base_bytes = encode base+    go acc = do+      (entries, more) <- iterChunk it chunk+      acc' <- foldM (\done entry -> (: done) <$> decodeEntry entry) acc entries+      if more then go acc' else return (reverse acc')+    chunk = chunkOf (encode base) chunkMost  -- | Internal function for recursively matching a key. Like -- 'matchRecursiveList', but streams the entries through a conduit.+--+-- It reads a chunk, yields its entries one by one, and reads the next chunk+-- only when the consumer asks for more: nothing is read for a consumer that+-- has stopped. The chunks start at 16 entries and grow to 256. An entry is+-- decoded when it is its turn to be yielded, so an entry that cannot be+-- decoded is an error only for a consumer that gets as far as it. matchRecursive ::   ( KeyValue key value,     Serialize key,@@ -176,20 +286,35 @@   key ->   Iterator ->   ConduitT i (key, value) IO ()-matchRecursive base it = go+matchRecursive base it = go chunkFirst   where-    go =-      liftIO (iterEntry it) >>= \case-        Nothing -> return ()-        Just (key_bytes, value_bytes) ->-          when (base_bytes `B.isPrefixOf` key_bytes) $ do-            key <- either error return (decode key_bytes)-            value <- either error return (decode value_bytes)-            yield (key, value)-            liftIO (iterNext it)-            go+    go n = do+      (entries, more) <- liftIO (iterChunk it (chunkOf base_bytes n))+      forM_ entries (liftIO . decodeEntry >=> yield)+      when more $ go (min chunkMost (n * 4))     base_bytes = encode base +-- | Internal function to read the entry that the iterator is on, if its key+-- starts with the encoding of the given key.+--+-- It reads the one entry in place, with no call that moves the iterator: a+-- chunk would read on past the entry that is wanted.+matchFirst ::+  (KeyValue key value, Serialize key, Serialize value) =>+  key ->+  Iterator ->+  IO (Maybe (key, value))+matchFirst base it =+  iterEntry it >>= \case+    Just entry+      | encode base `B.isPrefixOf` fst entry -> Just <$> decodeEntry entry+      | otherwise -> return Nothing+    Nothing -> do+      -- no entry here: the end of the data, unless the iterator says that+      -- it could not read+      iterGetError it >>= mapM_ (ioError . userError . ("firstMatching: " <>) . C.unpack)+      return Nothing+ -- | Pass a short key to filter all the elements whose key prefix match it. Use -- a sum type for keys that allows to create a version of the key that -- serializes to a prefix of a full key.@@ -209,7 +334,7 @@ -- >     -- (FullKey "hello" "world","despite all my rage") -- -- In this example the @ShortKey@ is serialized to the prefix of the only--- element in the database, which is then returned. Since the 'get' function of+-- element in the database, which is then returned. Since the 'S.get' function of -- the 'Serialize' instance for @MyKey@ only understands how to deserialize a -- @FullKey@, then that is what is returned. --@@ -220,8 +345,15 @@ -- themselves. -- -- The conduit version exists for sets too large to hold in memory, and for--- consumers that stop early: only the entries that are actually consumed are read--- from the database.+-- consumers that stop early. It reads the database in chunks, a little ahead+-- of its consumer: 16 entries at first, then four times as many with each+-- chunk, up to 256 entries or a megabyte. So a consumer that takes three+-- entries makes the database read 16, and one that takes thousands costs a+-- call into RocksDB for every 256 and not for each. Do not rely on where the+-- iterator is when the consumer stops: it is past the entries read ahead.+--+-- Throws an 'IOError' if RocksDB fails to read, where a short result would+-- otherwise look like the end of the data. matching ::   ( KeyValue key value,     Serialize key,@@ -326,6 +458,10 @@  -- | Like 'matching' but return the first element only, or 'Nothing' if no key -- starts with the prefix. Opens and closes its own iterator.+--+-- It reads that one entry and no further: a seek, and the entry under the+-- iterator. Use it, and not the head of a list or of a conduit, when one+-- entry is all that is wanted. firstMatching ::   ( KeyValue key value,     Serialize key,@@ -335,7 +471,9 @@   key ->   IO (Maybe (key, value)) firstMatching db base =-  withIter db $ \it -> runConduit $ matching it base .| headC+  withIter db $ \it -> do+    iterSeek it (encode base)+    matchFirst base it  -- | Like 'firstMatching', but read from the given column family. firstMatchingCF ::@@ -348,7 +486,9 @@   key ->   IO (Maybe (key, value)) firstMatchingCF db cf base =-  withIterCF db cf $ \it -> runConduit $ matching it base .| headC+  withIterCF db cf $ \it -> do+    iterSeek it (encode base)+    matchFirst base it  -- | Like 'matchingSkip', but return the first element only. Opens and closes -- its own iterator.@@ -362,9 +502,9 @@   key ->   IO (Maybe (key, value)) firstMatchingSkip db base start =-  withIter db $ \it ->-    runConduit $-      matchingSkip it base start .| headC+  withIter db $ \it -> do+    iterSeek it (encode start)+    matchFirst base it  -- | Like 'firstMatchingSkip', but read from the given column family. firstMatchingSkipCF ::@@ -378,13 +518,17 @@   key ->   IO (Maybe (key, value)) firstMatchingSkipCF db cf base start =-  withIterCF db cf $ \it ->-    runConduit $-      matchingSkip it base start .| headC+  withIterCF db cf $ \it -> do+    iterSeek it (encode start)+    matchFirst base it  -- | Like 'matching' but return a list. Opens and closes its own iterator. All -- matching entries are loaded into memory, so use 'matching' for prefixes that -- may match many entries.+--+-- The list is complete when the function returns: nothing of it is read+-- lazily, so the iterator can be closed. It is read in chunks of 256 entries+-- or a megabyte, and the time it takes grows in step with its length. matchingAsList ::   ( KeyValue key value,     Serialize key,
test/Spec.hs view
@@ -1,8 +1,26 @@ {-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE ImportQualifiedPost #-} {-# LANGUAGE MultiParamTypeClasses #-} +-- |+-- Tests of "Database.RocksDB.Query" against a real RocksDB, in temporary+-- directories.+--+-- The first group pins down what each function returns, on a handful of+-- records. The second is about how a prefix is read: in chunks, from one+-- call into RocksDB for many entries. Chunks must not show in the results,+-- so those tests use lists longer than any chunk, lists that end exactly+-- where a chunk does, and values larger than a chunk may be. The suite runs+-- with a stack of 1 MiB at most, so that a query whose stack grows with its+-- result fails on the long lists.+module Main (main) where++import Conduit import Control.Applicative+import Control.Exception (ErrorCall, evaluate) import Control.Monad+import Data.ByteString (ByteString)+import Data.ByteString qualified as B import Data.Default import Data.Serialize as S import Data.Word@@ -20,10 +38,19 @@   | KeyTwoBase Word32   deriving (Show, Eq) +-- | Keys of the tests of chunks: a group, and a number within it. They sort+-- after every 'KeyTwo'.+data KeyRun+  = KeyRun Word32 Word32+  | KeyRunBase Word32+  deriving (Show, Eq)+ instance KeyValue KeyTwo String  instance KeyValue KeyOne String +instance KeyValue KeyRun ByteString+ instance Serialize KeyOne where   put (KeyOne x) = do     putWord8 0x01@@ -42,42 +69,39 @@     (guard . (== 0x02) =<< getWord8)       >> KeyTwo <$> S.get <*> S.get <|> KeyTwoBase <$> S.get +instance Serialize KeyRun where+  put k = do+    putWord8 0x03+    case k of+      KeyRunBase g -> S.put g+      KeyRun g n -> S.put g >> S.put n+  get = do+    getWord8 >>= guard . (== 0x03)+    KeyRun <$> S.get <*> S.get+ main :: IO ()-main =-  setup $ \db ->-    describe "database" $ do-      it "reads a record" $ do-        r <- retrieve db (KeyTwo 1 2)-        r `shouldBe` Just "Hello First World Again!"-      it "reads two records at the end" $ do-        let ls =-              [ (KeyTwo 2 1, "Hello Second World!"),-                (KeyTwo 2 2, "Hello Second World Again!")-              ]-        rs <- matchingAsList db (KeyTwoBase 2)-        rs `shouldBe` ls-      it "reads two records in the middle" $ do-        let ls =-              [ (KeyTwo 1 1, "Hello First World!"),-                (KeyTwo 1 2, "Hello First World Again!")-              ]-        rs <- matchingAsList db (KeyTwoBase 1)-        rs `shouldBe` ls-      it "query and skip" $ do-        let ex = (KeyTwo 2 2, "Hello Second World Again!")-        rs <--          matchingSkipAsList-            db-            (KeyTwoBase 2)-            (KeyTwo 2 2)-        rs `shouldBe` [ex]+main = hspec $ do+  around withRecords recordSpec+  around withEmpty chunkSpec++-- | A new database in a temporary directory, with a second column family.+withEmpty :: (DB -> IO a) -> IO a+withEmpty f =+  withSystemTempDirectory "rocksdb-query-test-" $ \d ->+    withDBCF d cfg [("other", cfg)] f   where-    setup f =-      withSystemTempDirectory "rocksdb-query-test-" $ \d ->-        withDB d def {createIfMissing = True} $ \db -> do-          insertTestRecords db-          hspec $ f db+    cfg = def {createIfMissing = True, createMissingColumnFamilies = True} +-- | A new database with the records of 'insertTestRecords'.+withRecords :: (DB -> IO a) -> IO a+withRecords f = withEmpty $ \db -> insertTestRecords db >> f db++-- | The second column family of the test database.+other :: DB -> ColumnFamily+other db = case columnFamilies db of+  cf : _ -> cf+  [] -> error "the test database has no column family"+ insertTestRecords :: DB -> IO () insertTestRecords db = do   insert db (KeyOne 1) "Hello World!"@@ -86,3 +110,187 @@   insert db (KeyTwo 1 2) "Hello First World Again!"   insert db (KeyTwo 2 1) "Hello Second World!"   insert db (KeyTwo 2 2) "Hello Second World Again!"++recordSpec :: SpecWith DB+recordSpec =+  describe "database" $ do+    it "reads a record" $ \db -> do+      r <- retrieve db (KeyTwo 1 2)+      r `shouldBe` Just "Hello First World Again!"+    it "reads two records at the end" $ \db -> do+      let ls =+            [ (KeyTwo 2 1, "Hello Second World!"),+              (KeyTwo 2 2, "Hello Second World Again!")+            ]+      rs <- matchingAsList db (KeyTwoBase 2)+      rs `shouldBe` ls+    it "reads two records in the middle" $ \db -> do+      let ls =+            [ (KeyTwo 1 1, "Hello First World!"),+              (KeyTwo 1 2, "Hello First World Again!")+            ]+      rs <- matchingAsList db (KeyTwoBase 1)+      rs `shouldBe` ls+    it "query and skip" $ \db -> do+      let ex = (KeyTwo 2 2, "Hello Second World Again!")+      rs <-+        matchingSkipAsList+          db+          (KeyTwoBase 2)+          (KeyTwo 2 2)+      rs `shouldBe` [ex]+    it "reads nothing for a prefix that no key has" $ \db -> do+      rs <- matchingAsList db (KeyTwoBase 3)+      rs `shouldBe` ([] :: [(KeyTwo, String)])+      r <- firstMatching db (KeyTwoBase 3)+      r `shouldBe` nothing+      r' <- firstMatching db (KeyTwoBase 0)+      r' `shouldBe` nothing+    it "reads the first record of a prefix" $ \db -> do+      r <- firstMatching db (KeyTwoBase 1)+      r `shouldBe` Just (KeyTwo 1 1, "Hello First World!")+      r' <- firstMatching db (KeyTwoBase 2)+      r' `shouldBe` Just (KeyTwo 2 1, "Hello Second World!")+    it "reads the first record from a key on" $ \db -> do+      r <- firstMatchingSkip db (KeyTwoBase 1) (KeyTwo 1 2)+      r `shouldBe` Just (KeyTwo 1 2, "Hello First World Again!")+      -- past the last key of the prefix, and of the database+      r' <- firstMatchingSkip db (KeyTwoBase 1) (KeyTwo 1 3)+      r' `shouldBe` nothing+      r'' <- firstMatchingSkip db (KeyTwoBase 2) (KeyTwo 2 3)+      r'' `shouldBe` nothing+    it "streams the records of a prefix" $ \db -> do+      rs <- withIter db $ \it -> runConduit $ matching it (KeyTwoBase 1) .| sinkList+      rs+        `shouldBe` [ (KeyTwo 1 1, "Hello First World!"),+                     (KeyTwo 1 2, "Hello First World Again!")+                   ]+      rs' <- withIter db $ \it ->+        runConduit $ matchingSkip it (KeyTwoBase 2) (KeyTwo 2 2) .| sinkList+      rs' `shouldBe` [(KeyTwo 2 2, "Hello Second World Again!")]++-- | No record under a 'KeyTwo', for where nothing else says the type of the+-- value that was not found.+nothing :: Maybe (KeyTwo, String)+nothing = Nothing++-- | The value of an entry of a run: short, and different for every key.+runValue :: Word32 -> Word32 -> ByteString+runValue g n = encode (g * 1000003 + n)++-- | The entries of a run of so many keys in a group, in order.+run :: Word32 -> Word32 -> [(KeyRun, ByteString)]+run g count = [(KeyRun g n, runValue g n) | n <- [0 .. count - 1], count > 0]++-- | Write a run to a column family, or to the default one.+insertRun :: DB -> Maybe ColumnFamily -> Word32 -> Word32 -> IO ()+insertRun db mcf g count = mapM_ (writeBatch db) (pieces (map op (run g count)))+  where+    op (k, v) = maybe (insertOp k v) (\cf -> insertOpCF cf k v) mcf+    pieces [] = []+    pieces ops = let (a, b) = splitAt 1000 ops in a : pieces b++-- | Every way of reading a whole prefix, which all have to agree.+everyWay :: DB -> KeyRun -> IO [[(KeyRun, ByteString)]]+everyWay db base =+  sequence+    [ matchingAsList db base,+      withIter db $ \it -> runConduit $ matching it base .| sinkList+    ]++chunkSpec :: SpecWith DB+chunkSpec =+  describe "prefixes read in chunks" $ do+    it "reads a list of a hundred thousand records" $ \db -> do+      insertRun db Nothing 1 100000+      insertRun db Nothing 2 10+      rs <- matchingAsList db (KeyRunBase 1)+      length rs `shouldBe` 100000+      rs `shouldBe` run 1 100000+    it "streams a hundred thousand records" $ \db -> do+      insertRun db Nothing 1 100000+      insertRun db Nothing 2 10+      withIter db $ \it -> do+        rs <- runConduit $ matching it (KeyRunBase 1) .| sinkList+        rs `shouldBe` run 1 100000+        n <- runConduit $ stream it (KeyRunBase 1) .| lengthC+        n `shouldBe` (100000 :: Int)+    it "reads long lists from a key on, in a column family" $ \db -> do+      insertRun db (Just (other db)) 1 30000+      insertRun db (Just (other db)) 2 10+      rs <- matchingSkipAsListCF db (other db) (KeyRunBase 1) (KeyRun 1 12345)+      rs `shouldBe` drop 12345 (run 1 30000)+      rs' <- matchingAsListCF db (other db) (KeyRunBase 1)+      rs' `shouldBe` run 1 30000+      rs'' <- withIterCF db (other db) $ \it ->+        runConduit $ matchingSkip it (KeyRunBase 1) (KeyRun 1 29000) .| sinkList+      rs'' `shouldBe` drop 29000 (run 1 30000)+      list db (KeyRunBase 1) `shouldReturn` []+    it "ends a list where its prefix ends, wherever the chunks end" $ \db -> do+      -- Lists read 256 entries at a time, and conduits 16, then 64, then+      -- 256: each group has a number of keys at, just below or just above+      -- where one of those chunks ends, and the next group follows at once.+      let counts = [0, 1, 15, 16, 17, 79, 80, 81, 255, 256, 257, 335, 336, 337, 511, 512, 513, 592, 1024]+          groups = zip [10 ..] counts+      forM_ groups $ \(g, count) -> insertRun db Nothing g count+      forM_ groups $ \(g, count) -> do+        results <- everyWay db (KeyRunBase g)+        forM_ results (`shouldBe` run g count)+        first <- firstMatching db (KeyRunBase g)+        first `shouldBe` (if count == 0 then Nothing else Just (KeyRun g 0, runValue g 0))+    it "ends a list where the data ends, wherever the chunks end" $ \db ->+      forM_ [16, 256, 336, 512] $ \count -> do+        -- the last group of the database, longer with every round+        insertRun db Nothing 5 count+        results <- everyWay db (KeyRunBase 5)+        forM_ results (`shouldBe` run 5 count)+    it "reads values larger than a chunk may be" $ \db -> do+      -- a megabyte is the limit of a chunk: values above it, below it, and+      -- small ones between them+      let sizes = [10, 1500000, 20, 700000, 700000, 700000, 30, 2000000, 2000000, 40]+          entries = [(KeyRun 7 n, B.replicate size (fromIntegral n)) | (n, size) <- zip [0 ..] sizes]+      forM_ entries $ uncurry (insert db)+      insertRun db Nothing 8 10+      results <- everyWay db (KeyRunBase 7)+      forM_ results (`shouldBe` entries)+    it "reads only a little ahead of a consumer that stops" $ \db -> do+      insertRun db Nothing 1 1000+      withIter db $ \it -> do+        rs <- runConduit $ matching it (KeyRunBase 1) .| takeC 3 .| sinkList+        rs `shouldBe` take 3 (run 1 1000)+        -- the first chunk is of 16 entries, and no other was read+        iterKey it `shouldReturn` Just (encode (KeyRun 1 16))+        rs' <- runConduit $ matching it (KeyRunBase 1) .| takeC 17 .| sinkList+        rs' `shouldBe` take 17 (run 1 1000)+        -- the second is of 64+        iterKey it `shouldReturn` Just (encode (KeyRun 1 80))+    it "decodes an entry only when a consumer gets to it" $ \db -> do+      insertRun db Nothing 1 3+      -- a value that is not a ByteString: its length says more bytes than+      -- there are+      R.put db (encode (KeyRun 1 3)) (B.pack [0, 0, 0, 0, 0, 0, 0, 9, 1, 2, 3])+      withIter db $ \it -> do+        rs <- runConduit $ matching it (KeyRunBase 1) .| takeC 3 .| sinkList+        rs `shouldBe` run 1 3+        runConduit (stream it (KeyRunBase 1) .| sinkList) `shouldThrow` anyErrorCall+      list db (KeyRunBase 1) `shouldThrow` anyErrorCall+      firstMatching db (KeyRunBase 1) `shouldReturn` Just (KeyRun 1 0, runValue 1 0)+      firstFrom db (KeyRunBase 1) (KeyRun 1 3) `shouldThrow` anyErrorCall+    it "returns a list that does not need the iterator any more" $ \db -> do+      insertRun db Nothing 1 1000+      rs <- matchingAsList db (KeyRunBase 1)+      -- the database changes before the list is looked at+      forM_ (run 1 1000) $ \(k, _) -> R.delete db (encode k)+      n <- evaluate (length rs)+      n `shouldBe` 1000+      rs `shouldBe` run 1 1000+  where+    anyErrorCall :: Selector ErrorCall+    anyErrorCall = const True+    -- the queries at the types of a run, for where nothing else says them+    list :: DB -> KeyRun -> IO [(KeyRun, ByteString)]+    list = matchingAsList+    stream :: Iterator -> KeyRun -> ConduitT () (KeyRun, ByteString) IO ()+    stream = matching+    firstFrom :: DB -> KeyRun -> KeyRun -> IO (Maybe (KeyRun, ByteString))+    firstFrom = firstMatchingSkip