Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This sounds like a variation of the <a href="http://en.wikipedia.org/wiki/Bin_packing_problem" rel="nofollow noreferrer">bin packing problem</a>, but where you already have an inferior allocation that you want to improve. So I suggest looking at variations of the approaches which are successful for the bin packing problem.</p> <p>First of all, you probably want to parameterize your problem by defining what you consider "full enough" (where a block is full enough that you don't want to touch it), and what is "too empty" (where a block has so much empty space that it has to have more records added to it). Then, you can classify all the blocks as full enough, too empty, or partially full (those that are neither full enough nor too empty). You then redefine the problem as how to eliminate all the too empty blocks by creating as many full enough blocks as possible while minimising the number of partially full blocks.</p> <p>You'll also want to work out what's more important: getting the records into the fewest blocks possible, or packing them adequately but with the least amount of blocks read and written.</p> <p>My approach would be to make an initial pass over all the blocks, to classify them all into one of the three classes defined above. For each block, you also want to keep track of the free space available in it, and for the too empty blocks, you'll want to have a list of all the records and their sizes. Then, starting with the largest records in the too empty blocks, move them into the partially full blocks. If you want to minimise reads and writes, move them into any of the blocks you currently have in memory. If you want to minimise wasted space, find the block with the least amount of empty space that will still hold the record, reading the block in if necessary. If no block will hold the record, create a new block. If a block in memory reaches the "full enough" threshold, write it out. Repeat until all the records in the partially filled blocks have been placed.</p> <p>I've skipped over more than a few details, but this should give you some idea. Note that the bin packing problem is <a href="http://en.wikipedia.org/wiki/NP-hard" rel="nofollow noreferrer">NP-hard</a>, which means that for practical applications, you'll want to decide what's most important to you, so you can pick an approach that will give you an approximately best solution in reasonable time.</p>
    singulars
    1. This table or related slice is empty.
    1. POWhat is a good algorithm for compacting records in a blocked file?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USTimB
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POWhat is a good algorithm for compacting records in a blocked file?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COThanks for pointing out the bin packing problem comparison. This is helpful. A tricky part to a solution is the sheer volume of records to scan in the first pass and hold stats for is prohibitive. Also because writes are expensive, in a sense you only get a chance or two re-write a given block
      singulars
      1. PO
      1. USTall Jeff
    2. COIdeally, I'm thinking of some number of passes are used to target certain blocks and records for consolidation. ie: Find the lowest hanging fruit of each pass to harvest and stop when too much time or no significant optimizations remain. Thanks again!
      singulars
      1. PO
      1. USTall Jeff
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload