{-# OPTIONS_HADDOCK not-home #-}

module Database.LSMTree.Internal.Config (
    LevelNo (..)
    -- * Table configuration
  , TableConfig (..)
  , defaultTableConfig
  , RunLevelNo (..)
  , runParamsForLevel
    -- * Merge policy
  , MergePolicy (..)
    -- * Size ratio
  , SizeRatio (..)
  , sizeRatioInt
    -- * Write buffer allocation
  , WriteBufferAlloc (..)
    -- * Bloom filter allocation
  , BloomFilterAlloc (..)
  , bloomFilterAllocForLevel
    -- * Fence pointer index
  , FencePointerIndexType (..)
  , indexTypeForRun
  , serialiseKeyMinimalSize
    -- * Disk cache policy
  , DiskCachePolicy (..)
  , diskCachePolicyForLevel
    -- * Merge schedule
  , MergeSchedule (..)
  ) where

import           Control.DeepSeq (NFData (..))
import           Database.LSMTree.Internal.Index (IndexType)
import qualified Database.LSMTree.Internal.Index as Index
                     (IndexType (Compact, Ordinary))
import qualified Database.LSMTree.Internal.RawBytes as RB
import           Database.LSMTree.Internal.Run (RunDataCaching (..))
import           Database.LSMTree.Internal.RunAcc (RunBloomFilterAlloc (..))
import           Database.LSMTree.Internal.RunBuilder (RunParams (..))
import           Database.LSMTree.Internal.Serialise.Class (SerialiseKey (..))

newtype LevelNo = LevelNo Int
  deriving stock (Int -> LevelNo -> ShowS
[LevelNo] -> ShowS
LevelNo -> String
(Int -> LevelNo -> ShowS)
-> (LevelNo -> String) -> ([LevelNo] -> ShowS) -> Show LevelNo
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> LevelNo -> ShowS
showsPrec :: Int -> LevelNo -> ShowS
$cshow :: LevelNo -> String
show :: LevelNo -> String
$cshowList :: [LevelNo] -> ShowS
showList :: [LevelNo] -> ShowS
Show, LevelNo -> LevelNo -> Bool
(LevelNo -> LevelNo -> Bool)
-> (LevelNo -> LevelNo -> Bool) -> Eq LevelNo
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: LevelNo -> LevelNo -> Bool
== :: LevelNo -> LevelNo -> Bool
$c/= :: LevelNo -> LevelNo -> Bool
/= :: LevelNo -> LevelNo -> Bool
Eq, Eq LevelNo
Eq LevelNo =>
(LevelNo -> LevelNo -> Ordering)
-> (LevelNo -> LevelNo -> Bool)
-> (LevelNo -> LevelNo -> Bool)
-> (LevelNo -> LevelNo -> Bool)
-> (LevelNo -> LevelNo -> Bool)
-> (LevelNo -> LevelNo -> LevelNo)
-> (LevelNo -> LevelNo -> LevelNo)
-> Ord LevelNo
LevelNo -> LevelNo -> Bool
LevelNo -> LevelNo -> Ordering
LevelNo -> LevelNo -> LevelNo
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: LevelNo -> LevelNo -> Ordering
compare :: LevelNo -> LevelNo -> Ordering
$c< :: LevelNo -> LevelNo -> Bool
< :: LevelNo -> LevelNo -> Bool
$c<= :: LevelNo -> LevelNo -> Bool
<= :: LevelNo -> LevelNo -> Bool
$c> :: LevelNo -> LevelNo -> Bool
> :: LevelNo -> LevelNo -> Bool
$c>= :: LevelNo -> LevelNo -> Bool
>= :: LevelNo -> LevelNo -> Bool
$cmax :: LevelNo -> LevelNo -> LevelNo
max :: LevelNo -> LevelNo -> LevelNo
$cmin :: LevelNo -> LevelNo -> LevelNo
min :: LevelNo -> LevelNo -> LevelNo
Ord)
  deriving newtype (Int -> LevelNo
LevelNo -> Int
LevelNo -> [LevelNo]
LevelNo -> LevelNo
LevelNo -> LevelNo -> [LevelNo]
LevelNo -> LevelNo -> LevelNo -> [LevelNo]
(LevelNo -> LevelNo)
-> (LevelNo -> LevelNo)
-> (Int -> LevelNo)
-> (LevelNo -> Int)
-> (LevelNo -> [LevelNo])
-> (LevelNo -> LevelNo -> [LevelNo])
-> (LevelNo -> LevelNo -> [LevelNo])
-> (LevelNo -> LevelNo -> LevelNo -> [LevelNo])
-> Enum LevelNo
forall a.
(a -> a)
-> (a -> a)
-> (Int -> a)
-> (a -> Int)
-> (a -> [a])
-> (a -> a -> [a])
-> (a -> a -> [a])
-> (a -> a -> a -> [a])
-> Enum a
$csucc :: LevelNo -> LevelNo
succ :: LevelNo -> LevelNo
$cpred :: LevelNo -> LevelNo
pred :: LevelNo -> LevelNo
$ctoEnum :: Int -> LevelNo
toEnum :: Int -> LevelNo
$cfromEnum :: LevelNo -> Int
fromEnum :: LevelNo -> Int
$cenumFrom :: LevelNo -> [LevelNo]
enumFrom :: LevelNo -> [LevelNo]
$cenumFromThen :: LevelNo -> LevelNo -> [LevelNo]
enumFromThen :: LevelNo -> LevelNo -> [LevelNo]
$cenumFromTo :: LevelNo -> LevelNo -> [LevelNo]
enumFromTo :: LevelNo -> LevelNo -> [LevelNo]
$cenumFromThenTo :: LevelNo -> LevelNo -> LevelNo -> [LevelNo]
enumFromThenTo :: LevelNo -> LevelNo -> LevelNo -> [LevelNo]
Enum, LevelNo -> ()
(LevelNo -> ()) -> NFData LevelNo
forall a. (a -> ()) -> NFData a
$crnf :: LevelNo -> ()
rnf :: LevelNo -> ()
NFData)

{-------------------------------------------------------------------------------
  Table configuration
-------------------------------------------------------------------------------}

{- |
A collection of configuration parameters for tables, which can be used to tune the performance of the table.
To construct a 'TableConfig', modify the 'defaultTableConfig', which defines reasonable defaults for all parameters.

For a detailed discussion of fine-tuning the table configuration, see [Fine-tuning Table Configuration](../#fine_tuning).

[@confMergePolicy :: t'MergePolicy'@]
    The /merge policy/ balances the performance of lookups against the performance of updates.
    Levelling favours lookups.
    Tiering favours updates.
    Lazy levelling strikes a middle ground between levelling and tiering, and moderately favours updates.
    This parameter is explicitly referenced in the documentation of those operations it affects.

[@confSizeRatio :: t'SizeRatio'@]
    The /size ratio/ pushes the effects of the merge policy to the extreme.
    If the size ratio is higher, levelling favours lookups more, and tiering and lazy levelling favour updates more.
    This parameter is referred to as \(T\) in the disk I\/O cost of operations.

[@confWriteBufferAlloc :: t'WriteBufferAlloc'@]
    The /write buffer capacity/ balances the performance of lookups and updates against the in-memory size of the database.
    If the write buffer is larger, it takes up more memory, but lookups and updates are more efficient.
    This parameter is referred to as \(B\) in the disk I\/O cost of operations.
    Irrespective of this parameter, the write buffer size cannot exceed 4GiB.

[@confMergeSchedule :: t'MergeSchedule'@]
    The /merge schedule/ balances the performance of lookups and updates against the consistency of updates.
    The merge schedule does not affect the performance of table unions.
    With the one-shot merge schedule, lookups and updates are more efficient overall, but some updates may take much longer than others.
    With the incremental merge schedule, lookups and updates are less efficient overall, but each update does a similar amount of work.
    This parameter is explicitly referenced in the documentation of those operations it affects.

[@confBloomFilterAlloc :: t'BloomFilterAlloc'@]
    The Bloom filter size balances the performance of lookups against the in-memory size of the database.
    If the Bloom filters are larger, they take up more memory, but lookup operations are more efficient.

[@confFencePointerIndex :: t'FencePointerIndexType'@]
    The /fence-pointer index type/ supports two types of indexes.
    The /ordinary/ indexes are designed to work with any key.
    The /compact/ indexes are optimised for the case where the keys in the database are uniformly distributed, e.g., when the keys are hashes.

[@confDiskCachePolicy :: t'DiskCachePolicy'@]
    The /disk cache policy/ supports caching lookup operations using the OS page cache.
    Caching may improve the performance of lookups if database access follows certain patterns.
-}
data TableConfig = TableConfig {
    TableConfig -> MergePolicy
confMergePolicy       :: !MergePolicy
  , TableConfig -> MergeSchedule
confMergeSchedule     :: !MergeSchedule
  , TableConfig -> SizeRatio
confSizeRatio         :: !SizeRatio
  , TableConfig -> WriteBufferAlloc
confWriteBufferAlloc  :: !WriteBufferAlloc
  , TableConfig -> BloomFilterAlloc
confBloomFilterAlloc  :: !BloomFilterAlloc
  , TableConfig -> FencePointerIndexType
confFencePointerIndex :: !FencePointerIndexType
  , TableConfig -> DiskCachePolicy
confDiskCachePolicy   :: !DiskCachePolicy
  }
  deriving stock (Int -> TableConfig -> ShowS
[TableConfig] -> ShowS
TableConfig -> String
(Int -> TableConfig -> ShowS)
-> (TableConfig -> String)
-> ([TableConfig] -> ShowS)
-> Show TableConfig
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> TableConfig -> ShowS
showsPrec :: Int -> TableConfig -> ShowS
$cshow :: TableConfig -> String
show :: TableConfig -> String
$cshowList :: [TableConfig] -> ShowS
showList :: [TableConfig] -> ShowS
Show, TableConfig -> TableConfig -> Bool
(TableConfig -> TableConfig -> Bool)
-> (TableConfig -> TableConfig -> Bool) -> Eq TableConfig
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: TableConfig -> TableConfig -> Bool
== :: TableConfig -> TableConfig -> Bool
$c/= :: TableConfig -> TableConfig -> Bool
/= :: TableConfig -> TableConfig -> Bool
Eq)

instance NFData TableConfig where
  rnf :: TableConfig -> ()
rnf (TableConfig MergePolicy
a MergeSchedule
b SizeRatio
c WriteBufferAlloc
d BloomFilterAlloc
e FencePointerIndexType
f DiskCachePolicy
g) =
      MergePolicy -> ()
forall a. NFData a => a -> ()
rnf MergePolicy
a () -> () -> ()
forall a b. a -> b -> b
`seq` MergeSchedule -> ()
forall a. NFData a => a -> ()
rnf MergeSchedule
b () -> () -> ()
forall a b. a -> b -> b
`seq` SizeRatio -> ()
forall a. NFData a => a -> ()
rnf SizeRatio
c () -> () -> ()
forall a b. a -> b -> b
`seq` WriteBufferAlloc -> ()
forall a. NFData a => a -> ()
rnf WriteBufferAlloc
d () -> () -> ()
forall a b. a -> b -> b
`seq` BloomFilterAlloc -> ()
forall a. NFData a => a -> ()
rnf BloomFilterAlloc
e () -> () -> ()
forall a b. a -> b -> b
`seq` FencePointerIndexType -> ()
forall a. NFData a => a -> ()
rnf FencePointerIndexType
f () -> () -> ()
forall a b. a -> b -> b
`seq` DiskCachePolicy -> ()
forall a. NFData a => a -> ()
rnf DiskCachePolicy
g

-- | The 'defaultTableConfig' defines reasonable defaults for all 'TableConfig' parameters.
--
-- >>> confMergePolicy defaultTableConfig
-- LazyLevelling
-- >>> confMergeSchedule defaultTableConfig
-- Incremental
-- >>> confSizeRatio defaultTableConfig
-- Four
-- >>> confWriteBufferAlloc defaultTableConfig
-- AllocNumEntries 20000
-- >>> confBloomFilterAlloc defaultTableConfig
-- AllocRequestFPR 1.0e-3
-- >>> confFencePointerIndex defaultTableConfig
-- OrdinaryIndex
-- >>> confDiskCachePolicy defaultTableConfig
-- DiskCacheAll
--
defaultTableConfig :: TableConfig
defaultTableConfig :: TableConfig
defaultTableConfig =
    TableConfig
      { confMergePolicy :: MergePolicy
confMergePolicy       = MergePolicy
LazyLevelling
      , confMergeSchedule :: MergeSchedule
confMergeSchedule     = MergeSchedule
Incremental
      , confSizeRatio :: SizeRatio
confSizeRatio         = SizeRatio
Four
      , confWriteBufferAlloc :: WriteBufferAlloc
confWriteBufferAlloc  = Int -> WriteBufferAlloc
AllocNumEntries Int
20_000
      , confBloomFilterAlloc :: BloomFilterAlloc
confBloomFilterAlloc  = Double -> BloomFilterAlloc
AllocRequestFPR Double
1.0e-3
      , confFencePointerIndex :: FencePointerIndexType
confFencePointerIndex = FencePointerIndexType
OrdinaryIndex
      , confDiskCachePolicy :: DiskCachePolicy
confDiskCachePolicy   = DiskCachePolicy
DiskCacheAll
      }

data RunLevelNo = RegularLevel LevelNo | UnionLevel

runParamsForLevel :: TableConfig -> RunLevelNo -> RunParams
runParamsForLevel :: TableConfig -> RunLevelNo -> RunParams
runParamsForLevel conf :: TableConfig
conf@TableConfig {DiskCachePolicy
FencePointerIndexType
BloomFilterAlloc
MergeSchedule
WriteBufferAlloc
SizeRatio
MergePolicy
confMergePolicy :: TableConfig -> MergePolicy
confMergeSchedule :: TableConfig -> MergeSchedule
confSizeRatio :: TableConfig -> SizeRatio
confWriteBufferAlloc :: TableConfig -> WriteBufferAlloc
confBloomFilterAlloc :: TableConfig -> BloomFilterAlloc
confFencePointerIndex :: TableConfig -> FencePointerIndexType
confDiskCachePolicy :: TableConfig -> DiskCachePolicy
confMergePolicy :: MergePolicy
confMergeSchedule :: MergeSchedule
confSizeRatio :: SizeRatio
confWriteBufferAlloc :: WriteBufferAlloc
confBloomFilterAlloc :: BloomFilterAlloc
confFencePointerIndex :: FencePointerIndexType
confDiskCachePolicy :: DiskCachePolicy
..} RunLevelNo
levelNo =
    RunParams
      { runParamCaching :: RunDataCaching
runParamCaching = DiskCachePolicy -> RunLevelNo -> RunDataCaching
diskCachePolicyForLevel DiskCachePolicy
confDiskCachePolicy RunLevelNo
levelNo
      , runParamAlloc :: RunBloomFilterAlloc
runParamAlloc   = TableConfig -> RunLevelNo -> RunBloomFilterAlloc
bloomFilterAllocForLevel TableConfig
conf RunLevelNo
levelNo
      , runParamIndex :: IndexType
runParamIndex   = FencePointerIndexType -> IndexType
indexTypeForRun FencePointerIndexType
confFencePointerIndex
      }

{-------------------------------------------------------------------------------
  Merge policy
-------------------------------------------------------------------------------}

{- |
The /merge policy/ balances the performance of lookups against the performance of updates.
Levelling favours lookups.
Tiering favours updates.
Lazy levelling strikes a middle ground between levelling and tiering, and moderately favours updates.
This parameter is explicitly referenced in the documentation of those operations it affects.

__NOTE:__ This package only supports lazy levelling.

For a detailed discussion of the merge policy, see [Fine-tuning: Merge Policy, Size Ratio, and Write Buffer Size](../#fine_tuning_data_layout).
-}
data MergePolicy =
    LazyLevelling
  deriving stock (MergePolicy -> MergePolicy -> Bool
(MergePolicy -> MergePolicy -> Bool)
-> (MergePolicy -> MergePolicy -> Bool) -> Eq MergePolicy
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: MergePolicy -> MergePolicy -> Bool
== :: MergePolicy -> MergePolicy -> Bool
$c/= :: MergePolicy -> MergePolicy -> Bool
/= :: MergePolicy -> MergePolicy -> Bool
Eq, Int -> MergePolicy -> ShowS
[MergePolicy] -> ShowS
MergePolicy -> String
(Int -> MergePolicy -> ShowS)
-> (MergePolicy -> String)
-> ([MergePolicy] -> ShowS)
-> Show MergePolicy
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> MergePolicy -> ShowS
showsPrec :: Int -> MergePolicy -> ShowS
$cshow :: MergePolicy -> String
show :: MergePolicy -> String
$cshowList :: [MergePolicy] -> ShowS
showList :: [MergePolicy] -> ShowS
Show)

instance NFData MergePolicy where
  rnf :: MergePolicy -> ()
rnf MergePolicy
LazyLevelling = ()

{-------------------------------------------------------------------------------
  Size ratio
-------------------------------------------------------------------------------}

{- |
The /size ratio/ pushes the effects of the merge policy to the extreme.
If the size ratio is higher, levelling favours lookups more, and tiering and lazy levelling favour updates more.
This parameter is referred to as \(T\) in the disk I\/O cost of operations.

__NOTE:__ This package only supports a size ratio of four.

For a detailed discussion of the size ratio, see [Fine-tuning: Merge Policy, Size Ratio, and Write Buffer Size](../#fine_tuning_data_layout).
-}
data SizeRatio = Four
  deriving stock (SizeRatio -> SizeRatio -> Bool
(SizeRatio -> SizeRatio -> Bool)
-> (SizeRatio -> SizeRatio -> Bool) -> Eq SizeRatio
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: SizeRatio -> SizeRatio -> Bool
== :: SizeRatio -> SizeRatio -> Bool
$c/= :: SizeRatio -> SizeRatio -> Bool
/= :: SizeRatio -> SizeRatio -> Bool
Eq, Int -> SizeRatio -> ShowS
[SizeRatio] -> ShowS
SizeRatio -> String
(Int -> SizeRatio -> ShowS)
-> (SizeRatio -> String)
-> ([SizeRatio] -> ShowS)
-> Show SizeRatio
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> SizeRatio -> ShowS
showsPrec :: Int -> SizeRatio -> ShowS
$cshow :: SizeRatio -> String
show :: SizeRatio -> String
$cshowList :: [SizeRatio] -> ShowS
showList :: [SizeRatio] -> ShowS
Show)

instance NFData SizeRatio where
  rnf :: SizeRatio -> ()
rnf SizeRatio
Four = ()

sizeRatioInt :: SizeRatio -> Int
sizeRatioInt :: SizeRatio -> Int
sizeRatioInt = \case SizeRatio
Four -> Int
4

{-------------------------------------------------------------------------------
  Write buffer allocation
-------------------------------------------------------------------------------}

-- TODO: "If the sizes of values vary greatly, this can lead to unevenly sized runs on disk and unpredictable performance."

{- |
The /write buffer capacity/ balances the performance of lookups and updates against the in-memory size of the table.
If the write buffer is larger, it takes up more memory, but lookups and updates are more efficient.
Irrespective of this parameter, the write buffer size cannot exceed 4GiB.

For a detailed discussion of the size ratio, see [Fine-tuning: Merge Policy, Size Ratio, and Write Buffer Size](../#fine_tuning_data_layout).
-}
data WriteBufferAlloc =
    {- |
    Allocate space for the in-memory write buffer to fit the requested number of entries.
    This parameter is referred to as \(B\) in the disk I\/O cost of operations.
    -}
    AllocNumEntries !Int
  deriving stock (Int -> WriteBufferAlloc -> ShowS
[WriteBufferAlloc] -> ShowS
WriteBufferAlloc -> String
(Int -> WriteBufferAlloc -> ShowS)
-> (WriteBufferAlloc -> String)
-> ([WriteBufferAlloc] -> ShowS)
-> Show WriteBufferAlloc
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> WriteBufferAlloc -> ShowS
showsPrec :: Int -> WriteBufferAlloc -> ShowS
$cshow :: WriteBufferAlloc -> String
show :: WriteBufferAlloc -> String
$cshowList :: [WriteBufferAlloc] -> ShowS
showList :: [WriteBufferAlloc] -> ShowS
Show, WriteBufferAlloc -> WriteBufferAlloc -> Bool
(WriteBufferAlloc -> WriteBufferAlloc -> Bool)
-> (WriteBufferAlloc -> WriteBufferAlloc -> Bool)
-> Eq WriteBufferAlloc
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: WriteBufferAlloc -> WriteBufferAlloc -> Bool
== :: WriteBufferAlloc -> WriteBufferAlloc -> Bool
$c/= :: WriteBufferAlloc -> WriteBufferAlloc -> Bool
/= :: WriteBufferAlloc -> WriteBufferAlloc -> Bool
Eq)

instance NFData WriteBufferAlloc where
  rnf :: WriteBufferAlloc -> ()
rnf (AllocNumEntries Int
n) = Int -> ()
forall a. NFData a => a -> ()
rnf Int
n

{-------------------------------------------------------------------------------
  Merge schedule
-------------------------------------------------------------------------------}

{- |
The /merge schedule/ balances the performance of lookups and updates against the consistency of updates.
The merge schedule does not affect the performance of table unions.
With the one-shot merge schedule, lookups and updates are more efficient overall, but some updates may take much longer than others.
With the incremental merge schedule, lookups and updates are less efficient overall, but each update does a similar amount of work.
This parameter is explicitly referenced in the documentation of those operations it affects.

For a detailed discussion of the effect of the merge schedule, see [Fine-tuning: Merge Schedule](../#fine_tuning_merge_schedule).
-}
data MergeSchedule =
    {- |
    The 'OneShot' merge schedule causes the merging algorithm to complete merges immediately.
    This is more efficient than the 'Incremental' merge schedule, but has an inconsistent workload.
    Using the 'OneShot' merge schedule, the worst-case disk I\/O complexity of the update operations is /linear/ in the size of the table.
    For real-time systems and other use cases where unresponsiveness is unacceptable, use the 'Incremental' merge schedule.
    -}
    OneShot
    {- |
    The 'Incremental' merge schedule spreads out the merging work over time.
    This is less efficient than the 'OneShot' merge schedule, but has a consistent workload.
    Using the 'Incremental' merge schedule, the worst-case disk I\/O complexity of the update operations is /logarithmic/ in the size of the table.
    -}
  | Incremental
  deriving stock (MergeSchedule -> MergeSchedule -> Bool
(MergeSchedule -> MergeSchedule -> Bool)
-> (MergeSchedule -> MergeSchedule -> Bool) -> Eq MergeSchedule
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: MergeSchedule -> MergeSchedule -> Bool
== :: MergeSchedule -> MergeSchedule -> Bool
$c/= :: MergeSchedule -> MergeSchedule -> Bool
/= :: MergeSchedule -> MergeSchedule -> Bool
Eq, Int -> MergeSchedule -> ShowS
[MergeSchedule] -> ShowS
MergeSchedule -> String
(Int -> MergeSchedule -> ShowS)
-> (MergeSchedule -> String)
-> ([MergeSchedule] -> ShowS)
-> Show MergeSchedule
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> MergeSchedule -> ShowS
showsPrec :: Int -> MergeSchedule -> ShowS
$cshow :: MergeSchedule -> String
show :: MergeSchedule -> String
$cshowList :: [MergeSchedule] -> ShowS
showList :: [MergeSchedule] -> ShowS
Show)

instance NFData MergeSchedule where
  rnf :: MergeSchedule -> ()
rnf MergeSchedule
OneShot     = ()
  rnf MergeSchedule
Incremental = ()

{-------------------------------------------------------------------------------
  Bloom filter allocation
-------------------------------------------------------------------------------}

{- |
The Bloom filter size balances the performance of lookups against the in-memory size of the table.
If the Bloom filters are larger, they take up more memory, but lookup operations are more efficient.

For a detailed discussion of the Bloom filter size, see [Fine-tuning: Bloom Filter Size](../#fine_tuning_bloom_filter_size).
-}
data BloomFilterAlloc =
    {- |
    Allocate the requested number of bits per entry in the table.

    The value must strictly positive, but fractional values are permitted.
    The recommended range is \([2, 24]\).
    -}
    AllocFixed !Double
  | {- |
    Allocate the required number of bits per entry to get the requested false-positive rate.

    The value must be in the range \((0, 1)\).
    The recommended range is \([1\mathrm{e}{ -5 },1\mathrm{e}{ -2 }]\).
    -}
    AllocRequestFPR !Double
  deriving stock (Int -> BloomFilterAlloc -> ShowS
[BloomFilterAlloc] -> ShowS
BloomFilterAlloc -> String
(Int -> BloomFilterAlloc -> ShowS)
-> (BloomFilterAlloc -> String)
-> ([BloomFilterAlloc] -> ShowS)
-> Show BloomFilterAlloc
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> BloomFilterAlloc -> ShowS
showsPrec :: Int -> BloomFilterAlloc -> ShowS
$cshow :: BloomFilterAlloc -> String
show :: BloomFilterAlloc -> String
$cshowList :: [BloomFilterAlloc] -> ShowS
showList :: [BloomFilterAlloc] -> ShowS
Show, BloomFilterAlloc -> BloomFilterAlloc -> Bool
(BloomFilterAlloc -> BloomFilterAlloc -> Bool)
-> (BloomFilterAlloc -> BloomFilterAlloc -> Bool)
-> Eq BloomFilterAlloc
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: BloomFilterAlloc -> BloomFilterAlloc -> Bool
== :: BloomFilterAlloc -> BloomFilterAlloc -> Bool
$c/= :: BloomFilterAlloc -> BloomFilterAlloc -> Bool
/= :: BloomFilterAlloc -> BloomFilterAlloc -> Bool
Eq)

instance NFData BloomFilterAlloc where
  rnf :: BloomFilterAlloc -> ()
rnf (AllocFixed Double
n)        = Double -> ()
forall a. NFData a => a -> ()
rnf Double
n
  rnf (AllocRequestFPR Double
fpr) = Double -> ()
forall a. NFData a => a -> ()
rnf Double
fpr

bloomFilterAllocForLevel :: TableConfig -> RunLevelNo -> RunBloomFilterAlloc
bloomFilterAllocForLevel :: TableConfig -> RunLevelNo -> RunBloomFilterAlloc
bloomFilterAllocForLevel TableConfig
conf RunLevelNo
_levelNo =
    case TableConfig -> BloomFilterAlloc
confBloomFilterAlloc TableConfig
conf of
      AllocFixed Double
n        -> Double -> RunBloomFilterAlloc
RunAllocFixed Double
n
      AllocRequestFPR Double
fpr -> Double -> RunBloomFilterAlloc
RunAllocRequestFPR Double
fpr

{-------------------------------------------------------------------------------
  Fence pointer index
-------------------------------------------------------------------------------}

{- |
The /fence-pointer index type/ supports two types of indexes.
The /ordinary/ indexes are designed to work with any key.
The /compact/ indexes are optimised for the case where the keys in the database are uniformly distributed, e.g., when the keys are hashes.

For a detailed discussion the fence-pointer index types, see [Fine-tuning: Fence-Pointer Index Type](../#fine_tuning_fence_pointer_index_type).
-}
data FencePointerIndexType =
    {- |
    Ordinary indexes are designed to work with any key.

    When using an ordinary index, the 'Database.LSMTree.Internal.Serialise.Class.serialiseKey' function cannot produce output larger than 64KiB.
    -}
    OrdinaryIndex
  | {- |
    Compact indexes are designed  for the case where the keys in the database are uniformly distributed, e.g., when the keys are hashes.

    When using a compact index, the 'Database.LSMTree.Internal.Serialise.Class.serialiseKey' function must satisfy the following additional law:

    [Minimal size]
      @'Database.LSMTree.Internal.RawBytes.size' ('Database.LSMTree.Internal.Serialise.Class.serialiseKey' x) >= 8@

    Use 'serialiseKeyMinimalSize' to test this law.
    -}
    CompactIndex
  deriving stock (FencePointerIndexType -> FencePointerIndexType -> Bool
(FencePointerIndexType -> FencePointerIndexType -> Bool)
-> (FencePointerIndexType -> FencePointerIndexType -> Bool)
-> Eq FencePointerIndexType
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: FencePointerIndexType -> FencePointerIndexType -> Bool
== :: FencePointerIndexType -> FencePointerIndexType -> Bool
$c/= :: FencePointerIndexType -> FencePointerIndexType -> Bool
/= :: FencePointerIndexType -> FencePointerIndexType -> Bool
Eq, Int -> FencePointerIndexType -> ShowS
[FencePointerIndexType] -> ShowS
FencePointerIndexType -> String
(Int -> FencePointerIndexType -> ShowS)
-> (FencePointerIndexType -> String)
-> ([FencePointerIndexType] -> ShowS)
-> Show FencePointerIndexType
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> FencePointerIndexType -> ShowS
showsPrec :: Int -> FencePointerIndexType -> ShowS
$cshow :: FencePointerIndexType -> String
show :: FencePointerIndexType -> String
$cshowList :: [FencePointerIndexType] -> ShowS
showList :: [FencePointerIndexType] -> ShowS
Show)

instance NFData FencePointerIndexType where
  rnf :: FencePointerIndexType -> ()
rnf FencePointerIndexType
CompactIndex  = ()
  rnf FencePointerIndexType
OrdinaryIndex = ()

indexTypeForRun :: FencePointerIndexType -> IndexType
indexTypeForRun :: FencePointerIndexType -> IndexType
indexTypeForRun FencePointerIndexType
CompactIndex  = IndexType
Index.Compact
indexTypeForRun FencePointerIndexType
OrdinaryIndex = IndexType
Index.Ordinary

-- | Test the __Minimal size__ law for the 'CompactIndex' option.
serialiseKeyMinimalSize :: SerialiseKey k => k -> Bool
serialiseKeyMinimalSize :: forall k. SerialiseKey k => k -> Bool
serialiseKeyMinimalSize k
x = RawBytes -> Int
RB.size (k -> RawBytes
forall k. SerialiseKey k => k -> RawBytes
serialiseKey k
x) Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
8

{-------------------------------------------------------------------------------
  Disk cache policy
-------------------------------------------------------------------------------}

{- |
The /disk cache policy/ determines if lookup operations use the OS page cache.
Caching may improve the performance of lookups if database access follows certain patterns.

For a detailed discussion the disk cache policy, see [Fine-tuning: Disk Cache Policy](../#fine_tuning_disk_cache_policy).
-}
data DiskCachePolicy =
    {- |
    Cache all data in the table.

    Use this policy if the database's access pattern has either good spatial locality or both good spatial and temporal locality.
    -}
    DiskCacheAll

  | {- |
    Cache the data in the freshest @l@ levels.

    Use this policy if the database's access pattern only has good temporal locality.

    The variable @l@ determines the number of levels that are cached.
    For a description of levels, see [Merge Policy, Size Ratio, and Write Buffer Size](#fine_tuning_data_layout).
    With this setting, the database can be expected to cache up to \(\frac{k}{P}\) pages of memory,
    where \(k\) refers to the number of entries that fit in levels \([1,l]\) and is defined as \(\sum_{i=1}^{l}BT^{i}\).
    -}
    -- TODO: Add a policy for caching based on size in bytes, rather than exposing internal details such as levels.
    --       For instance, a policy that states "cache the freshest 10MiB"
    DiskCacheLevelOneTo !Int

  | {- |
    Do not cache any table data.

    Use this policy if the database's access pattern has does not have good spatial or temporal locality.
    For instance, if the access pattern is uniformly random.
    -}
    DiskCacheNone
  deriving stock (Int -> DiskCachePolicy -> ShowS
[DiskCachePolicy] -> ShowS
DiskCachePolicy -> String
(Int -> DiskCachePolicy -> ShowS)
-> (DiskCachePolicy -> String)
-> ([DiskCachePolicy] -> ShowS)
-> Show DiskCachePolicy
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> DiskCachePolicy -> ShowS
showsPrec :: Int -> DiskCachePolicy -> ShowS
$cshow :: DiskCachePolicy -> String
show :: DiskCachePolicy -> String
$cshowList :: [DiskCachePolicy] -> ShowS
showList :: [DiskCachePolicy] -> ShowS
Show, DiskCachePolicy -> DiskCachePolicy -> Bool
(DiskCachePolicy -> DiskCachePolicy -> Bool)
-> (DiskCachePolicy -> DiskCachePolicy -> Bool)
-> Eq DiskCachePolicy
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: DiskCachePolicy -> DiskCachePolicy -> Bool
== :: DiskCachePolicy -> DiskCachePolicy -> Bool
$c/= :: DiskCachePolicy -> DiskCachePolicy -> Bool
/= :: DiskCachePolicy -> DiskCachePolicy -> Bool
Eq)

instance NFData DiskCachePolicy where
  rnf :: DiskCachePolicy -> ()
rnf DiskCachePolicy
DiskCacheAll            = ()
  rnf (DiskCacheLevelOneTo Int
l) = Int -> ()
forall a. NFData a => a -> ()
rnf Int
l
  rnf DiskCachePolicy
DiskCacheNone           = ()

-- | Interpret the 'DiskCachePolicy' for a level: should we cache data in runs
-- at this level.
--
diskCachePolicyForLevel :: DiskCachePolicy -> RunLevelNo -> RunDataCaching
diskCachePolicyForLevel :: DiskCachePolicy -> RunLevelNo -> RunDataCaching
diskCachePolicyForLevel DiskCachePolicy
policy RunLevelNo
levelNo =
  case DiskCachePolicy
policy of
    DiskCachePolicy
DiskCacheAll          -> RunDataCaching
CacheRunData
    DiskCachePolicy
DiskCacheNone         -> RunDataCaching
NoCacheRunData
    DiskCacheLevelOneTo Int
n ->
      case RunLevelNo
levelNo of
        RegularLevel LevelNo
l | LevelNo
l LevelNo -> LevelNo -> Bool
forall a. Ord a => a -> a -> Bool
<= Int -> LevelNo
LevelNo Int
n -> RunDataCaching
CacheRunData
                       | Bool
otherwise      -> RunDataCaching
NoCacheRunData
        RunLevelNo
UnionLevel                      -> RunDataCaching
NoCacheRunData